Faster Attractor-Based Indexes.
Gonzalo Navarro, Nicola Prezza · arXiv (Cornell University) · 2018
String attractors are a novel combinatorial object encompassing most known compressibility measures for highly-repetitive texts. Recently, the first index building on an attractor of size $\gamma$ of a text $T[1..n]$ was obtained. It uses $O(\gamma\log(n/\gamma))$ space and finds the $occ$ occurrences of a pattern $P[1..m]$ in time $O(m\log n + occ \log^\epsilon n)$ for any constant $\epsilon>0$. We now show how to reduce the search time to $O(m + (occ+1) \log^\epsilon n)$ within the same space, and ultimately obtain the optimal $O(m + occ)$ time within $O(\gamma\log(n/\gamma)\log n)$ space. Further, we show how to count the number of occurrences of $P$ in time $O(m+\log^{3+\epsilon} n)$ within $O(\gamma\log(n/\gamma))$ space, or the optimal $O(m)$ time within $O(\gamma\log(n/\gamma)\log n)$ space. These turn out to be the first optimal-time indexes within grammar- and Lempel-Ziv-bounded space. As a byproduct of independent interest, we show how to build, in $O(n\log n)$ expected time and without knowing the size $\gamma$ of the smallest attractor, a run-length context-free grammar of size $O(\gamma\log(n/\gamma))$ generating (only) $T$.