Shannon measures information
Claude Shannon, at Bell Labs, shows that a message holds a measurable amount of surprise, which he calls entropy. Whatever is predictable can be left out and rebuilt. Whatever is not sets a floor that no scheme will ever get under.
A parlour game with a purpose
Shannon has people guess a sentence one letter at a time and counts their mistakes. English, he concludes, carries about one bit a letter to somebody who can read it. Compressing and predicting turn out to be one problem.
Huffman writes a term paper
Offered a choice between a final exam and an essay, an MIT student named David Huffman takes the essay and finds the best possible way to give short codes to common symbols. It is still inside almost every file you own.
A way to describe a square
Nasir Ahmed, T. Natarajan and K. R. Rao publish the discrete cosine transform, which describes a block of signal as a sum of smooth waves. In natural sounds and pictures a handful of those waves carry nearly everything.
Lempel and Ziv point backwards
Why write a phrase twice when you can say “the same as forty characters ago”? Jacob Ziv and Abraham Lempel turn repetition itself into the code. ZIP, PNG and gzip all descend from them.
Photographs for everyone
JPEG cuts a picture into squares of eight dots by eight, transforms each one, and rounds off the fine detail the eye forgives. A photograph shrinks tenfold and the web gets its pictures.
Music down a telephone line
MPEG-1 Layer III, soon known as MP3, works out what the ear cannot hear behind louder sounds and discards it. In the same year gzip joins Lempel and Ziv's pointers to Huffman's codes and quietly becomes the default for everything else.
A rabbit is measured
At Stanford, Greg Turk and Marc Levoy stitch laser scans of a clay rabbit into a single surface of 69,451 triangles. It becomes the object on which a generation of methods for shrinking shapes is tried out.
Sorting as compression
bzip2 puts the Burrows–Wheeler transform to everyday use. Shuffle a file so that similar passages sit together, and it becomes far easier to code. Two years later LZMA gives Lempel and Ziv a long memory and a finer coder, and it lives on in 7-Zip and xz.
Video reaches the internet
H.264 predicts each block of a frame from its neighbours and from earlier frames, then sends only the mistake. Two decades on it is still the format everything can play, and the one every newcomer is measured against.
A genome as an email attachment
A team at the University of California, Irvine stores James Watson's genome as a list of its differences from a reference. Three billion letters come down to about four megabytes.
A new way to write fractions of a bit
Jarosław Duda describes asymmetric numeral systems, which code nearly as tightly as arithmetic coding at nearly the speed of Huffman. Within a few years the method is inside Zstandard, and from there in operating systems, browsers and data centres.
One codec for speech and music
A speech coder from Skype and a music coder from the Xiph.Org Foundation are joined into one open standard, Opus. It handles a whisper on a bad connection and an orchestra on a good one, and it is what your calls and your browser use today.
A fork in the road
HEVC promises to halve the bitrate of H.264 and arrives tangled in patent licences from several competing pools. Google answers with VP9, which is free. Two years later browser makers, chip makers and streaming services found the Alliance for Open Media.
One bit for a timestamp
Engineers at Facebook publish Gorilla, the store that keeps their monitoring data in memory. By saving only how each reading differs from what was expected, it fits 96 per cent of its timestamps into a single bit each.
Lossless, rebuilt for speed
Two new general-purpose compressors go into wide use within months of each other. Zstandard unpacks at more than a gigabyte a second. Brotli squeezes the text of the web harder than gzip ever could.
An open codec for moving pictures
The Alliance for Open Media publishes AV1, with every tool of the previous generation enlarged and several new ones, free to use. It asks far more arithmetic of the encoder and repays it with the same picture in far fewer bits than H.264, often about half.
The photograph catches up
Take a single frame of AV1, put it in a file, and call it a photograph. That is AVIF. A quarter of a century after JPEG, still pictures inherit what video learned in the meantime.
The new codec reaches silicon
A codec is only as useful as the chips that can run it. Within a single year Intel, NVIDIA and AMD all sell graphics cards with AV1 encoders built in, and what took a server farm in 2018 can be done live on a desk.
The guessing is handed to machines
Researchers at DeepMind show that a language model trained only on text can compress photographs and speech better than the formats designed for them, provided nobody counts the size of the model. The oldest idea in the field has become the newest.