FIX to Compressed Text Indexes with Fast Locate
s
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 https://arxiv.org/pdf/1705.10382.pdf.
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.