LZ77: exploiting repetitions

Another source of redundancy

Huffman exploits symbol frequencies. But real files contain another kind of redundancy: repeated sequences. In a text, words recur; in an image, patterns repeat. The LZ77 algorithm (Lempel-Ziv, 1977) exploits precisely these repetitions, and it is the core of formats like ZIP, PNG and gzip.

The idea: replace a repetition with a reference

When a sequence has already been seen recently, instead of writing it out again, LZ77 inserts a reference: "copy so many characters, located so many positions back." A long repetition is thus replaced by a small pair (distance, length).

Sliding window over the text "abcabcabc":

[               ] abcabcabc      (window empty at the start)
[a              ] bcabcabc       (write 'a' as is)
[ab             ] cabcabc        (write 'b')
[abc            ] abcabc         (write 'c')
[abc  ] abc <---- abc            ('abcabc' already seen! -> reference)

     -> the run "abcabc" is replaced by (distance=3, length=6)
(distance = how far to go back, length = how many characters to copy)

The sliding window

LZ77 does not search for repetitions in the whole file (too costly), but in a window of recent characters that slides along the text. A larger window finds more distant repetitions (better compression) but costs more memory and search time.

The best of both worlds

In practice, modern formats combine both approaches: LZ77 first replaces repetitions with references, then Huffman encodes the result. This is exactly what DEFLATE does, the algorithm behind gzip and ZIP: two complementary ideas attacking two different kinds of redundancy.

Classic pitfall

LZ77 gains nothing on data without repetition, such as an already compressed file or random data: there is then no sequence to reference. Worse, encoding useless references can make the file slightly larger. Each algorithm targets a specific redundancy; where it is absent, it works no miracles.