ATTENTION: 10:45
Guillaume Lagarde (LaBRI)
Title: Analyzing and Leveraging the k-Sensitivity of LZ77
Abstract:
We study the sensitivity of the Lempel-Ziv 77 compression algorithm to edits, showing how modifying a string can deteriorate or improve its compression. Our first result is a tight upper bound for k edits: ∀w'∈B(w,k), we have C_{LZ77}(w') ≤ 3 C_{LZ77}(w) + 4k. This result contrasts with Lempel-Ziv 78, where a single edit can significantly deteriorate compressibility, a phenomenon known as a « one-bit catastrophe ».
We further refine this bound, focusing on the coefficient 3 in front of C_{LZ77}(w), and establish a surprising trichotomy based on the compressibility of w. More precisely we prove the following bounds:
· if C_{LZ77}(w) ≲ k^{3/2} √n, the compression may increase by up to a factor of ≈3,
· if k^{3/2} √n ≲ C_{LZ77}(w) ≲ k^{1/3} n^{2.3}, this factor is at most ≈2,
· if C_{LZ77}(w) ≳ k^{1/3} n^{2.3}, the factor is at most ≈1.
F
Finally, we present an ε-approximation algorithm to pre-edit a word w with a budget of k modifications to improve its compression. In favorable scenarios, this approach yields a total compressed size reduction by up to a factor of ~3, accounting for both the LZ77 compression of the modified word and the cost of storing the edits, C_{LZ77}(w')+k log |w|.