Overview
Jacob Ziv (1931–2023) and Abraham Lempel published LZ77 in 1977 and LZ78 in 1978, introducing universal lossless compression that builds its dictionary from the data as it reads it, without prior statistics. The family underlies ZIP, gzip, PNG, GIF and much else.
What You Need
- Lived: 1931–2023, Israel
- Anchor year: 1977 — LZ77
- Strand: overlooked
Steps
The problem as it stood
Huffman coding is optimal for symbol-by-symbol coding but needs symbol frequencies in advance, and it cannot exploit repetition of longer sequences. Real data is full of repeated strings that a symbol-frequency approach cannot see.
What he actually did
Ziv and Lempel devised schemes that replace a repeated sequence with a reference to its earlier occurrence — a distance back and a length. The dictionary is the data already seen, so no advance analysis is needed and the decoder reconstructs it as it goes.
How it worked
"Universal" means asymptotically optimal without knowing the source statistics: the algorithm adapts. Because the decoder builds the same dictionary from the same data, nothing needs transmitting alongside. That single-pass, self-describing property is what made it practical for files and streams alike.
What it made possible
General-purpose lossless compression. ZIP, gzip, PNG and GIF all use LZ variants, usually followed by Huffman coding. The combination — dictionary matching then entropy coding — is the standard architecture of lossless compression.
What happened to him
He was a professor at the Technion and president of the Israel Academy of Sciences, and received the IEEE Medal of Honor. He died in 2023.
Where the credit landed
Ziv and Lempel are properly credited and the algorithms carry their initials, which is better than most in this wave manage. LZW — the Welch variant used in GIF — was patented by Unisys, and enforcement of that patent in the 1990s caused significant disruption on the early web and directly motivated the creation of PNG.
Pro Tips
- The dictionary is the data already seen, so nothing needs transmitting with it.
- "Universal" means it adapts without knowing the source statistics in advance.
- The LZW patent dispute is why PNG exists.
Knowledge Base
What You'll Learn
Dictionary matching then entropy coding is the standard shape of lossless compression.
Why LZ and Huffman are used together
They exploit different redundancies. LZ finds repeated sequences and replaces them with back-references; Huffman exploits uneven symbol frequencies in whatever remains. Running LZ first and Huffman second captures both, which is exactly what DEFLATE — the algorithm inside ZIP, gzip and PNG — does.
Where This Fits
This guide covers one specific part of the history of media technology. The wider picture — how each link in the chain from capture through transmission to display was actually built, who built it, and why the credit so often landed somewhere else — is in A History of Broadcast Technology: The Chain From Capture to Screen, which frames the discipline as a whole and links out to the detailed guides underneath it, including this one. If you are starting from scratch rather than solving a specific problem, read that first and come back here.
FAQ
Q: What is LZ compression?
A: A family of lossless algorithms replacing repeated sequences with references to their earlier occurrences, building the dictionary from the data itself so nothing needs transmitting alongside.
Q: Why does PNG exist?
A: Largely because Unisys enforced its patent on the LZW variant used in GIF during the 1990s. PNG was created as a free, unencumbered alternative.