Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.12000 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917043677167616 |
|---|---|
| author | Boneh, Itai Golan, Shay Kraus, Matan |
| author_facet | Boneh, Itai Golan, Shay Kraus, Matan |
| contents | The Lempel-Ziv 77 (LZ77) factorization is a fundamental compression scheme widely used in text processing and data compression. In this work, we investigate the time complexity of maintaining the LZ77 factorization of a dynamic string. By establishing matching upper and lower bounds, we fully characterize the complexity of this problem.
We present an algorithm that efficiently maintains the LZ77 factorization of a string $S$ undergoing edit operations, including character substitutions, insertions, and deletions. Our data structure can be constructed in $\tilde{O}(n)$ time for an initial string of length $n$ and supports updates in $\tilde{O}(n^{2/3})$ time, where $n$ is the current length of $S$. Additionally, we prove that no algorithm can achieve an update time of $O(n^{2/3-\varepsilon})$ unless the Strong Exponential Time Hypothesis fails. This lower bound holds even in the restricted setting where only substitutions are allowed and only the length of the LZ77 factorization is maintained. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_12000 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$ Boneh, Itai Golan, Shay Kraus, Matan Data Structures and Algorithms The Lempel-Ziv 77 (LZ77) factorization is a fundamental compression scheme widely used in text processing and data compression. In this work, we investigate the time complexity of maintaining the LZ77 factorization of a dynamic string. By establishing matching upper and lower bounds, we fully characterize the complexity of this problem. We present an algorithm that efficiently maintains the LZ77 factorization of a string $S$ undergoing edit operations, including character substitutions, insertions, and deletions. Our data structure can be constructed in $\tilde{O}(n)$ time for an initial string of length $n$ and supports updates in $\tilde{O}(n^{2/3})$ time, where $n$ is the current length of $S$. Additionally, we prove that no algorithm can achieve an update time of $O(n^{2/3-\varepsilon})$ unless the Strong Exponential Time Hypothesis fails. This lower bound holds even in the restricted setting where only substitutions are allowed and only the length of the LZ77 factorization is maintained. |
| title | The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$ |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.12000 |