The Complexity of Dynamic LZ77 is \(\tilde \Theta(n^{2/3})\)

Society for Industrial and Applied Mathematics eBooks 2026

View at publisher
Authors: Itai Boneh, Shay Golan, Matan Kraus
DOI: 10.1137/1.9781611978971.67
Cited by: 0

Abstract

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.

Fields of Study & Subjects

Algorithms and Data Compression Genome Rearrangement Algorithms graph theory and CDMA systems

Publication details

Journal / source
Society for Industrial and Applied Mathematics eBooks
Pages
1859–1872
Publication date
1 January 2026
Language
EN