Lempel-Ziv (LZ77) Factorization in Sublinear Time

Lempel-Ziv (LZ77) factorization is a fundamental problem in string processing: Greedily partition a given string <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(n)$</tex> time, which is a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Theta(\log n)$</tex> factor away from the lower bound of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(n/\log n)$</tex> (following simply from the necessity to read the entire input, which takes <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Theta(n/\log n)$</tex> space for any <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T\in\{0,1\}^{n})$</tex>. 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$o(n)$</tex> -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-<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> string <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T\in \{0,1\}^{n}$</tex> in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(n/\sqrt{\log n})=o(n)$</tex> time and using the optimal <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(n/\log n)$</tex> working space. Our algorithm generalizes to larger alphabets <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma=[0.. \sigma),\text{ where }\sigma=n^{\mathcal{O}2(1)}$</tex>. The runtime and working space then become <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}((n\log\sigma)/\sqrt{\log n})$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(n/\log_{\sigma}n)$</tex>, respectively. To achieve this sublinear-time LZ77 algorithm, we prove a more general result: We show that, for any constant <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\epsilon\in(0,1)$</tex> and string <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T\in[0..\sigma)^{n}$</tex>, in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}((n\log\sigma)/\sqrt{\log n})$</tex> time and using <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(n/\log_{\sigma}n)$</tex> working space, we can construct an index of optimal size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(n/\log_{\sigma}n)$</tex> that, given any substring <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P=T[j.. j+\ell)$</tex> specified with a pair <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(j,\ell)$</tex>, computes the leftmost occurrence of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P$</tex> in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex> in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log^{\epsilon}n)$</tex> 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).