Dynamic index and LZ factorization in compressed space

Abstract

In this paper, we propose a new \emph{dynamic compressed index} of $O(w)$ space for a dynamic text $T$, where $w=O(\min (z\log N{\log }^{\ast }M,N))$ is the size of the signature encoding of $T$, $z$ is the size of the Lempel-Ziv77 (LZ77) factorization of $T$, $N$ is the length of $T$, and $M\ge 3N$ is an integer that can be handled in constant time under word RAM model. Our index supports searching for a pattern $P$ in $T$ in $O(|P|f_{\mathcal{A}}+\log w\log |P|{\log }^{\ast }M(\log N+\log |P|{\log }^{\ast }M)+occ\log N)$ time and insertion/deletion of a substring of length $y$ in $O((y+\log N{\log }^{\ast }M)\log w\log N{\log }^{\ast }M)$ time, where $f_{\mathcal{A}}=O(\min \{\frac{\log \log M\log \log w}{\log \log \log M},\sqrt{\frac{\log w}{\log \log w}}\})$. Also, we propose a new space-efficient LZ77 factorization algorithm for a given text of length $N$, which runs in $O(N{f}_{\mathcal{A}}+z\log w{\log }^{3}N({\log }^{\ast }N{)}^2)$ time with $O(w)$ working space.

arXiv admin note: substantial text overlap with arXiv:1605.01488; text overlap with arXiv:1504.06954