Lempel-Ziv (LZ77) Factorization in Sublinear Time

Abstract

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 letter or the longest prefix of the unprocessed suffix that has another occurrence earlier in $T$. Due to numerous applications, LZ77 factorization is one of the most studied problems on strings. In the 47 years since its inception, several algorithms were developed for different models of computation, including parallel, GPU, external-memory, and quantum. Remarkably, however, the complexity of the most basic variant 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 from the necessity to read the input, which takes $\Theta (n/\log n)$ space for $T\in \{0,1{\}}^n$). We present the first $o(n)$-time algorithm for LZ77 factorization, breaking the linear-time barrier present for nearly 50 years. For $T\in \{0,1{\}}^n$, our algorithm runs in $\mathcal{O}(n/\sqrt{\log n})=o(n)$ time and uses the optimal $\mathcal{O}(n/\log n)$ working space. Our algorithm generalizes to $\Sigma =[\mathrm{0..}\sigma )$, where $\sigma =n^{\mathcal{O}(1)}$. The runtime and working space then become $\mathcal{O}((n\log \sigma )/\sqrt{\log n})$ and $\mathcal{O}(n/{\log }_{\sigma }n)$. To obtain our algorithm, we prove a more general result: For any constant $\epsilon \in (0,1)$ and $T\in [\mathrm{0..}\sigma {)}^n$, in $\mathcal{O}((n\log \sigma )/\sqrt{\log n})$ time and using $\mathcal{O}(n/{\log }_{\sigma }n)$ space, we can construct an $\mathcal{O}(n/{\log }_{\sigma }n)$-size index that, given any $P=T[j..j+\ell )$ (represented as $(j,\ell )$), computes the leftmost occurrence of $P$ in $T$ in $\mathcal{O}({\log }^{\epsilon }n)$ time. In other words, we solve the indexing/online variant of the LZ77 problem.

arXiv commentAccepted to FOCS 2024

References in corpus (7)

• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing
• Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
• Optimal Construction of Compressed Indexes for Highly Repetitive Texts
• Near-Optimal Search Time in $\delta$-Optimal Space, and Vice Versa
• Grammar Compressed Sequences with Rank/Select Support
• Lempel-Ziv (LZ77) Factorization in Sublinear Time

Cited by in corpus (2)

• Lempel-Ziv (LZ77) Factorization in Sublinear Time
• On the Hardness Hierarchy for the $O(n\sqrt{\log n})$ Complexity in the Word RAM