Analyzing and Leveraging the $k$-Sensitivity of LZ77

We study the sensitivity of the Lempel-Ziv 77 compression algorithm to edits, showing how modifying a string $w$ can deteriorate or improve its compression. Our first result is a tight upper bound for $k$ edits: $\mathrm{\forall }{w}^{\mathrm{\prime }}\in B(w,k)$, we have $C_{\mathrm{L}\mathrm{Z}77}(w^{\mathrm{\prime }})\le 3\cdot C_{\mathrm{L}\mathrm{Z}77}(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_{\mathrm{L}\mathrm{Z}77}(w)$, and establish a surprising trichotomy based on the compressibility of $w$. More precisely we prove the following bounds: - if $C_{\mathrm{L}\mathrm{Z}77}(w)\lesssim k^{3\mathrm{/}2}\sqrt{n}$, the compression may increase by up to a factor of $\approx 3$, - if $k^{3\mathrm{/}2}\sqrt{n}\lesssim C_{\mathrm{L}\mathrm{Z}77}(w)\lesssim k^{1\mathrm{/}3}{n}^{2\mathrm{/}3}$, this factor is at most $\approx 2$, - if $C_{\mathrm{L}\mathrm{Z}77}(w)\gtrsim k^{1\mathrm{/}3}{n}^{2\mathrm{/}3}$, the factor is at most $\approx 1$. Finally, we present an $\epsilon$-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_{\mathrm{L}\mathrm{Z}77}(w^{\mathrm{\prime }})+k\log \mathrm{\mid }w\mathrm{\mid }$.