Suffix array

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 \mathcal{O}(n) time suffix array construction algorithm that is optimal both in time and space, where in-place means that the algorithm only needs \mathcal{O}(1) 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. A sorted array of only some (rather than all) suffixes of a string is called a sparse suffix array.

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 \mathcal{O}(n) time suffix array construction algorithm that is optimal both in time and space, where in-place means that the algorithm only needs \mathcal{O}(1) 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. A sorted array of only some (rather than all) suffixes of a string is called a sparse suffix array. Let S=S[1]S[2]...S[n] be an n -string and let S[i,j] denote the substring of S ranging from i to j inclusive. The suffix array A of S is now defined to be an array of integers providing the starting positions of suffixes of S in lexicographical order. This means, an entry A[i] contains the starting position of the i -th smallest suffix in S and thus for all 1 \leq i \leq n : S[A[i-1],n] . Each suffix of S shows up in 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 A . Consider the text S = 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 A contains the starting positions of these sorted suffixes: The suffix array with the suffixes written out vertically underneath for clarity: So for example, A[3] contains the value 4, and therefore refers to the suffix starting at position 4 within S , which is the suffix ana$ . For a human genome with \sigma = 4 and n = 3.4 \times 10^9 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. 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, S=S_1,S_2,S_3,...,S_k and is lexicographically sorted with all suffixes of each string. n = len(S) def search(P: str) -> tuple[int, int]: """ Return indices (s, r) such that the interval A[s:r] (excluding 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 suffixAt(A[mid]): l = mid + 1 else: r = mid s = l # Find ending position of interval r = n while l Finding the substring pattern P of length m in the string S of length n takes \mathcal{O}(m \log n) time, given that a single suffix comparison needs to compare m characters. describe how this bound can be improved to \mathcal{O}(m + \log n) 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 \mathcal{O}(m) 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: BWT[i] = S[A[i]-1] . 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. ==External links== 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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1343994068 under CC BY-SA 4.0; modifications have been made.