Near-Optimal Search Time in $\delta$-Optimal Space

Abstract

Two recent lower bounds on the compressiblity of repetitive sequences, $\delta \le \gamma$, have received much attention. It has been shown that a string S[1..n] can be represented within the optimal $O(\delta \log \tfrac{n}{\delta })$ 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 ^\epsilon n)$ for any constant $\epsilon >0$. Instead, the near-optimal search time $O(m+({occ+1})\log ^\epsilon n)$ was achieved only within $O(\gamma \log \frac{n}{\gamma })$ 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 $\delta$-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 ^\epsilon n)$ search time within $O(\delta \log \tfrac{n}{\delta })$ space.

Funded in part by Basal Funds FB0001, Fondecyt Grant 1-200038 and a Conicyt Doctoral Scholarship, ANID, Chile.