Nothing Lost
“The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point.”
Claude Shannon, 1948
Some things cannot afford to lose anything. A program with one wrong character does not run, and a bank statement with one wrong digit is a different bank statement.
Everything in this room comes back exactly as it went in. The only question is how few marks it takes to write it down.
Start with a coin. Toss it a thousand times and write down what happens, a mark for heads and a mark for tails.
A fair coin gives you no help. A thousand tosses take a thousand marks.
Now load the coin. Drag it towards heads and watch the number.
The more lopsided the coin, the more of its tosses you could have guessed. What can be guessed does not need saying.
In 1948 Claude Shannon, an engineer at Bell Labs, gave this quantity a name and a unit. The entropy of a source is how much it can still surprise you, measured in bits.
It is a floor. No method, however ingenious, writes the message in fewer bits than its entropy.
Words are a loaded coin with many sides. This is the opening of A Tale of Two Cities.
You can type over it. Everything else in this room will work on your text.
Count the letters. The space and the letter e turn up constantly, and a few letters hardly at all.
Alfred Vail, who worked with Samuel Morse, is said to have counted the type in a printer's case to find this out. Their code gave e a single dot.
In 1951 a student at MIT, David Huffman, was offered a choice between a final exam and a term paper. He chose the paper, and in it found the best possible way to hand short codes to common letters.
Follow any letter down from the top. Each turn to the left is a 0 and each turn to the right is a 1. Common letters sit near the top and get short codes.
Your text now costs 4.06 bits a letter instead of 8.
Shannon's floor for it is 4.03. Huffman cannot go under that while it treats each letter on its own.
Letters do not come on their own. They come in words, and words come back.
In 1977 Jacob Ziv and Abraham Lempel replaced each repeated stretch with a note saying how far back to look and how much to copy. Point at a highlighted stretch to see where it came from.
Put the two together, pointers first and short codes for whatever is left, and you have gzip. Since 1993 it has been inside almost everything.
Your browser carries one. This is what it makes of your text.
Every compressor since is some arrangement of those ideas, and each strikes its own bargain between small and fast.
Here six of them work on the same 212 MB of real files: novels, a database, program code, medical scans, a star catalogue. Higher is smaller. Further right is faster.
gzip is in the place nobody would now choose. Newer designs are smaller and faster at once.
LZ4 gives up size to move data nearly as fast as memory can be copied. xz takes its time and wins on size. Zstandard covers most of the range with one format, which is why it has spread so far.
How far a file shrinks depends on the file.
A chemical database full of repeated patterns folds up 22 times over. An X-ray, which is mostly fine grain, only halves.
Two last files, sixteen million bytes each. The first is nothing but noughts.
It holds no surprise at all, and it shrinks to almost nothing.
The second is pure chance. It is all surprise.
Every compressor here makes it slightly bigger.
That is the wall Shannon described in 1948, and no lossless method will ever get through it.
Sound and pictures are full of fine detail that looks like chance. To make them small, something has to be given up.