LZ77
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.
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
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 paper is more general than this page
Ziv and Lempel are proving something about universal compression of sequences from an unknown source, and the sliding window with a literal-or-pointer encoding is one concrete reading of it. What everybody now implements descends from that reading rather than being what the paper literally specifies.