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 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.
Definition
Let be an -string and let denote the substring of ranging from to inclusive.
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 .
Example
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 ana$.
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.
Space efficiency
Suffix arrays were introduced by 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.
Construction algorithms
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 .