What is this site? It is generaly simplier version of wikipedia. You will find there selected articles. Enjoy!
In computer science, a suffix array is an array of integers giving the starting positions of suffixes of a string in lexicographical order.
Contents |
Consider the string
of length 12, that ends with a sentinel letter $, appearing only once and less than any other letter in the string.
It has twelve suffixes: "abracadabra$", "bracadabra$", "racadabra$", and so on down to "a$" and "$" that can be sorted into lexicographical order to obtain:
If the original string is available, each suffix can be completely specified by the index of its first character. The suffix array is the array of the indices of suffixes sorted in lexicographical order. For the string "abracadabra$", using one-based indexing, the suffix array is {12,11,8,1,4,6,9,2,5,7,10,3}, because the suffix "$" begins at position 12, "a$" begins at position 11, "abra$" begins at position 8, and so forth.
The longest common prefix is also shown above as lcp. This value, stored alongside the list of prefix indices, indicates how many characters a particular suffix has in common with the suffix directly above it, starting at the beginning of both suffixes. The lcp is useful in making some string operations more efficient. For example, it can be used to avoid comparing characters that are already known to be the same when searching through the list of suffixes. The fact that the minimum lcp value belonging to a consecutive set of sorted prefixes gives the longest common prefix among all of those suffixes can also be useful.
The easiest way to construct a suffix array is to use an efficient comparison sort algorithm. This requires O(nlogn) suffix comparisons, but a suffix comparison requires O(n) time, so the overall runtime of this approach is O(n2logn). More sophisticated algorithms improve this to O(nlogn) by exploiting the results of partial sorts to avoid redundant comparisons. Several Θ(n) algorithms (of Pang Ko and Srinivas Aluru, Juha Kärkkäinen and Peter Sanders, etc) have also been developed which provide faster construction and have space usage of O(n) with low constants.
Recent work by Salson et al. proposes an algorithm for updating the suffix array of a text that has been edited instead of rebuilding a new suffix array from scratch. Even if the theoretical worst-case time complexity is O(nlogn), it appears to perform well in practice: experimental results from the authors showed that their implementation of dynamic suffix arrays is generally more efficient than rebuilding when comparing the insertion of 500 characters into their dynamic array with a complete rebuild of a static suffix array containing the updated text.
The suffix array of a string can be used as an index to quickly locate every occurrence of a substring within the string. Finding every occurrence of the substring is equivalent to finding every suffix that begins with the substring. Thanks to the lexicographical ordering, these suffixes will be grouped together in the suffix array, and can be found efficiently with a binary search. If implemented straightforwardly, this binary search takes O(mlogn) time, where m is the length of the substring W. The following pseudo-code from Manber and Myers shows how to find W (or the suffix lexicographically immediately before W if W is not present) in a suffix array with indices stored in pos.
if W <= suffixAt(pos[0]) then
ans = 0
else if W > suffixAt(pos[m-1]) then
ans = m
else
{
L = 0, R = m-1
while R-L > 1 do
{
M = (L + R)/2
if W <= suffixAt(pos[M]) then
R = M
else
L = M
}
ans = R
}
To avoid redoing comparisons, extra data structures giving information about the longest common prefixes (LCPs) of suffixes are constructed, giving O(m + logn) search time.
Suffix sorting algorithms can be used to perform the Burrows–Wheeler transform (BWT). Technically the BWT requires sorting cyclic permutations of a string, not suffixes. We can fix this by appending to the string a special end-of-string character which sorts lexicographically before every other character. Sorting cyclic permutations is then equivalent to sorting suffixes.
Suffix arrays are used to look up substrings in Example-Based Machine Translation, demanding much less storage than a full phrase table as used in Statistical machine translation.
Suffix arrays were originally developed by Gene Myers and Udi Manber to reduce memory consumption compared to a suffix tree. This began the trend towards compressed suffix arrays and BWT-based compressed full-text indices.