Workspace

LZ77: replacing repeats with back-references

3 day streakD

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.

DepthLesson 3 of 620 min

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.

Worked exampleabcabcabc
Positions 0–2
No earlier match: literals a, b, c
Position 3
abcabc matches 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.

Figure 3.1

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.

Pick or type text and adjust the window. Literals are grey; matches are gold, labelled with distance and length. The token count and estimated size update, showing how repetition, and a window large enough to reach it, drive the ratio.

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

StageDEFLATE (gzip)Zstandard
Repeat removalLZ77, 32 KB windowLZ77, large configurable window
Literals coded withHuffmanHuffman
Lengths and distances coded withHuffmanFSE (ANS)
Levels1–9Negative 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 storage

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

Git stores objects zlib-compressed and also delta-compresses similar files against each other in packfiles: the same back-reference idea across files.

Kafka

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.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap