On this page
Abraham Lempel and Jacob Ziv of the Technion in Israel published a plain idea in 1977: when data repeats, don't send it again, point back to where it already appeared. That method, and the one they published a year later, still sit under ZIP files, PNG images and GIF animations. Here is how both work, with a pencil-and-paper example.
What did Lempel and Ziv invent?
Their paper "A universal algorithm for sequential data compression" (LZ77) appeared in IEEE Transactions on Information Theory in May 1977. "Compression of individual sequences via variable-rate coding" (LZ78) followed in the same journal in September 1978.
"Universal" is the important word. The 1977 paper says that when nothing is known in advance about the data, the coding process must be "interlaced with a learning process". Codes such as David Huffman's are built from how often each symbol appears; Lempel–Ziv methods learn the patterns while reading.
Ziv died in March 2023 at 91, two years after receiving the IEEE Medal of Honor "for fundamental contributions to information theory and data compression technology" (Technion). Lempel, a computer scientist born in Poland in 1936, died the same year (Technion).
How does LZ77 compression work?
The 1977 paper describes "maximum-length copying from a buffer containing the recent past output" (Ziv and Lempel, 1977). In plain words: find the longest piece of what comes next that already appears in the recent text, and send only where it is and how long it is. In the paper, each codeword holds the match's position, its length and the next symbol.
The version inside ZIP and PNG, called DEFLATE, sends either a plain letter or a pair: a backward distance and a length. Its specification limits distances to 32K bytes and lengths to 258 bytes, and the shortest copy is 3 bytes (RFC 1951).
Try it on "banana bandana", space included, using the DEFLATE rule: copies at least 3 letters long, written as (distance back, length).
b, a, n: nothing has been seen yet, so send three plain letters.
"ana" comes next. It starts 2 places back. Send (2,3). The copy overlaps itself: the last letter copied is the a you just wrote. That is allowed, and it is how LZ77 squeezes long runs like "aaaaaaa".
The space is new: send it plain.
"ban" appeared 7 places back. Send (7,3).
d is new: send it plain.
"ana" appeared 8 places back. Send (8,3).
The output is b a n (2,3) space (7,3) d (8,3): eight tokens instead of fourteen characters.
The paper names the main drawback: "susceptibility to error propagation in the event of a channel error". Later copies point back to earlier text, so one damaged letter can spread.
How is LZ78 different, and where does GIF come in?
LZ78 drops the window of recent text and builds a numbered dictionary instead. Its "incremental parsing" "creates a new phrase as soon as a prefix of the still unparsed part of the string differs from all preceding phrases" (Ziv and Lempel, 1978). Each new phrase is an earlier phrase plus one letter, so it is sent as (number of that earlier phrase, new letter). On banana bandana:
1: b = (0, b)
2: a = (0, a)
3: n = (0, n)
4: an = (2, n)
5: a and space = (2, space)
6: ba = (1, a)
7: nd = (3, d)
8: ana = (4, a)
In 1984 Terry Welch published a variant, LZW, in IEEE Computer. The GIF89a specification calls its compression "a variation of the Lempel-Ziv Compression algorithm in which variable-length codes are used to replace patterns", with codes of up to 12 bits.
Where is Lempel–Ziv used today?
ZIP: the format's APPNOTE lists method 8, "Deflated".
DEFLATE: it "compresses data using a combination of the LZ77 algorithm and Huffman coding" (RFC 1951). LZ77 removes repeats; Huffman coding gives frequent symbols shorter codes.
PNG: the W3C PNG specification defines one compression method, deflate with a sliding window of at most 32768 bytes.
GIF: LZW, as above.
All of these are lossless. As the 1978 paper puts it, "no distortion is allowed, and the original data must be fully recoverable" (Ziv and Lempel, 1978). For a different approach to images, read how Ingrid Daubechies's wavelets changed image compression.
How can you practise Lempel–Ziv by hand?
Write a line with repeats, such as the chant "India India India".
Encode it with LZ77 pairs (minimum copy of 3), then with LZ78 phrases.
Count tokens for each, then try a line with no repeats and see why it does not shrink.
Swap with a friend and decode each other's output.
If ideas underneath, such as bits and binary codes, feel shaky, the Fermi Concept Library has every concept in physics, chemistry, biology, mathematics and computing. And if you get stuck on an overlapping copy, Fermi's AI tutor can work out what you already know and build a plan for the session.
For where it all began, read how Claude Shannon measured information in bits.
