high-order entropy-compressed text indexes
We present a novel implementation of compressed suffix arrays exhibiting new tradeoffs between search time and space occupancy for a given text (or sequence) of n symbols over an alphabet ?, where each symbol is encoded by lg&verbar;?&verbar; bits. We show that compressed suffix arrays use just nH h + ? bits, while retaining full text indexing functionalities, such as searching any pattern sequence of length m in O ( m lg &verbar;?&verbar; + polylog( n )) time. The term H h ? lg &verbar;?&verbar; 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 constant 1). If the text is highly compressible so that H n = 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 tradeoffs are reported in the paper.
text indexing implementation search timing space sequence use pattern entropy optimality size paper order