LZ77
Huffman static Huffman needs to know how often each symbol occurs before it can start. LZ77 needs to know nothing at all. The text it has already sent is the dictionary, so a repeat is replaced by a pointer backwards into what the decoder already has, and the decoder builds the same dictionary as it goes without being sent one. Type anything below and watch it find its own repeats.
New to compression by reference? Start here
Instead of sending the next bytes, send a note saying how far back the same bytes already appeared and how many of them to take. The decoder has already read those, so it can copy them.
The dictionary is never transmitted, because it is just the text already decoded. Both ends build the same one by having read the same thing, which is why this costs nothing to set up and why the beginning of a file compresses badly.
Only patterns can be spent
A file gets smaller for one of three reasons. Something in it repeats, so the second copy can be a note saying where the first one was. Or some symbols are commoner than others, so the common ones can be given shorter codes and the rare ones longer. Those two keep every bit, and are called lossless. The third is to throw information away on purpose, which works only where something can be relied on not to miss it: an eye, an ear, or an application that never needed it.
The first two are spending a pattern, and a pattern can only be spent once. Compress an already compressed file and you usually get nothing, or a little worse, because the first pass took what was there. Not always: a different method can find structure the first one was not looking for, which is why some formats chain two. What is certain is the counting argument underneath, and it is about all inputs rather than about yours: no lossless method can shorten every possible input, because shortening some must lengthen others. The machines here are choosing which inputs to be good at.
The machine for this idea on its own is Huffman, if you would rather press it than read about it.
A window, the longest match in it, and a decoder that needs nothing extra
1 The window of bytes already seen
Everything already encoded is available to point back into, up to the window's width. Nothing outside it can be referred to, which is why a repeat that comes back too late costs full price.
2 The longest match inside it
At each position the encoder looks back through the window for the longest run that matches what comes next. Not the first match, and not a sampled one: the longest, found by looking at every position.
| at | token | stands for | bits |
|---|---|---|---|
| 0 | literal | "a" | 9 |
| 1 | literal | "b" | 9 |
| 2 | literal | "r" | 9 |
| 3 | literal | "a" | 9 |
| 4 | literal | "c" | 9 |
| 5 | literal | "a" | 9 |
| 6 | literal | "d" | 9 |
| 7 | back 7, length 4 | "abra" | 10 |
| 11 | literal | " " | 9 |
| 12 | back 12, length 11 | "abracadabra" | 10 |
3 A pointer and a length, instead of the bytes
A pointer is a distance and a length, and it is only worth emitting when it is shorter than the characters it replaces. Short matches are left as literals for exactly that reason.
- literals
- 8
- pointers
- 2
- bits out
- 92 bits
- bits in
- 184 bits
- ratio
- 0.50
4 Decoding, which needs no dictionary because it builds one
The decoder has no dictionary and is never sent one. It copies from what it has already produced, one character at a time, which is also why a pointer may legally reach into the run it is currently writing.
- what the decoder produced
- "abracadabra abracadabra"
- identical to the input
- yes
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| all 4 texts decode back to exactly what went in | yes | the decoder is handed tokens and nothing else, and rebuilds the dictionary as it goes |
| a pointer may reach further than it goes back, and 1 here do | yes | distance 1, length 16: the copy reads bytes it is still writing, which is why it is done one character at a time |
| repetition costs 50 per cent of the raw bits and unique text costs 105 | yes | a text with nothing to point at gets bigger, which is the honest half and the reason the flag bit is counted |
| the cost counts a flag and a pointer, never the text a pointer stands for | yes | 92 bits either way; the token carries the matched text for the page to show and it is not counted |
| no pointer reaches further back than the window, at any window size | yes | an 8-byte window produced 3 pointers, none reaching past it |
The encoder replaced 2 runs with pointers into text the decoder already had, and the decoder rebuilt the input exactly without ever being sent a dictionary. 92 bits against 184.
What is real here, and what is not
The bit costs here are assumed, not a format
A literal is counted as one flag bit and eight bits of character, and a pointer as one flag bit, five bits of distance and four of length. Real formats do not do this: DEFLATE Huffman-codes the literals and the lengths together and encodes distances in buckets, which makes it smaller than the number shown here. The sizes are stated so the comparison is honest rather than implied.
Random text gets bigger, and the page shows it
Compression is not free. Text with no repeats emits nothing but literals, each of which costs a flag bit more than the character did, so the output is larger than the input. Type something without repetition and watch the ratio go above one. Any explanation that only ever shows a saving is hiding this.
A match may overlap what it is producing
A distance of one and a length of forty means repeat the previous byte forty times, and the decoder handles it by copying one character at a time rather than in a block. That is not an edge case to be defended against; it is the case that does the most work on runs.
The search is the paper's; the token format is later
Ziv and Lempel are proving something about universal compression of sequences from an unknown source, and this entry used to say the sliding window with its literal-or-pointer encoding was one concrete reading of a more abstract paper. That gives the paper too little credit and this page too much. The bounded buffer of recent output and the maximum-length copy from it are in the 1977 paper, plainly. What is later is the TOKEN: the classical LZ77 phrase carries the match together with the following unmatched symbol, where this page chooses between emitting a literal and emitting a copy, and only points backward when the pointer costs fewer bits. That choice is the Storer and Szymanski line of 1982, usually called LZSS, and it is here because it makes the decision visible. An outside audit found the boundary drawn in the wrong place, which is to say backwards.