|Invented by||Manber & Myers (1990)|
in big O notation
In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used in, among others, full text indices, data compression algorithms, and the field of bibliometrics.
Suffix arrays were introduced by Manber & Myers (1990) as a simple, space efficient alternative to suffix trees. They had independently been discovered by Gaston Gonnet in 1987 under the name PAT array (Gonnet, Baeza-Yates & Snider 1992).
Li, Li & Huo (2016) gave the first in-place time suffix array construction algorithm that is optimal both in time and space, where in-place means that the algorithm only needs additional space beyond the input string and the output suffix array.
Enhanced suffix arrays (ESAs) are suffix arrays with additional tables that reproduce the full functionality of suffix trees preserving the same time and memory complexity. The suffix array for a subset of all suffixes of a string is called sparse suffix array. Multiple probabilistic algorithms have been developed to minimize the additional memory usage including an optimal time and memory algorithm.
Let be an -string and let denote the substring of ranging from to .
The suffix array of is now defined to be an array of integers providing the starting positions of suffixes of in lexicographical order. This means, an entry contains the starting position of the -th smallest suffix in and thus for all : .
Each suffix of shows up in exactly once. Suffixes are simple strings. These strings are sorted (as in a paper dictionary), before their starting positions (integer indices) are saved in .
Consider the text =
banana$ to be indexed:
The text ends with the special sentinel letter
$ that is unique and lexicographically smaller than any other character. The text has the following suffixes:
These suffixes can be sorted in ascending order:
The suffix array contains the starting positions of these sorted suffixes:
The suffix array with the suffixes written out vertically underneath for clarity:
So for example, contains the value 4, and therefore refers to the suffix starting at position 4 within , which is the suffix
Correspondence to suffix trees
Suffix arrays are closely related to suffix trees:
- Suffix arrays can be constructed by performing a depth-first traversal of a suffix tree. The suffix array corresponds to the leaf-labels given in the order in which these are visited during the traversal, if edges are visited in the lexicographical order of their first character.
- A suffix tree can be constructed in linear time by using a combination of suffix array and LCP array. For a description of the algorithm, see the corresponding section in the LCP array article.
It has been shown that every suffix tree algorithm can be systematically replaced with an algorithm that uses a suffix array enhanced with additional information (such as the LCP array) and solves the same problem in the same time complexity. Advantages of suffix arrays over suffix trees include improved space requirements, simpler linear time construction algorithms (e.g., compared to Ukkonen's algorithm) and improved cache locality.
Suffix arrays were introduced by Manber & Myers (1990) in order to improve over the space requirements of suffix trees: Suffix arrays store integers. Assuming an integer requires bytes, a suffix array requires bytes in total. This is significantly less than the bytes which are required by a careful suffix tree implementation.
However, in certain applications, the space requirements of suffix arrays may still be prohibitive. Analyzed in bits, a suffix array requires space, whereas the original text over an alphabet of size only requires bits. For a human genome with and the suffix array would therefore occupy about 16 times more memory than the genome itself.
Such discrepancies motivated a trend towards compressed suffix arrays and BWT-based compressed full-text indices such as the FM-index. These data structures require only space within the size of the text or even less.
A suffix tree can be built in and can be converted into a suffix array by traversing the tree depth-first also in , so there exist algorithms that can build a suffix array in .
A naive approach to construct a suffix array is to use a comparison-based sorting algorithm. These algorithms require suffix comparisons, but a suffix comparison runs in time, so the overall runtime of this approach is .
More advanced algorithms take advantage of the fact that the suffixes to be sorted are not arbitrary strings but related to each other. These algorithms strive to achieve the following goals:
- minimal asymptotic complexity
- lightweight in space, meaning little or no working memory beside the text and the suffix array itself is needed
- fast in practice
One of the first algorithms to achieve all goals is the SA-IS algorithm of Nong, Zhang & Chan (2009). The algorithm is also rather simple (< 100 LOC) and can be enhanced to simultaneously construct the LCP array. The SA-IS algorithm is one of the fastest known suffix array construction algorithms. A careful implementation by Yuta Mori outperforms most other linear or super-linear construction approaches.
Beside time and space requirements, suffix array construction algorithms are also differentiated by their supported alphabet: constant alphabets where the alphabet size is bound by a constant, integer alphabets where characters are integers in a range depending on and general alphabets where only character comparisons are allowed.
Most suffix array construction algorithms are based on one of the following approaches:
- Prefix doubling algorithms are based on a strategy of Karp, Miller & Rosenberg (1972). The idea is to find prefixes that honor the lexicographic ordering of suffixes. The assessed prefix length doubles in each iteration of the algorithm until a prefix is unique and provides the rank of the associated suffix.
- Recursive algorithms follow the approach of the suffix tree construction algorithm by Farach (1997) to recursively sort a subset of suffixes. This subset is then used to infer a suffix array of the remaining suffixes. Both of these suffix arrays are then merged to compute the final suffix array.
- Induced copying algorithms are similar to recursive algorithms in the sense that they use an already sorted subset to induce a fast sort of the remaining suffixes. The difference is that these algorithms favor iteration over recursion to sort the selected suffix subset. A survey of this diverse group of algorithms has been put together by Puglisi, Smyth & Turpin (2007).
A well-known recursive algorithm for integer alphabets is the DC3 / skew algorithm of Kärkkäinen & Sanders (2003). It runs in linear time and has successfully been used as the basis for parallel and external memory suffix array construction algorithms.
Recent work by Salson et al. (2010) 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 , 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 considering the insertion of a reasonable number of letters in the original text.
In practical open source work, a commonly used routine for suffix array construction was qsufsort, based on the 1999 Larsson-Sadakane algorithm. This routine has been superseded by Yuta Mori's DivSufSort, "the fastest known suffix sorting algorithm in main memory" as of 2017. It too can be modified to compute an LCP array. It uses a induced copying combined with Itoh-Tanaka.
The suffix array of a string can be used as an index to quickly locate every occurrence of a substring pattern within the string . Finding every occurrence of the pattern 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 two binary searches. The first search locates the starting position of the interval, and the second one determines the end position:
n = len(S) def search(P: str) -> Tuple[int, int]: """ Return indices (s, r) such that the interval A[s:r] (including the end index) represents all suffixes of S that start with the pattern P. """ # Find starting position of interval l = 0 # in Python, arrays are indexed starting at 0 r = n while l < r: mid = (l + r) // 2 # division rounding down to nearest integer # suffixAt(A[i]) is the ith smallest suffix if P > suffixAt(A[mid]): l = mid + 1 else: r = mid s = l # Find ending position of interval r = n while l < r: mid = (l + r) // 2 if suffixAt(A[mid]).startswith(P): l = mid + 1 else: r = mid return (s, r)
Finding the substring pattern of length in the string of length takes time, given that a single suffix comparison needs to compare characters. Manber & Myers (1990) describe how this bound can be improved to time using LCP information. The idea is that a pattern comparison does not need to re-compare certain characters, when it is already known that these are part of the longest common prefix of the pattern and the current search interval. Abouelhoda, Kurtz & Ohlebusch (2004) harvtxt error: multiple targets (2×): CITEREFAbouelhodaKurtzOhlebusch2004 (help) improve the bound even further and achieve a search time of as known from suffix trees.
Suffix sorting algorithms can be used to compute the Burrows–Wheeler transform (BWT). The BWT requires sorting of all cyclic permutations of a string. If this string ends in a special end-of-string character that is lexicographically smaller than all other character (i.e., $), then the order of the sorted rotated BWT matrix corresponds to the order of suffixes in a suffix array. The BWT can therefore be computed in linear time by first constructing a suffix array of the text and then deducing the BWT string: .
- Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (March 2004). "Replacing suffix trees with enhanced suffix arrays". Journal of Discrete Algorithms. 2 (1): 53–86. doi:10.1016/s1570-8667(03)00065-0. ISSN 1570-8667.
- Kärkkäinen, Juha; Ukkonen, Esko (1996), "Sparse suffix trees", Lecture Notes in Computer Science, Springer Berlin Heidelberg, pp. 219–230, doi:10.1007/3-540-61332-3_155, ISBN 9783540613329
- Gawrychowski, Paweł; Kociumaka, Tomasz (January 2017). "Sparse Suffix Tree Construction in Optimal Time and Space". Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics: 425–439. arXiv:1608.00865. doi:10.1137/1.9781611974782.27. ISBN 9781611974782.
- Abouelhoda, Kurtz & Ohlebusch 2004. sfn error: multiple targets (2×): CITEREFAbouelhodaKurtzOhlebusch2004 (help)
- Abouelhoda, Kurtz & Ohlebusch 2002.
- Kurtz 1999.
- Puglisi, Smyth & Turpin 2007.
- Fischer 2011.
- Burkhardt & Kärkkäinen 2003.
- Kulla & Sanders 2007.
- Dementiev et al. 2008.
- Larsson, N. Jesper; Sadakane, Kunihiko (22 November 2007). "Faster suffix sorting". Theoretical Computer Science. 387 (3): 258–272. doi:10.1016/j.tcs.2007.07.017. ISSN 0304-3975.
- Fischer, Johannes; Kurpicz, Florian (5 October 2017). "Dismantling DivSufSort". Proceedings of the Prague Stringology Conference 2017. arXiv:1710.01896.
- Manber, Udi; Myers, Gene (1990). Suffix arrays: a new method for on-line string searches. First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319–327.CS1 maint: ref=harv (link)
- Manber, Udi; Myers, Gene (1993). "Suffix arrays: a new method for on-line string searches". SIAM Journal on Computing. 22 (5): 935–948. doi:10.1137/0222058.CS1 maint: ref=harv (link)
- Li, Zhize; Li, Jian; Huo, Hongwei (2016). Optimal In-Place Suffix Sorting. Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE). Lecture Notes in Computer Science. 11147. Springer. pp. 268–284. arXiv:1610.08305. doi:10.1007/978-3-030-00479-8_22. ISBN 978-3-030-00478-1.CS1 maint: ref=harv (link)
- Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). "Replacing suffix trees with enhanced suffix arrays". Journal of Discrete Algorithms. 2 (1): 53–86. doi:10.1016/S1570-8667(03)00065-0.CS1 maint: ref=harv (link)
- Gonnet, G.H; Baeza-Yates, R.A; Snider, T (1992). "New indices for text: PAT trees and PAT arrays". Information Retrieval: Data Structures and Algorithms.CS1 maint: ref=harv (link)
- Kurtz, S (1999). "Reducing the space requirement of suffix trees". Software-Practice and Experience. 29 (13): 1149–1171. doi:10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O. hdl:10338.dmlcz/135448.CS1 maint: ref=harv (link)
- Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). The Enhanced Suffix Array and Its Applications to Genome Analysis. Algorithms in Bioinformatics. Lecture Notes in Computer Science. 2452. p. 449. doi:10.1007/3-540-45784-4_35. ISBN 978-3-540-44211-0.CS1 maint: ref=harv (link)
- Puglisi, Simon J.; Smyth, W. F.; Turpin, Andrew H. (2007). "A taxonomy of suffix array construction algorithms". ACM Computing Surveys. 39 (2): 4. doi:10.1145/1242471.1242472.CS1 maint: ref=harv (link)
- Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Linear Suffix Array Construction by Almost Pure Induced-Sorting. 2009 Data Compression Conference. p. 193. doi:10.1109/DCC.2009.42. ISBN 978-0-7695-3592-0.CS1 maint: ref=harv (link)
- Fischer, Johannes (2011). Inducing the LCP-Array. Algorithms and Data Structures. Lecture Notes in Computer Science. 6844. p. 374. arXiv:1101.3448. doi:10.1007/978-3-642-22300-6_32. ISBN 978-3-642-22299-3.CS1 maint: ref=harv (link)
- Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). "Dynamic extended suffix arrays". Journal of Discrete Algorithms. 8 (2): 241. doi:10.1016/j.jda.2009.02.007.CS1 maint: ref=harv (link)
- Burkhardt, Stefan; Kärkkäinen, Juha (2003). Fast Lightweight Suffix Array Construction and Checking. Combinatorial Pattern Matching. Lecture Notes in Computer Science. 2676. p. 55. doi:10.1007/3-540-44888-8_5. ISBN 978-3-540-40311-1.CS1 maint: ref=harv (link)
- Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972). Rapid identification of repeated patterns in strings, trees and arrays. Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. p. 125. doi:10.1145/800152.804905.CS1 maint: ref=harv (link)
- Farach, M. (1997). Optimal suffix tree construction with large alphabets. Proceedings 38th Annual Symposium on Foundations of Computer Science. p. 137. doi:10.1109/SFCS.1997.646102. ISBN 0-8186-8197-7.CS1 maint: ref=harv (link)
- Kärkkäinen, Juha; Sanders, Peter (2003). Simple Linear Work Suffix Array Construction. Automata, Languages and Programming. Lecture Notes in Computer Science. 2719. p. 943. doi:10.1007/3-540-45061-0_73. ISBN 978-3-540-40493-4.CS1 maint: ref=harv (link)
- Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). "Better external memory suffix array construction". Journal of Experimental Algorithmics. 12: 1. doi:10.1145/1227161.1402296.CS1 maint: ref=harv (link)
- Kulla, Fabian; Sanders, Peter (2007). "Scalable parallel suffix array construction". Parallel Computing. 33 (9): 605. doi:10.1016/j.parco.2007.06.004.CS1 maint: ref=harv (link)
|Wikimedia Commons has media related to Suffix array.|
- Suffix Array in Java
- Suffix sorting module for BWT in C code
- Suffix Array Implementation in Ruby
- Suffix array library and tools
- Project containing various Suffix Array c/c++ Implementations with a unified interface
- A fast, lightweight, and robust C API library to construct the suffix array
- Suffix Array implementation in Python
- Linear Time Suffix Array implementation in C using suffix tree