Lempel-Ziv (LZ77) Factorization in Sublinear Time

Lempel-Ziv (LZ77) factorization is a fundamental problem in string processing: Greedily partition a given string$T$from left to right into blocks (called phrases) so that each phrase is either the leftmost occurrence of a single letter or the longest prefix of the unprocessed suffix that has another occurrence earlier in the text. This simple routine has numerous applications. Most importantly, the LZ77 factorization is the central component and the computational bottleneck of most existing compression algorithms (utilized in formats like zip, pdf, and png). LZ77 is also a widely used algorithmic tool for the detection of repetitions and periodicities in strings, and the centerpiece of many powerful compressed indexes that enable computation directly over compressed data. LZ77 factorization is one of the most studied problems in string processing. In the 47 years since its inception, numerous efficient algorithms were developed for different models of computation, including parallel, GPU, external-memory, and quantum. Remarkably, however, the complexity of the most basic problem is still not settled: All existing algorithms in the RAM model run in$\Omega(n)$time, which is a$\Theta(\log n)$factor away from the lower bound of$\Omega(n/\log n)$(following simply from the necessity to read the entire input, which takes$\Theta(n/\log n)$space for any$T\in\{0,1\}^{n})$. Sublinear-time algorithms are known for nearly all other fundamental problems on strings, but LZ77 seems resistant to all currently known techniques. We present the first$o(n)$-time algorithm for constructing the LZ77 factorization, breaking the linear-time barrier present for nearly 50 years. More precisely, we show that, in the standard RAM model, it is possible to compute the LZ77 factorization of a given length-$n$string$T\in \{0,1\}^{n}$in$\mathcal{O}(n/\sqrt{\log n})=o(n)$time and using the optimal$O(n/\log n)$working space. Our algorithm generalizes to larger alphabets$\Sigma=[0.. \sigma),\text{ where }\sigma=n^{\mathcal{O}2(1)}$. The runtime and working space then become$\mathcal{O}((n\log\sigma)/\sqrt{\log n})$and$\mathcal{O}(n/\log_{\sigma}n)$, respectively. To achieve this sublinear-time LZ77 algorithm, we prove a more general result: We show that, for any constant$\epsilon\in(0,1)$and string$T\in[0..\sigma)^{n}$, in$\mathcal{O}((n\log\sigma)/\sqrt{\log n})$time and using$\mathcal{O}(n/\log_{\sigma}n)$working space, we can construct an index of optimal size$\mathcal{O}(n/\log_{\sigma}n)$that, given any substring$P=T[j.. j+\ell)$specified with a pair$(j,\ell)$, computes the leftmost occurrence of$P$in$T$in$O(\log^{\epsilon}n)$time. In other words, we solve the indexing/online variant of the LZ77 problem, where we can efficiently query the phrase length starting at any position. Our solution is based on a new type of queries that we call prefix range minimum queries or prefix RMQ. After developing an efficient solution for these queries, we provide a general reduction showing that any new tradeoff for the prefix RMQ implies a new tradeoff for an index finding leftmost occurrences (and hence a new LZ77 factorization algorithm).