Near-Optimal Search Time in δ-Optimal Space
Tomasz Kociumaka, Gonzalo Navarro, and Francisco Olivares
Two recent lower bounds on the compressiblity of repetitive sequences,
δ <= γ, have received much attention. It has been shown that
a string S[1..n] can be represented within the optimal O(δ
log(n/δ)) space, and further, that within that space one can find all
the occ occurrences in S of any pattern of length m in
time O(m log n + occ log^ε n) for any constant ε>0.
Instead, the near-optimal search time O(m + (occ+1) log^ε n) was
achieved only within O(γ log(n/γ)) space. Both results are
based on considerably different locally consistent parsing techniques. The
question of whether the better search time could be obtained within the
δ-optimal space was open. In this paper we prove that both techniques can
indeed be combined in order to obtain the best of both worlds,
O(m + (occ+1) log^ε n)
search time within O(δ log(n/δ)) space.