Cairn
algorithms · compression · O(n·W·L) encode (naive), O(n) decode — n = input length, W = window size, L = lookahead size

↩ back to Compression

LZ77 Compression

LZ77 looks for repeats a different way than LZW Compression does. Instead of building a dictionary that remembers every substring seen since the start of the message, it only ever looks inside a fixed-size window of the most recently seen characters — and only ever reads ahead by a fixed-size lookahead. At each position, it searches the window for the longest match to what's coming up next and emits one token: how far back the match starts (offset), how long it runs (length), and the one literal character right after the match ends. If nothing in the window matches at all, the token is just that one literal, with offset and length both zero. The decoder replays each token by copying length characters from offset positions back in its own already-reconstructed output, then appending the trailing literal — nothing but the token stream itself ever needs to cross the wire, the same self-describing property RLE and LZW both already have.

This is the Compression category's fourth entry. The genuinely different idea against the other four: a bounded window is a real resource cap that LZW's adaptive dictionary (see its own Pitfalls) has no equivalent of — memory use here never grows past what the window and lookahead sizes allow, no matter how long the message runs. The real cost of that cap is just as real: a repeat sitting even one character outside the window becomes invisible, in a way a repeat anywhere earlier in an unbounded dictionary never would be. LZ77 (Ziv & Lempel, 1977) is also not a museum piece — it's the actual mechanism behind DEFLATE, the algorithm zlib, gzip, and PNG all build on, though every one of those real formats uses a variant (LZSS) that changes the token format for reasons measured in the first Pitfall below — DEFLATE's own page measures what LZSS and a Huffman-coded token stream are each worth on top of this one.

Try it

Type a message and press Load, then Step or Run. This demo fixes the window at 6 characters and the lookahead at 4, small enough to watch by eye: the tan cells are the current search window, green marks the actual match found inside it (if any), and the accent-colored cells are the characters that match consumes this step (the copied span plus its trailing literal). The default message is built so its final match reaches the exact edge of the 6-character window — see the first Pitfall below for what happens when that same message meets a window one character narrower.

input (window / match / consumed highlighted)

tokens emitted, in order (offset, length, next)

Press Load.

Why it works

On the default message abcabcabcabc (12 characters, window 6, lookahead 4): the first three positions (a, b, c) have nothing behind them yet, so each emits a plain literal token — (0,0,a), (0,0,b), (0,0,c). At position 3 (the second a), the window holds abc: starting the comparison at offset 3 (the very first a), a matches a, b matches b, c matches c, and a (one more character into the lookahead) matches a again — four characters, which is as far as the 4-character lookahead lets the match run. Emit (3,4,b) (the trailing literal is whatever comes right after the match, position 7) and jump ahead 5 positions, to position 8. The window there is cabcab (the 6 characters immediately behind position 8); starting the comparison at offset 6 (the very first c) again finds a run of 4 matching characters — the lookahead cap again — and this time the match runs out the message exactly: there's no character left after it, so the token is (6,4) with no trailing literal at all. Five tokens — three literals and two length-4 matches — cover all twelve characters, and the second match's offset of 6 is the largest one this window can ever produce: it's reaching all the way to the window's own far edge.

Reference implementation

