FIX to Locally Compressed Suffix Arrays


Level: Serious

The analytical results of the paper, claiming O(rho log(n/rho)) space for the LCSA, 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.