LZ77: replacing repeats with back-references
Most real data repeats itself. LZ77 replaces a repeat with “copy n bytes from d back”. Learn the parse, the window, and how DEFLATE and zstd combine it with entropy coding.
Entropy coding treats symbols one at a time. But text, code and JSON repeat whole strings: keys, function names, HTML tags, log prefixes. LZ77 scans the input and, at each position, looks back into a window of recent data for the longest earlier match. If it finds one, it emits a (distance, length) pair; otherwise it emits the next byte as a literal.
- Positions 0–2
- No earlier match: literals
a,b,c - Position 3
abcabcmatches starting 3 back- Emit
- (distance 3, length 6)
- Output
a b c+ copy 6 from 3 back
The copy overlaps itself: copying byte by byte from 3 back regenerates the pattern as it goes. That is how LZ77 expresses runs too.
Parse text into literals and matches
{"type":"tool_result","id":1},↩30,27{"type":"tool_result","id":2}
- Literals
- 32
- Matches
- 1
- Estimated size
- 38 B
- vs 8-bit text
- 64%
Toy cost model: a literal costs 9 bits (flag + byte); a match costs 1 + 6 distance bits + 8 length bits. Real codecs entropy-code these too.
Finding matches quickly
Checking every earlier position for every new one would be quadratic. Encoders hash the next three or four bytes and keep hash chains: for each hash, a list of earlier positions with the same prefix. At each position they follow the chain for a few candidates and keep the longest match. Compression levels mostly decide how long to search: level 1 checks a handful, level 9 or 19 searches deep.
Window size
The window limits how far back a match can reach. DEFLATE's window is 32 KB, so a repeat 40 KB earlier is invisible. zstd and Brotli support much larger windows, megabytes up to gigabytes in long modes, which finds repeats across a large file. The cost is memory: the decoder must keep the whole window too.
Putting it together: DEFLATE and zstd
| Stage | DEFLATE (gzip) | Zstandard |
|---|---|---|
| Repeat removal | LZ77, 32 KB window | LZ77, large configurable window |
| Literals coded with | Huffman | Huffman |
| Lengths and distances coded with | Huffman | FSE (ANS) |
| Levels | 1–9 | Negative fast levels through 19, plus ultra 20–22 |
Go deeperStreaming and flush modes
A compressor holds data back to find better matches and to fill a block. That is fine for files and fatal for streams: an SSE event sitting inside a gzip buffer never reaches the client. Codecs offer flush operations that end the current block and emit everything so far, at a small cost in ratio.
In Node, zlib streams take flush: zlib.constants.Z_SYNC_FLUSH, and you can call .flush() after each event. Many compression middlewares do neither, which is why they buffer token streams (Module 6).
Where you will meet it
Log systems compress blocks of lines with zstd or LZ4. Repeated prefixes such as timestamps and service names make ratios of 5–10× common.
Git stores objects zlib-compressed and also delta-compresses similar files against each other in packfiles: the same back-reference idea across files.
Kafka compresses batches of messages together, so repeats across messages are found, which single-message compression would miss.
Words to know
- Literal
- A byte emitted as-is because no useful match was found.
- Back-reference
- A (distance, length) pair pointing to earlier data.
- Window
- How far back the encoder may look for matches.
- Hash chain
- Lists of earlier positions with the same short prefix, for fast match search.
Check yourself
Answer out loud before you open each one.
What does an LZ77 match encode?
A distance back into the window and a length to copy.
How can a match be longer than its distance?
The copy overlaps itself; copying byte by byte reuses bytes just written, which encodes runs and periodic patterns.
Why does gzip miss a repeat 100 KB back?
DEFLATE's window is 32 KB, so the earlier copy is out of reach.
Try it
Concatenate a 50 KB file with itself and gzip both the single and double versions. Then do the same with zstd --long. Explain the difference.