LZ77 — Sliding Window

Huffman exploits symbol frequency. Lempel-Ziv (1977) exploits repetition: when a substring re-appears, replace the second occurrence with a back-reference.

input:  abcdeabcdef
        ^^^^^^^^^^^
LZ77:   a b c d e (5,5) f
                  ^^^^^
                  back 5 bytes, copy 5 bytes

Decoding (5,5) at position 5 means: "go back 5 positions, copy 5 bytes from there". This works recursively with current output — copying bytes can include bytes you JUST emitted via the same back-reference.

Three flavors of token in LZ77 output:

Window size and lookahead size are tunable:

• gzip uses 32 KB window (offset up to 32768)
• zstd defaults to 1 MB, configurable up to 2 GB
• Larger window = catches longer-range repetition; more memory + slower search

The encoder is the hard part: at each position, find the longest match in the previous window. Naive O(n*w) per position. Real encoders use hash chains or suffix automatons.

The decoder is trivial: read tokens, emit literals or copy from history. ~50 lines of code.

LZ77 is the basis of: gzip (DEFLATE = LZ77 + Huffman), zstd, snappy, lz4, brotli. The differences are in the encoder's match-finding cleverness and the literal/length encoding.