{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiabln4mn76yey355j537ecln5hy6zeucl2t43yzfuxoagpel2usta",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mflbf3spaaz2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.19649v1",
  "publishedAt": "2026-02-24T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Gabriel Bathie",
    "Paul Huber",
    "Guillaume Lagarde",
    "Akka Zemmari"
  ],
  "textContent": "**Authors:** Gabriel Bathie, Paul Huber, Guillaume Lagarde, Akka Zemmari\n\nWe 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: $\\forall w' \\in B(w,k)$, we have $C_{\\mathrm{LZ77}}(w') \\leq 3 \\cdot C_{\\mathrm{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_{\\mathrm{LZ77}}(w)$, and establish a surprising trichotomy based on the compressibility of $w$. More precisely we prove the following bounds: - if $C_{\\mathrm{LZ77}}(w) \\lesssim k^{3/2}\\sqrt{n}$, the compression may increase by up to a factor of $\\approx 3$, - if $k^{3/2}\\sqrt{n} \\lesssim C_{\\mathrm{LZ77}}(w) \\lesssim k^{1/3}n^{2/3}$, this factor is at most $\\approx 2$, - if $C_{\\mathrm{LZ77}}(w) \\gtrsim k^{1/3}n^{2/3}$, the factor is at most $\\approx 1$. Finally, we present an $\\varepsilon$-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{LZ77}}(w') + k \\log |w|$.",
  "title": "Analyzing and Leveraging the $k$-Sensitivity of LZ77"
}