The idea: remove repeats, then code what is left
DEFLATE, the format inside gzip, zip and PNG, compresses in two passes. First LZ77 (Lempel and Ziv, 1977) walks through the input and replaces every repeat of something it has seen recently with a short back-reference: "go back distance bytes and copy length bytes". Bytes that are not part of a repeat go out unchanged as literals. Then Huffman coding gives the resulting symbols codes of different lengths: frequent ones short, rare ones long.
The two passes remove different kinds of redundancy. LZ77 removes repeated strings; Huffman coding removes uneven symbol counts. The page shows both on three short inputs, one cell per byte.
LZ77: the sliding window
The encoder keeps a window of the last W bytes it has already encoded (the shaded cells). At the cursor it looks for the longest match: the longest string starting at the cursor that also starts somewhere in the window. If the match has at least 3 bytes it emits the token (distance, length) and jumps length bytes ahead; otherwise it emits the byte at the cursor as a literal and moves one byte. This is the greedy rule. When two matches are equally long, the page takes the closer one, since small distances get cheaper codes.
In "abracadabra abracadabra" the first seven bytes are literals; then "abra" is found 7 bytes back and becomes (7,4); after a literal space, the whole second "abracadabra" is a copy of the first, 12 bytes back: (12,11). (Demos: one token at a time; abracadabra ×2.)
The decoder needs no window search at all. It appends literals to its output and, for (d, L), copies L bytes starting d bytes back. That is why decompression is much faster than compression, and why gzip's -9 (search harder) slows down only the compressor.
Copies that overlap themselves
A match is allowed to run past the cursor, so its length can be larger than its distance. "Blah blah blah blah blah!" becomes B l a h ␣ b (5,18) !: copy 18 bytes from 5 back, although only 5 bytes lie between the source and the cursor. The decoder copies one byte at a time, so by the time it needs byte 11 it has already written it as part of the same copy.
This is how LZ77 handles runs: "aaaaaaaa" is a (1,7), which is run-length encoding for free. A decoder that copies with memcpy for overlapping ranges gets this wrong; real decoders copy byte by byte (or in chunks no larger than d). (Demo: Blah blah…)
The window size
The window bounds how far back a match may start. A repeat further back than W bytes is invisible. With an 8-byte window the second "abracadabra" is 12 bytes back, too far, so the encoder finds only the shorter "abra" pieces: 15 tokens and 48 bits instead of 11 tokens and 40 bits. (Demo: small window.)
| parameter | on this page | DEFLATE (RFC 1951) |
|---|---|---|
| window | 32 or 8 bytes | up to 32 KB (distances 1–32768) |
| match length | 3 or more | 3–258 |
| finding matches | try every distance | hash of the next 3 bytes → chain of earlier positions (zlib), cut off by the compression level |
| choice | greedy longest match | zlib uses lazy matching: if the next position has a longer match, emit a literal first |
Searching every distance in a 32 KB window would be slow, so zlib hashes the 3 bytes at the cursor and walks a chain of earlier positions with the same hash, giving up after a number of steps set by the compression level. Bigger windows find more repeats; zstd and brotli use windows of megabytes for that reason.
The Huffman stage: two alphabets
DEFLATE codes the LZ77 tokens with two Huffman codes. The literal/length alphabet has 286 symbols: bytes 0–255, 256 for end of block, and 257–285 for match lengths. The distance alphabet has 30 symbols. To keep the alphabets small, each length or distance symbol stands for a range, and extra bits after the code pick the exact value:
| value | symbol | extra bits |
|---|---|---|
| length 3, 4, …, 10 | 257, 258, …, 264 | 0 |
| length 11–12, 13–14, 15–16, 17–18 | 265, 266, 267, 268 | 1 |
| length 258 | 285 | 0 |
| distance 1, 2, 3, 4 | 0, 1, 2, 3 | 0 |
| distance 5–6, 7–8 | 4, 5 | 1 |
| distance 9–12, 13–16 | 6, 7 | 2 |
| distance 24577–32768 | 29 | 13 |
So (12,11) costs: the code for symbol 265, 1 extra bit (11 − 11 = 0), the code for distance symbol 6, and 2 extra bits (12 − 9 = 3 = 11). Each alphabet gets its own Huffman code from the symbol counts, built exactly as on the Huffman Coding page. DEFLATE then sends only the code lengths, and both sides build the same canonical codes from them: sort the symbols by code length, then by value, and count upward in binary.
A DEFLATE stream is a series of blocks, each with a 3-bit header: BTYPE = 00 stored (no compression), 01 fixed Huffman codes defined by the standard, or 10 dynamic codes like the ones on this page, whose code lengths are themselves Huffman-coded in the block header. For short inputs the header can cost more than it saves, so encoders pick the fixed codes; the page leaves the header out of its totals.
Why both passes
| input | raw | Huffman alone | LZ77 + Huffman |
|---|---|---|---|
| abracadabra abracadabra | 184 bits | 58 bits | 40 bits |
| Blah blah blah blah blah! | 200 bits | 73 bits | 32 bits |
| abacadaeafagahaiaj | 144 bits | 53 bits | 53 bits |
Text full of repeats gains most from LZ77. Text without repeated strings of 3 or more bytes gets no tokens from LZ77, only literals, but its letter counts are still uneven ('a' is half of "abacadaeafagahaiaj"), so Huffman still halves it. (Demo: no repeats.) Random or already-compressed data has neither kind of redundancy, which is why zipping a JPEG or a .gz file gains nothing.
DEFLATE is everywhere: gzip and zlib, zip and jar files, PNG images, HTTP Content-Encoding: gzip, git objects. Newer formats keep the same two-stage plan with bigger windows and better entropy coders (zstd: finite-state entropy; brotli: a built-in dictionary and context modelling). See String Search Race and Suffix Array for other ways to find repeated strings.
What the page leaves out
The hash chains and lazy matching that zlib uses to find matches fast; the block header (HLIT, HDIST, HCLEN and the code-length code) and the fixed codes of BTYPE = 01; splitting long inputs into blocks with fresh codes; the limit of 15 bits on a code length; the bit order in which DEFLATE packs codes; and the gzip and zlib wrappers (headers, CRC-32 or Adler-32 checksums). LZ78 and LZW, which build a dictionary instead of pointing back into a window, are also not shown.