FIX to Compressed Text Indexes with Fast Locate


Level: Serious

The analytical results claiming O(H_k log(1/H_k)n log n) bits for the locating structure, are not properly proved and most likely are incorrect; see Appendix A in An alternative grammar compressor achieving this space is given in that arxiv paper.

In practice RePair compresses much better than the variant that offers a guarantee, and the value of the paper is mostly practical.