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.