Round-trip tested with a 20,000-trial fuzz test (random strings, alphabet size 1–4, length 1–30, window 20, lookahead 10 — the same harness convention LZW's own page uses) — zero mismatches.

function lz77Encode(input, windowSize, lookaheadSize) {
  const tokens = [];
  let pos = 0;
  while (pos < input.length) {
    let bestLen = 0, bestOffset = 0;
    const windowStart = Math.max(0, pos - windowSize);
    const maxLen = Math.min(lookaheadSize, input.length - pos);
    for (let start = windowStart; start < pos; start++) {
      let len = 0;
      while (len < maxLen && input[start + len] === input[pos + len]) len++;
      if (len > bestLen) { bestLen = len; bestOffset = pos - start; }
    }
    const next = (pos + bestLen < input.length) ? input[pos + bestLen] : '';
    tokens.push({ offset: bestOffset, length: bestLen, next });
    pos += bestLen + 1;
  }
  return tokens;
}

function lz77Decode(tokens) {
  let out = '';
  for (const t of tokens) {
    // One character at a time, not a one-shot slice — a match can legitimately reach past
    // its own starting point (length > offset), copying characters this very token is still
    // writing. See Pitfalls for how common that is and what a one-shot slice gets wrong.
    for (let i = 0; i < t.length; i++) out += out[out.length - t.offset];
    if (t.next !== '') out += t.next;
  }
  return out;
}

Pitfalls

Every token pays the same fixed cost whether or not it found anything to point at — so this format is a losing choice on short, lightly-repetitive input, and not just against doing nothing. With a 32-character window (6 bits per offset) and a 15-character lookahead (4 bits per length), every token costs at least 10 bits before a single literal is added. Run that fixed format against the same short strings LZW's own Pitfalls already measured:

inputLZ77 bitsLZW bitsfixed-width baseline
ABABABABA32119
abracadabra753233
mississippi723022
the quick brown fox2249676

LZ77 loses to the fixed-width baseline on every single row, and loses to LZW by 2–3x on top of that — the opposite of a free win. The same mechanism turns around completely once the input is long and genuinely repetitive enough to amortize that fixed per-token tax over longer matches:

inputlengthtokensLZ77 bitsfixed-width baselineratio
a sentence repeated 3×134356256700.93x
ab repeated 100×20081122000.56x
abcdef repeated 50×300152379000.26x

The gap between these two tables is exactly the gap between a textbook demo string and the kind of input LZ77 is actually for. Real formats avoid the short-input tax a different way than this page's reference implementation: LZSS, the variant DEFLATE and friends actually use, spends one flag bit per token instead of a full offset+length pair, and only pays for offset/length at all when that bit says "this is a match" — a plain literal costs one flag bit plus the literal itself, not a wasted 10-bit offset/length pair it never needed. This page's always-emit-a-triple format is the original 1977 description, kept here because it's simpler to trace by hand; the fixed tax measured above is specifically its cost, not a cost inherent to sliding-window compression itself.

A window one character too narrow doesn't shrink a match — it can erase it completely. Encode abcdefabcdef (12 characters, the two halves identical) with a 6-character window: the first six characters go out as literals, then the second half matches the first at offset 6, length 6 — one token covering the entire second half, 7 tokens total. Shrink the window to 5 and rerun the identical input: offset 6 is now one character past what a 5-character window can reach, and there is no shorter match available either (nothing in the last 5 characters behind position 6 repeats) — the entire second half falls back to six more literal tokens, 12 tokens total, zero compression. One character of window lost the whole match, not a fraction of it. LZW has no equivalent failure mode (its dictionary has no size limit of its own, per its own Pitfalls) — but pays for that with unbounded memory growth that LZ77's fixed window never has to worry about. Bounded memory and a bounded view of the past are the same tradeoff, not two separate ones.

A match commonly reaches past its own starting point, copying characters it is still in the middle of writing — and that's the normal case, not a rare corner. Encode twelve repeated as with the demo's own 6-window/4-lookahead sizing: the tokens are (0,0,a), (1,4,a), (6,4,a), (6,1) — the second token alone has length 4 copying from only 1 character back, so three of its four copied characters don't exist in the output yet when the token starts. A decoder that copies the match as one slice(start, start + length) call, rather than one character at a time, reads that still-too-short output and produces aaaaa — 5 characters — instead of the correct 12. Across the same 20,000-trial fuzz test above, 15,121 of the resulting tokens had a length greater than their own offset, and the one-shot-slice decoder failed on 12,083 of the 20,000 trials (60.4%) — not an exotic edge case, close to a coin flip. Copying one character at a time, letting each newly written character become a valid source for the next copy within the same token, is what the reference implementation above does and why it's correct.

Complexity

Time: the reference implementation above is O(n·W·L) — for each of the n input positions, it scans up to W window-start candidates and compares up to L characters at each one. A real high-throughput implementation (zlib's own included) avoids the W factor with a hash chain keyed on the next few characters, jumping straight to candidate match positions instead of scanning the whole window — the same "don't rehash, index instead" shortcut LZW's own Complexity section mentions for its dictionary lookups, applied to a different data structure. Decoding is O(n): one constant-time step (a character copy or a literal append) per output character, with no search at all. Space: O(W + L) for the window and lookahead — bounded by two fixed numbers chosen once in advance, never by the input length. That's the direct flip side of the window-size Pitfall above: the same cap that can erase a distant match is also what keeps memory use flat no matter how long the message runs, unlike LZW's dictionary, which is O(n) in the worst case for exactly the opposite reason.

See Choosing a Compression Approach for how this entry compares against the site's other six.