- Free Articles
- Suffix Tree Construction in Hierarchical Memory Encyclopedia of Algorithms
- Probabilistic Data Forwarding in Wireless Sensor Networks Encyclopedia of Algorithms
- Renaming Encyclopedia of Algorithms
- Time in Philosophical Logic Encyclopedia of Database Systems
- Indoor Localization Encyclopedia of GIS
- More Free Articles
Suffix Array Construction
Keywords and Synonyms
Suffix sorting; Full-text index construction
The suffix array [5,14] is the lexicographically sorted array of all the suffixes of a string. It is a popular text index structure with many applications. The subject of this entry are algorithms that construct the suffix array.
More precisely, the input to a suffix array construction algorithm is a text string T = T[0,n) = t0t1⋅⋅⋅tn − 1, i. e., a sequence of n characters from an alphabet Σ. For i∈[0,n], let S i denote the suffix T[i,n) = titi + 1⋅⋅⋅tn − 1. The output is the suffix array SA[0,n] of T, a permutation of [0,n] satisfying SSA < SSA < ⋅⋅⋅ < SSA[n], where < denotes the lexicographic order of strings.
Two specific models for the alphabet Σ are considered. An ordered alphabet is an arbitrary ordered set with constant time character comparisons. An integer alphabet is the integer range [1,n]. There is also a result that holds for any alphabet.