public class SuffixArray
extends java.lang.Object
This class was originally created by Doug McIlroy, Adj. Prof. of CS. at Dartmouth. At that time it served as suffixArray java wrapper for the suffix-array he wrote in C.
Comments and additions were later made by Jonathan Carlson.
Charles DeZiel then rewrote the C code in Java to remove any platform dependence, and added the use of char[]sourceCharArray
in place of Strings in order to speed things up and save on memory use. (The addition of char[]sourceCharArray may
not actually be helpful as comparison tests were never done.)
This was later replaced by the use of char[] and int[], and the implementation of quick sort, by Jonathan Carlson. This improved memory and running time of creating SuffixArrays by ~4-5 fold each.
Modifier and Type | Field and Description |
---|---|
private java.lang.String |
sequence |
private int[] |
suffixArray |
Modifier | Constructor and Description |
---|---|
|
SuffixArray(java.lang.String s0)
Builds suffixArray suffix array for the given string.
|
private |
SuffixArray(java.lang.String pSequence,
boolean doCheckData) |
|
SuffixArray(java.lang.String s0,
int[] a0)
Builds suffixArray suffix array for the given string.
|
Modifier and Type | Method and Description |
---|---|
static boolean |
checkData(char[] charArray,
int[] suffixArray)
Compares the array to the string to make sure they match.
|
private static int |
compare(char[] charArray,
int i,
int j)
Compares the suffix starting at i to the suffix starting at j.
|
int |
count(java.lang.String x)
Returns the number of times that x occurs in the sequence.
|
int[] |
find(java.lang.String x)
Returns an unsorted array of the indices of where x occurs in the sequence.
|
int |
findBegin(java.lang.String query)
Returns the array index for the alphabetically first instance of x.
|
int |
findEnd(java.lang.String query)
Returns the array index one past the alphabetically last instance of x.
|
int |
get(int suffixArrayIndex) |
int[] |
getArray() |
int[] |
getHits(int start,
int end) |
java.lang.String |
getSequence() |
private static boolean |
isTerminalChar(char theChar) |
static void |
main(java.lang.String[] args) |
private static int |
med3(int[] x,
int a,
int b,
int c)
Returns the index of the median of the three indexed integers.
|
private int |
restrictedCompare(java.lang.String query,
int j)
Compares the query string the suffix starting at j, but only looks at the first |query| letter of the suffix.
|
private static void |
sort(char[] charArray,
int[] a)
Copied and modified from Sun's Java source code in java.util.Arrays Sorts the specified array of ints into ascending numerical order.
|
private static void |
sort1(char[] charArray,
int[] x,
int offset,
int length)
Sorts the specified sub-array of integers into ascending order.
|
private static void |
swap(int[] x,
int a,
int b)
Swaps x[a] with x[b].
|
private static java.lang.String |
toString(char[] charArray,
int i) |
private static void |
vecswap(int[] x,
int a,
int b,
int n)
Swaps x[a ..
|
private final java.lang.String sequence
private final int[] suffixArray
public SuffixArray(java.lang.String s0)
private SuffixArray(java.lang.String pSequence, boolean doCheckData)
public SuffixArray(java.lang.String s0, int[] a0)
public static boolean checkData(char[] charArray, int[] suffixArray)
private static int compare(char[] charArray, int i, int j)
private static boolean isTerminalChar(char theChar)
public static void main(java.lang.String[] args)
private static int med3(int[] x, int a, int b, int c)
private static void sort(char[] charArray, int[] a)
a
- the array to be sortedprivate static void sort1(char[] charArray, int[] x, int offset, int length)
private static void swap(int[] x, int a, int b)
private static java.lang.String toString(char[] charArray, int i)
private static void vecswap(int[] x, int a, int b, int n)
public int count(java.lang.String x)
public int[] find(java.lang.String x)
public int findBegin(java.lang.String query)
public int findEnd(java.lang.String query)
public int get(int suffixArrayIndex)
public int[] getArray()
public int[] getHits(int start, int end)
public java.lang.String getSequence()
private int restrictedCompare(java.lang.String query, int j)