LZ77 Compression: Finding Repeats In a Sliding Window

Replace repeats with pointers to the past

LZ77, published by Abraham Lempel and Jacob Ziv in 1977, compresses data by replacing repeated substrings with a small back-reference to where they occurred earlier — the founding idea behind gzip, zlib, PNG, DEFLATE and, indirectly, most modern compressors. The algorithm slides a two-part window across the input: a search buffer of already-seen data behind the cursor, and a look-ahead buffer of upcoming data still to be encoded.

[........search buffer........][cursor][...look-ahead buffer...]
at each step: find the LONGEST match between look-ahead and search buffer
emit token (distance, length, next-literal)  then slide the window forward

The (distance, length, literal) token

Every step of LZ77 emits one token: a distance back to the start of the best match found in the search buffer, a length for how many bytes match, and one literal byte that follows the match (needed to guarantee progress even when no match exists, in which case distance and length are both zero). A greedy longest-match search is standard — always take the longest match available at the cursor, even though a shorter match now can occasionally allow an even longer one immediately after; real compressors sometimes use lazy matching, peeking one byte ahead before committing, to claw back some of that lost ratio cheaply.

example:  "the cat sat on the mat"
encoding "the mat" late in the string can reference "the " from position 0:
token: (distance=19, length=4, literal='m') + literals "at"

Why the match can overlap itself

A subtlety that trips up naive implementations: the match length can legally exceed the current distance. If distance is 3 and length is 8, the decoder does not fail — it copies byte-by-byte from 3 positions back, and because each copied byte immediately becomes available as a source for the next copy, the result is a repeating pattern. This single rule is how LZ77 compresses long runs of a repeated short pattern (like 'aaaaaaaa' or a repeating wallpaper texture) into one tiny token instead of needing one token per repetition.

Window size is the whole trade-off

The search buffer's size caps how far back a match can reference, so it directly bounds the compression ratio on data with long-range repetition: DEFLATE (used by gzip, zlib and PNG) fixes it at 32 KB, while newer formats push it much further — Brotli allows up to 16 MB and Zstandard's "long distance matching" mode can span the entire file. A bigger window catches more repeats but costs more memory and, naively, more search time; production encoders use a hash table keyed on the next few bytes so a match search is O(1) average instead of scanning the whole window linearly.

LZ77 is only half the pipeline

Raw LZ77 output — a stream of (distance, length, literal) tokens — is not itself maximally compact, because short distances, common lengths and frequent literals should cost fewer bits than rare ones. DEFLATE therefore runs LZ77's output through a second stage, Huffman coding, which assigns shorter bit-codes to the most frequent tokens; this two-stage design (dictionary matching, then entropy coding) is the template that essentially every general-purpose compressor since 1977 has followed, including LZMA, Brotli and Zstandard, which mostly differ in how cleverly they search for matches and which entropy coder they pair it with.

LZ77 versus LZ78

The sibling algorithm LZ78 (1978) replaces the sliding window with an explicit, growing dictionary of previously seen phrases, referenced by index rather than by (distance, length) — the basis of LZW, used in GIF and old Unix compress. LZ77's advantage is that it needs no explicit dictionary structure to transmit or synchronise; its disadvantage is that a match can only look as far back as the window allows, whereas LZ78's dictionary conceptually spans the entire input seen so far.

Frequently asked questions

Try it live

Everything above runs in your browser — open LZ77 Compression and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.