In particular, for a text of n symbols from alphabet e, we develop a data structure called the compressed suffix array that uses just nHh + O(n(log lg n) / log|(| n) bits while retaining full text indexing functionality, such as searching for patterns in time linear in the pattern length plus a polylogarithmic term in n. The term Hh ( log2 |(| denotes the hth-order empirical entropy of the text, which means that our index is nearly optimal in space apart from lower-order terms, achieving the empirical entropy of the text (with multiplicative constant 1). Our approach is also self-indexing, which means that the original text can be discarded and recovered in a random access manner from the index itself.
This work was done jointly with Ankur Gupta and Roberto Grossi.