A Universal Algorithm for Sequential Data Compression
Don't repeat yourself — point back to the earlier copy. The idea inside every ZIP.
Every ZIP file, every web page, every PNG image owes its smaller size to one idea from 1977: instead of repeating yourself, point back to where you said it before.
The idea, unpacked
Real data repeats. The same words, the same patterns of code, the same runs of colour in an image — they come back again and again. Lempel and Ziv's insight was that you don't have to store a repeat at all. You can replace it with a tiny note: 'go back this many characters, and copy that many.' A note like that is far smaller than the text it stands in for.
The clever part is that the method learns the repetitions as it reads. It keeps a window onto the recent past, and whenever the text ahead matches something already inside that window, it swaps the match for a pointer. No dictionary has to be prepared in advance, and nothing extra has to be sent alongside — the receiver rebuilds everything from the pointers themselves.
Where it came from
The idea came from two Israeli engineers, Jacob Ziv and Abraham Lempel, working at the Technion in Haifa. Their 1977 paper in the IEEE Transactions on Information Theory laid out the sliding-window method; a 1978 follow-up gave a second version with a cleaner proof. Together the two papers are known simply as 'LZ' — LZ77 and LZ78 — and between them they became the backbone of almost all general-purpose compression. The authors weren't chasing a product; they were after a provably good answer to a theoretical question, and the practical revolution followed.
Why it mattered
Two things made it win. First, it is universal: you can point it at English, at Chinese, at program code, at sensor logs, at an image — anything — with no tuning, and it adapts on its own. Second, it isn't just a clever trick that happens to work; Ziv and Lempel proved it gets close to the theoretical best any compressor could do. 'Works on everything' plus 'provably near-optimal' is a rare combination, and it is exactly why the idea spread into every corner of computing.
An everyday analogy
Think of taking notes in a long meeting. The third time someone says the same long phrase, you don't write it out again — you scribble 'same as above' with an arrow. Or a knitting pattern that says 'repeat rows 2–5 four times' instead of printing twenty rows. LZ77 is that habit, made exact: every repeat becomes a precise arrow saying how far back to look and how much to copy.
Where it sits
This is the third corner of a triangle already in this Library. Claude Shannon (1948) proved how small data can be squeezed in principle. David Huffman (1952) found the best way to shrink individual symbols. Lempel and Ziv took on the part neither covered — repeated phrases — and the dominant real-world coder, DEFLATE, runs LZ77 and Huffman back to back, so all three ideas literally cooperate inside the gzip and PNG you use every day.
A universal algorithm for sequential data compression is presented. Its performance is investigated with respect to a nonprobabilistic model of constrained sources. The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable-to-block codes designed to match a completely specified source.