Breaking the 𝒪(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees

The suffix array, describing the lexicographical order of suffixes of a given text, and the suffix tree, a path-compressed trie of all suffixes, are the two most fundamental data structures for string processing, with plethora of applications in data compression, bioinformatics, and information retrieval. For a length-n text, however, they use Θ(n log n) bits of space, which is often too costly. To address this, Grossi and Vitter [STOC 2000] and, independently, Ferragina and Manzini [FOCS 2000] introduced space-efficient versions of the suffix array, known as the compressed suffix array (CSA) and the FM-index. Sadakane [SODA 2002] then showed how to augment them to obtain the compressed suffix tree (CST). For a length-n text over an alphabet of size σ, these structures use only O(n log σ) bits. Nowadays, these structures are part of the standard toolbox: modern textbooks spend dozens of pages describing their applications, and they almost completely replaced suffix arrays and suffix trees in space-critical applications. The biggest remaining open question is how efficiently they can be constructed. After two decades, the fastest algorithms still run in O(n) time [Hon et al., FOCS 2003], which is Θ(log σ n) factor away from the lower bound of Ω(n/ log σ n) (following from the necessity to read the input).

In this paper, we make the first in 20 years improvement in n for this problem by proposing a new compressed suffix array and a new compressed suffix tree which admit o(n)-time construction algorithms while matching the space bounds and the query times of the original CSA/CST and the FM-index. More precisely, our structures take O(n log σ) bits, support SA queries and full suffix tree functionality in O(log n) time per operation, and can be constructed in O(n min(1, log σ/ √ log n)) time using O(n log σ) bits of working space. (For example, if σ = 2, the construction time is O(n/ √ log n) = o(n).) We derive this result as a corollary from a much more general reduction: We prove that all parameters of a compressed suffix array/tree (query time, space, construction time, and construction working space) can essentially be reduced to those of a data structure answering new query types that we call prefix rank and prefix selection. Using the novel techniques, we also develop a new index for pattern matching.