Suffix array

In computer science, a suffix array is an array giving the suffixes of a string in lexicographical order.

Details

Consider the string "abracadabra", of length 11. It has eleven suffixes: "abracadabra", "bracadabra", "racadabra", and so on down to "a". Sorted into lexicographical order, these suffixes are

a
abra
abracadabra
acadabra
adabra
bra
bracadabra
cadabra
dabra
ra
racadabra

If the original string is available, each suffix can be completely specified by the zero-based or one-based index of its first character. The suffix array is the array of these indices in lexicographical order. For the string "abracadabra", using one-based indexing, the suffix array is {11,8,1,4,6,9,2,5,7,10,3}, because the suffix "a" begins at the 11th character, "abra" begins at the 8th character, and so forth.

One may also treat the string "abracadabra" as having a twelfth suffix, the empty string (with index 12). But since the empty string will always sort lexicographically before every other suffix, we lose no information by omitting it.

Algorithms

The easiest way to construct a suffix array is to use an efficient comparison sort algorithm. This requires ${\displaystyle O(n\log n)}$  suffix comparisons, but a suffix comparison requires ${\displaystyle O(n)}$  time, so the overall runtime of this approach is ${\displaystyle O(n^{2}\log n)}$ . More sophisticated algorithms improve this to ${\displaystyle O(n\log n)}$  by exploiting the results of partial sorts to avoid redundant comparisons. Several ${\displaystyle \Theta (n)}$  algorithms are known, but are rarely used in practice because of complexity, high memory requirements, and inefficiency (high constant factors).

Applications

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 ${\displaystyle O(m\log n)}$  time, where ${\displaystyle m}$  is the length of the substring.

To avoid redoing comparisons, it is possible to perform up to ${\displaystyle 2m}$  binary searches on progressively narrower ranges, obtaining ${\displaystyle O(m+\log n)}$  worst-case time. Each pair of binary searches restricts the range to suffixes that match one more character of the requested substring. When searching for abracad, for example, the following steps would be followed:

• Find the first suffix starting with a (which is a itself)
• Find the last suffix starting with a (adabra)
• Find the first suffix lying between a and adabra whose second character is b (abra)
• Find the last suffix lying between a and adabra whose second character is b (abracadabra)
• Find the first suffix lying between abra and abracadabra whose third character is r
• Find the last suffix lying between abra and abracadabra whose third character is r
• Keep doing the same until the range restricts to a single suffix (in this case at abrac)
• Check the remaining characters of the suffix (adabra) match the remaining characters of the requested string (ad)

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.

History

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.

References

• Udi Manber and Gene Myers (1991). "Suffix arrays: a new method for on-line string searches". SIAM Journal on Computing, Volume 22, Issue 5 (October 1993), pp. 935-948.
• Pang Ko and Srinivas Aluru (2003). "Space efficient linear time construction of suffix arrays." In Combinatorial Pattern Matching (CPM 03). LNCS 2676, Springer, 2003, pp 203-210.
• Juha Kärkkäinen and Peter Sanders (2003). "Simple linear work suffix array construction." In Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP '03). LNCS 2719, Springer, 2003, pp. 943-955.
• Klaus-Bernd Schürmann and Jens Stoye (2005). "An incomplex algorithm for fast suffix array construction". In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments and the 2nd Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO 2005), 2005, pp. 77-85.