Data structure for a string
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 as a simple, space efficient alternative to suffix trees. They had independently been discovered by Gaston Gonnet in 1987 under the name "PAT array" .
 gave the first in-place formula_1 time suffix array construction algorithm that is optimal both in time and space, where "in-place" means that the algorithm only needs formula_2 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.
Definition.
Let formula_3 be an formula_4-string and let formula_5 denote the substring of formula_6 ranging from formula_7 to formula_8 inclusive.
The suffix array formula_9 of formula_6 is now defined to be an array of integers providing the starting positions of suffixes of formula_6 in lexicographical order. This means, an entry formula_12 contains the starting position of the formula_7-th smallest suffix in formula_6 and thus for all formula_15: formula_16.
Each suffix of formula_6 shows up in formula_9 exactly once. Suffixes are simple strings. These strings are sorted (as in a paper dictionary), before their starting positions (integer indices) are saved in formula_9.
Example.
Consider the text formula_6=codice_1 to be indexed:
The text ends with the special sentinel letter codice_2 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 formula_9 contains the starting positions of these sorted suffixes:
The suffix array with the suffixes written out vertically underneath for clarity:
So for example, formula_22 contains the value 4, and therefore refers to the suffix starting at position 4 within formula_6, which is the suffix codice_3.
Correspondence to suffix trees.
Suffix arrays are closely related to suffix trees:
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.
Space efficiency.
Suffix arrays were introduced by in order to improve over the space requirements of suffix trees: Suffix arrays store formula_24 integers. Assuming an integer requires formula_25 bytes, a suffix array requires formula_26 bytes in total. This is significantly less than the formula_27 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 formula_28 space, whereas the original text over an alphabet of size formula_29 only requires formula_30 bits.
For a human genome with formula_31 and formula_32 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 algorithms.
A suffix tree can be built in formula_1 and can be converted into a suffix array by traversing the tree depth-first also in formula_1, so there exist algorithms that can build a suffix array in formula_1.
A naive approach to construct a suffix array is to use a comparison-based sorting algorithm. These algorithms require formula_28 suffix comparisons, but a suffix comparison runs in formula_1 time, so the overall runtime of this approach is formula_38.
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:
One of the first algorithms to achieve all goals is the SA-IS algorithm of . 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 formula_24 and "general alphabets" where only character comparisons are allowed.
Most suffix array construction algorithms are based on one of the following approaches:
A well-known recursive algorithm for integer alphabets is the "DC3 / skew" algorithm of . 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 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 formula_28, 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 Silesia Corpus.
Generalized suffix array.
The 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, formula_42 and is lexicographically sorted with all suffixes of each string.
Applications.
The suffix array of a string can be used as an index to quickly locate every occurrence of a substring pattern formula_43 within the string formula_6. 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 formula_43 of length formula_46 in the string formula_6 of length formula_24 takes formula_49 time, given that a single suffix comparison needs to compare formula_46 characters. describe how this bound can be improved to formula_51 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. improve the bound even further and achieve a search time of formula_52 for constant alphabet size, 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: formula_53.
Suffix arrays can also be 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.
Many additional applications of the suffix array require the LCP array. Some of these are detailed in the application section of the latter.
Enhanced suffix arrays.
Suffix trees are powerful data structures that have wide application in areas of pattern and string matching, indexing and textual statistics. However, it occupies a significant amount of space and thus has a drawback in many real-time applications that require processing a considerably large amount of data like genome analysis. To overcome this drawback, Enhanced Suffix Arrays were developed that are data structures consisting of suffix arrays and an additional table called the child table that contains the information about the parent-child relationship between the nodes in the suffix tree. The node branching data structure for this tree is a linked list. Enhanced suffix arrays are superior in terms of both space efficiency and time complexity and are easy to implement. Moreover, they can be applied to any algorithm that uses a suffix tree by using an abstract concept lcp-interval trees. The time complexity for searching a pattern in an enhanced suffix array is O(m|Σ|).
The suffix array of the string is an array of n integers in the range of 0 to n that represents the n+1 suffixes of the string including the special character #.
The suffix array is composed of two arrays:
Constructing the lcp-interval.
For a suffix array of S, the lcp-interval associated with the corresponding node of suffix tree of S can be defined as:
"Interval [i..j], 0 ≤ i ≤ j ≤ n is an lcp-interval of lcp-value, if"
"1. lcptab[i] ; l,"
"2. lcptab[k] ≥ l for all i + 1 ≤ k ≤ j,"
"3. lcptab[k] = l for some i + 1 ≤ k ≤ j if i ≠ j and l = n − i + 1 if i = j," 
"4. lcptab[j + 1] ; l."
The length of the longest common prefix of pos[i − 1] and pos[i] is stored in lcp[i],where 2 ≤ i ≤ n. The lcp-interval portrays the same parent-child relationship as that among the associated nodes in the suffix tree of S.This shows that if the corresponding node of [i..j] is a child of the corresponding node of [k..l], a lcp-interval [i..j] is a child interval of another lcp-interval [k..l]. If [k..l] is a child interval of [i..j], a lcp-interval [i..j] is the parent interval of a lcp-interval [k..l].
Constructing a child table.
The child table "cldtab" is composed of three n arrays, "up", "down" and "nextlIndex". The information about the edges of the corresponding suffix tree is stored and maintained by the "up" and "down" arrays. The "nextlIndex" array stores the links in the linked list used for node branching the suffix tree.
The "up", "down" and "nextlIndex" array are defined as follows:
By performing a bottom-up traversal of the lcp-interval of the tree, the child table can be constructed in linear time. The "up/down" values and the "nextlIndex" values can be computed separately by using two distinct algorithms.
Constructing a suffix link table.
The suffix links for an enhanced suffix array can be computed by generating the suffix link interval ["1..,r"] for each [i..j] interval during the preprocessing. The left and right elements l and r of the interval are maintained in the first index of [i..,j]. The table for this interval ranges from 0 to n. The suffix link table is constructed by the left-to-right breadth-first traversal of the lcp-interval tree. Every time an "l"-interval is computed, it is added to the list of l-intervals, which is referred to as the l-list. When the lcp-value ; 0, for every "l"-interval[i..,j] in the list, link[i] is