Suffix Array Construction

Keywords and Synonyms

Suffix sorting; Full-text index construction

Problem Definition

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) = t₀t₁⋅⋅⋅t_{n − 1}, i. e., a sequence of n characters from an alphabet Σ. For i∈[0,n], let S _i denote the suffix T[i,n) = t_it_i + 1⋅⋅⋅t_{n − 1}. The output is the suffix array SA[0,n] of T, a permutation of [0,n] satisfying S_SA[0] < S_SA[1] < ⋅⋅⋅ < S_SA[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.

Many