The encyclopedia · Engineering & Operations · Technical decision · 1977
Ziv and Lempel compressed data by pointing back to text already sent
LZ77 shrank data with 'go back N and copy L symbols' instead of a pre-agreed codebook, making compression universal.
Technion — Israel Institute of Technology
the move
Classical compression centered on Huffman coding, but Huffman needs a symbol-probability model built before it can code. Until 1977, most work assumed that model had to come from somewhere.
In 'A Universal Algorithm for Sequential Data Compression', Jacob Ziv and Abraham Lempel at the Technion showed the model could be dropped. The encoder keeps a window of recently seen text and matches the incoming look-ahead buffer against it; a match is written as an offset and a length, so repetition costs almost nothing.
The result is a universal scheme — it compresses any source with no prior statistics, because the dictionary is the data itself. The 1977 paper is the classic that made dictionary compression the basis of gzip, PNG and the ZIP family.
why it works
- Using the already-sent text as the dictionary needs no pre-computed probability table.
- A single offset-plus-length token handles any repeated phrase, long or short.
- The scheme works on unknown sources, so it is universal rather than tuned to a file type.
what transfers
Don't build a model of the data in advance; let the data supply its own structure as you go. A self-referential representation adapts to any input, no matter what it is.
what came after
The LZ approach became the foundation of modern lossless compression: LZ77 and its descendant LZ78/LZW power gzip, zip, PNG and the DEFLATE stream used across the web. Ziv and Lempel's papers earned the IEEE Information Theory Society's 1997 Golden Jubilee Technological Innovation Award.
references
- A universal algorithm for sequential data compression
- The Data Compression Book — Chapter 8: Sliding Window Compression
spotted an error? The archive wants to know.