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.[1]
The suffix array for a subset of all suffixes of a string is called sparse suffix array.[2] Multiple probabilistic algorithms have been developed to minimize the additional memory usage including an optimal time and memory algorithm.[3]
In computer science, a suffixarray is a sorted array of all suffixes of a string. It is a data structure used in, among others, full-text indices, data-compression...
computer science, a compressed suffixarray is a compressed data structure for pattern matching. Compressed suffixarrays are a general class of data structure...
computer science, the longest common prefix array (LCP array) is an auxiliary data structure to the suffixarray. It stores the lengths of the longest common...
In computer science, a generalized suffixarray (GSA) is a suffixarray containing all suffixes for a set of strings. Given the set of strings S = S 1...
algorithms for constructing both suffix trees and suffixarrays, for example, in external memory, compressed, succinct, etc. The suffix tree for the string S {\displaystyle...
time with a generalized suffix tree. The longest common substrings of a set of strings can be found by building a generalized suffix tree for the strings...
alternative to building a generalized suffix tree is to concatenate the strings, and build a regular suffix tree or suffixarray for the resulting string. When...
string algorithms. The suffixarray is a simplified version of this data structure that lists the start positions of the suffixes in alphabetically sorted...
the LCP of the suffixes that start at indexes i and j in T. To do this we first compute the suffixarray A, and the inverse suffixarray A−1. We then compute...
Structured analysis, a software engineering technique Suffixarray, a sorted array of all suffixes of a string System administrator System architecture...
In computer science, a suffix automaton is an efficient data structure for representing the substring index of a given string which allows the storage...
Important examples of compressed data structures include the compressed suffixarray and the FM-index, both of which can represent an arbitrary text of characters...
Smith–Waterman algorithm Data structure DAFSA SuffixarraySuffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie Other Parsing...
Substring indexes include: Suffix tree Suffixarray N-gram index, an inverted file for all N-grams of the text Compressed suffixarray FM-index LZ-index R....
Smith–Waterman algorithm Data structure DAFSA SuffixarraySuffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie Other Parsing...
Lossy Audio Image Video Theory Compressed data structures Compressed suffixarray FM-index Entropy Information theory Timeline Kolmogorov complexity Prefix...
Smith–Waterman algorithm Data structure DAFSA SuffixarraySuffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie Other Parsing...
Award software award in 1999. Together with Gene Myers he developed the suffixarray, a data structure for string matching. He was a professor at the University...
changing sprited images. Discontinued projects: jSuffixArrays: Several Java implementations of the SuffixArray data structure with different performance and...
Smith–Waterman algorithm Data structure DAFSA SuffixarraySuffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie Other Parsing...
Global Information
