Introduction

Open any text file and you will find it repeating itself. The same words, the same phrases, the same chunks of HTML come back again and again. LZ77 — published by Abraham Lempel and Jacob Ziv in 1977 — is the algorithm that noticed this and made it pay.

The idea is almost embarrassingly simple. As the algorithm reads through the text it keeps a sliding window of everything it has seen recently. Whenever the next few characters have already appeared inside that window, it does not write them out again. Instead it writes a tiny back-reference: a pair of numbers saying "go back this far, copy this many characters."

Take the word banana. After emitting bb, aa, nn, the next ana is a copy of text three positions back — so banana becomes banb a n followed by (go back 2, copy 3). That single trick, repeated millions of times, is the engine inside gzip, zip, PNG and the DEFLATE format that quietly moves most of the web.

Slide the Window

Type anything into the box below — repetitive text works best. The demo slides a window across your text one position at a time. At each step it looks back for the longest match it has already seen and, when it finds one, replaces those characters with a back-pointer (distance, length) instead of copying them out.

<p class="hint">Type some text — repetitive text shrinks best. LZ77 slides a window across it and turns every repeat into a back-pointer <b>(distance, length)</b> to text it has already seen.</p>
<textarea id="src" rows="2" spellcheck="false">abracadabra abracadabra</textarea>
<div class="btns">
  <button id="run" type="button">Compress</button>
  <button id="ex1" type="button" class="ghost">banana</button>
  <button id="ex2" type="button" class="ghost">abcabcabcabc</button>
