LZ77 Compressor Demo

Watch the sliding window scan left-to-right: on each step it finds the longest back-reference in the search window and emits a (offset, length, literal) token.

Worked example — LZ77 Compressor Demo

Look-ahead	[0..7] "abracada"
Tokens emitted: 1 of 6	5.18×
Output tokens	(0,0,'a')

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

A bigger window helps less than it costs 🖖

It seems obvious that a larger search window compresses better, since more history means more chances to find a match. The catch is that every single pointer has to be able to address anywhere in that window, so widening it lengthens the distance field for every reference you emit — including the thousands that only needed to reach back a few bytes. Double the window and you add a bit to all of them, whether it bought a longer match or not. That trade-off is why DEFLATE, the algorithm inside ZIP, PNG and gzip, settled on 32 KB and stayed there for decades: far enough back to catch real repetition in ordinary text, close enough that the offsets stay cheap.

Copying instead of repeating 🖖

When the algorithm meets text it has already read, it does not spell it out again. It jots a short note: "go back offset characters and copy length of them." Each token here is (offset, length, literal): a back-reference plus one fresh character. Text full of repeated words or patterns shrinks a lot, while already-random data barely compresses at all.

When one token becomes a long run 🖖

A match can point just one character back yet copy more characters than exist there yet. With offset 1, the decoder copies each byte the instant it writes it, so a single token like (1, 5, ...) unfolds aaaaaa from one starting a. Classic run-length encoding therefore falls out of LZ77 for free — the "copy" overlaps text still being produced. Try the repetitive sample to watch a match region stretch past the current position.

Problem solved in full

Six tokens of "abracadabra" with a search window of 16 characters 5 steps
The panel reads 5.18× after one token. Work out what it reads after all six. The input is "abracadabra", the search window is 16 characters and the look-ahead buffer is 8.
1. A token is three fixed-width fields, so its cost is decided by the two settings and not by the data. The offset has to address any position in the window, the length any value up to the buffer size, and the literal is a raw byte.
  
  $⌈ lo g_{2} (W + 1)⌉ + ⌈ lo g_{2} (B + 1)⌉ + 8 = ⌈ lo g_{2} 17 ⌉ + ⌈ lo g_{2} 9 ⌉ + 8 = 5 + 4 + 8 = 17 bits$
2. The encoder scans left to right and takes the longest match the window offers. Nothing sits behind the first three characters, so 'a', 'b' and 'r' each cost a whole token to say once. Only the final token earns its keep, copying "abra" from position 0.
  
  $(0, 0, a) (0, 0, b) (0, 0, r) (3, 1, c) (5, 1, d) (7, 4, \emptyset)$
3. The ratio on the panel is a running figure, and it divides the whole input by the output produced so far. After one token it is weighing eleven characters against seventeen bits, which is why it opens so high.
  
  $\frac{11 \times 8}{1 \times 17} = \frac{88}{17} = 5.18 \times$
4. Six tokens at seventeen bits each is 102 bits, against an input of 88. The encoding is bigger than the thing it encodes.
  
  $\frac{11 \times 8}{6 \times 17} = \frac{88}{102} = 0.86 \times$
5. The break-even is one division. A token costs 17 bits and buys some number of characters worth 8 bits each, so the scheme wins only when the average token advances more than 17/8 characters — and of these six, only the last one does.
  
  $\frac{N}{T} > \frac{17}{8} = 2.125, \frac{N}{T} = \frac{11}{6} = 1.83$
Answer

The panel prints 5.18× after the first token and 0.86× after the sixth: the same string, the same encoding, on opposite sides of 1.0. The figure worth keeping is 2.125 characters per token, which is just the token width divided by eight, and it is the whole test of whether LZ77 helps a given input. It also prices a knob that looks free. Widening the search window to 64 adds two bits to every offset field, and on this string it finds no longer match at all — the parse is the same six tokens — so the ratio drops to 0.77×. Every doubling of the reach costs one more bit on every token, used or not.

$\frac{N}{T} > \frac{⌈ lo g _{2} ( W + 1 )⌉ + ⌈ lo g _{2} ( B + 1 )⌉ + 8}{8}$

Learning path

Compression by hand

Leads to Burrows-Wheeler repetition measured in phrases rather than symbols: a back-reference saying how far back to go and how much to copy.

References (1)

The algorithm, and the offset-1 trick block 3 turns on: J. Ziv and A. Lempel, "A universal algorithm for sequential data compression." IEEE Transactions on Information Theory 23(3), 337–343, 1977.

By the 42Math team · Updated 2026-08-17

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

abracadabra → 6 tokens - "abracadabra": 6 tokens for 11 characters, and the last one reaches 7 back to copy 4 - the whole of "abra" in a single reference.
aabaabaabaab → 3 tokens - "aabaabaabaab": 4 tokens for 12 characters, and one of them copies 7 from only 3 back, so the match runs past the character being written. Run-length encoding, for nothing.
the quick brown fox → 16 tokens - "the quick brown fox": 16 tokens for 19 characters, and the longest match in it is a single letter. Prose this short has almost nothing to point back at.
ATGATCGATCG → 5 tokens - "ATGATCGATCGATCG": 6 tokens for 15 bases. The fifth reference copies 7 from 4 back, overlapping itself, because ATCG repeats on a shorter period than the match it is filling.