| Average | Worst case |
|---|
| Space | 𝒪(n) | 𝒪(n) time suffix array construction algorithm that is optimal both in time and space, where in-place means that the algorithm only needs S=S[1]S[2]...S[n] be an S ranging from A of A[i] contains the starting position of the 1≤i≤n: A exactly once. Suffixes are simple strings. These strings are sorted (as in a paper dictionary), before their starting positions (integer indices) are saved in i
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|
| scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>i = |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
| scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>2 |
| $ | n | n | a | a | a |
| scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>3 |
| | a | a | n | $ | n |
| scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>4 |
| | $ | n | a | | a |
| scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>5 |
| | | a | n | | $ |
| scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>6 |
| | | $ | a | | |
| scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>7 |
| | | | $ | | |
So for example, 4n bytes in total. This is significantly less than the σ only requires n=3.4×109 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.
Construction algorithmseditA suffix tree can be built in 𝒪(n).
A naive approach to construct a suffix array is to use a comparison-based sorting algorithm. These algorithms require 𝒪(n2logn).
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 𝒪(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 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. In 2021 a faster implementation of the algorithm was presented by Ilya Grebnov which in average showed 65% performance improvement over DivSufSort implementation on the Silesia corpus.
Generalized suffix arrayeditThe concept of a suffix array can be extended to more than one string. This is called a generalized suffix array (or GSA), a suffix array that contains all suffixes for a set of strings (for example, S. 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:
P of length n takes 𝒪(m+logn) 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) improve the bound even further and achieve a search time of m in an enhanced suffix array is 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.
- ↑ Grebnov, Ilya (2021-09-22), libsais, retrieved 2021-10-02
- ↑ Shi 1996.
- 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. Vol. 11147. Springer. pp. 268–284. arXiv:1610.08305. doi:10.1007/978-3-030-00479-8_22. ISBN 978-3-030-00478-1.
- 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.
- 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. S2CID 2653529.
- 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.
- Kärkkäinen, Juha; Sanders, Peter (2003). Simple Linear Work Suffix Array Construction. Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 2719. doi:10.1007/3-540-45061-0_73. ISBN 978-3-540-40493-4.
-
|