FIX to Stronger Lempel-Ziv Based Compressed Text Indexing

Level: Small

Lemma 1 [28] actually states that n log n <= u Hk + ..., not the equality. We use the equality along the paper as an upper bound.

Level: Medium

Section 5 probably does not work (fortunately it is just a different way to obtain what we already have earlier in the paper). The problem is that we sample regularly the tree preorders, and then advance on a DFS traversal to find the next sampled preorder. Such DFS traversal, however, does not ensure that we work O(1) to get the next preorder. For example, if we are in the rightmost leaf of a subtree with a long rightmost path, we have to work a lot to reach the next sibling of the subtree root.

Nicola Prezza, in his SODA 2021 paper "On Locating Paths in Compressed Tries", Lemma 2 (proof in the Appendix), provides a more complex construction that works.