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. The problem can probably be fixed by regularly sampling not the preorders but the Euler Tour of the tree, which names every node twice. Each step of the DFS traversal advances one position on the Euler Tour.