</div>
<div id="tokens" class="tokens"></div>
<div class="status" id="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
textarea { width: 100%; font: 600 14px ui-monospace, monospace; padding: .5rem;
           border: 1px solid #cdd9e3; border-radius: 8px; resize: vertical; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .6rem 0; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.tokens { display: flex; flex-wrap: wrap; gap: .35rem; margin: .6rem 0; }
.tok { display: inline-flex; align-items: center; justify-content: center;
       font: 700 13px ui-monospace, monospace; padding: .3rem .5rem; border-radius: 7px; }
.tok.lit { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.tok.ref { background: #1d3557; color: #fff; border: 1px solid #14233a; }
.tok.lit .sym { white-space: pre; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// LZ77 encoder (Lempel & Ziv, 1977). Slide a window over the input; at each
// position, look BACK for the longest run of characters that already appeared,
// and emit either a literal character or a back-reference (distance, length).
// Decoding just replays the tokens, copying from earlier output. The pair of functions below are exact inverses — that round-trip is the demo's claim.
const WINDOW = 64;       // how far back we may point
const MAX_LEN = 64;      // longest copy we encode in one token

function compress(s){
  const out = [];
  let i = 0;
  while (i < s.length){
    let bestLen = 0, bestDist = 0;
    const start = Math.max(0, i - WINDOW);
    for (let j = start; j < i; j++){
      let len = 0;
      // matches may overlap the cursor (classic LZ77 run-length trick)
      while (len < MAX_LEN && i + len < s.length && s[j + len] === s[i + len]) len++;
      if (len > bestLen){ bestLen = len; bestDist = i - j; }
    }
    if (bestLen >= 3){                       // only worth a token if long enough
      out.push({ d: bestDist, l: bestLen });
      i += bestLen;
    } else {
      out.push({ c: s[i] });                 // literal character
      i += 1;
    }
  }
  return out;
}

function decompress(tokens){
  let s = "";
  for (const t of tokens){
    if (t.c !== undefined){ s += t.c; }
    else { const start = s.length - t.d; for (let k = 0; k < t.l; k++) s += s[start + k]; }
  }
  return s;
}

function render(){
  const s = document.getElementById('src').value;
  const tokens = compress(s);
  const box = document.getElementById('tokens'); box.innerHTML = '';
  let lits = 0, refs = 0;
  for (const t of tokens){
    const el = document.createElement('span');
    if (t.c !== undefined){
      lits++;
      el.className = 'tok lit';
      const shown = t.c === ' ' ? '␣' : t.c;
      el.innerHTML = '<span class="sym">' + shown + '</span>';
    } else {
      refs++;
      el.className = 'tok ref';
      el.textContent = '(' + t.d + ',' + t.l + ')';
    }
    box.appendChild(el);
  }
  const ok = decompress(tokens) === s;
  const ratio = s.length ? Math.round(100 * tokens.length / s.length) : 100;
  document.getElementById('status').textContent =
    fmt('%length% chars → %length2% tokens (%lits% literal, %refs% back-refs) — %ratio%% of slots%v%', { length: s.length, length2: tokens.length, lits: lits, refs: refs, ratio: ratio, v: ok ? ' ✓ round-trip OK' : ' ✗ mismatch' });
}

document.getElementById('run').addEventListener('click', render);
document.getElementById('ex1').addEventListener('click', ()=>{ document.getElementById('src').value='banana banana banana'; render(); });
document.getElementById('ex2').addEventListener('click', ()=>{ document.getElementById('src').value='abcabcabcabc'; render(); });
render();
Result
Console

Watch the token list build up. Plain characters cost a full slot each; a single (distance, length) token can stand in for a long stretch of repeated text. Feed it abcabcabcabc or a sentence with repeated words and see how many literal characters collapse into a handful of pointers — that shrinking ratio is exactly what gzip is doing to every page you load.

The Real Complexity

How hard is LZ77 to run, and how good is the result?

  • It is fast. With a hash table mapping short prefixes to recent positions, real LZ77 encoders find matches in roughly linear time in the length of the input. Decoding is even cheaper: just copy bytes that you have already produced.
  • It is provably good. Ziv and Lempel proved that the Lempel–Ziv family is asymptotically optimal: on any stationary, ergodic source it drives the compressed size down to the source's entropy rate, without knowing the statistics in advance. That is why it is called a universal compressor.
  • It is a solved problem. Unlike many topics on KipuHub, LZ77 hides no open question and no intractability. The encoder makes a greedy or near-greedy choice at each step; the only engineering knobs are the window size and how hard you search for matches.
  • The tension is just speed versus ratio. A bigger window and a more thorough match search squeeze out more redundancy but cost more time — that is the whole tuning story behind gzip's -1 through -9 levels.

So LZ77 is the rare star that is both theoretically optimal and practical. Where data compression studies the limits, LZ77 is the workhorse that gets close to them at internet scale.

Where It Matters

LZ77 is probably the most-run compression algorithm in history. Its back-reference trick shows up nearly everywhere bytes need to shrink:

  • The web: HTTP responses are routinely sent with gzip or br (Brotli), both built on the LZ77 idea, so pages download faster.
  • File formats: zip, gzip, PNG images and PDF streams all use DEFLATE, which pairs LZ77 with Huffman coding to pack the tokens tightly.
  • Modern compressors: Zstandard, LZ4 and Brotli are all refinements of the same sliding-window family, trading window size and search effort for speed or ratio.
  • Storage and games: filesystems, databases and game assets lean on LZ77-style codecs to fit more into less space.

Understand LZ77 and you understand the practical core of nearly every compressed file. To see where these methods bump against fundamental limits, compare it with Huffman coding and the broader story of data compression.

Conclusion

LZ77's genius is its modesty. It does not model language or guess what comes next; it simply remembers what it has already seen and replaces every repeat with a short "look back here" pointer. From that one move comes an algorithm that is fast, provably optimal, and woven into nearly every file you open.

That is a satisfying kind of ending — a problem that is genuinely solved. Ziv and Lempel's 1977 sliding window did its job so well that, almost fifty years later, every web page you load is still quietly pointing backwards. For the limits that compression cannot beat, see data compression and Huffman coding.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lz77/Content licensed under CC BY-NC 4.0.