FIX to Faster Entropy-Bounded Compressed Suffix Trees

Level: Small

There is an error in Sec. 7, page 14. t_psi is not O(1) for the GCSA variant we use there (i.e., with o(n) extra space); it is t_psi = O(log sigma). This does not affect Table 1 because sigma = O(1) is assumed in there, nor the complexities of our suffix tree because they depend only on t_SA. Thanks to Kunihiko Sadakane for pointing out this.

It should also be noticed that we have put two identical lines in Table 1. One should have been for SLink and the other for LCA. The complexities are identical.

In Sect. 8.1 it is said that RePair compresses the differential SA and LCP arrays to O(R log(n/R) log n) bits. This is inherited from previous publications, where it is not properly proved, and most likely to be 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.