High-order entropy-compressed text indexes

We present a novel implementation of compressed sux arrays exhibiting new tradeos between search time and space occupancy for a given text (or sequence) of n sym-bols over an alphabet , where each symbol is encoded by lg jj bits. We show that compressed sux arrays use just nHh + O(n lg lg n = lgjj n) bits, while retaining full text in-dexing functionalities, such as searching any pattern se-quence of length m in O(m lg jj + polylog(n)) time. The term Hh lg jj 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 asymptotically the empirical entropy of the text (with a multiplicative con-stant 1). If the text is highly compressible so that Hh = o(1) and the alphabet size is small, we obtain a text index with o(m) search time that requires only o(n) bits. Further results and tradeos are reported in the paper.