Lossless compression

How can a file be made smaller with nothing at all thrown away?

A text file shrinks to a third of its size and comes back byte-for-byte identical. That sounds like getting something for nothing, and the natural first response is to ask where the limit is — if a third, why not a hundredth, and why not again on the output? So the useful question is not "how does it work" but "what stops it", because whatever stops it will explain what it was doing in the first place.

Begin with the strongest possible version of the doubt. Could there be a compressor that makes every input at least one bit shorter?

No, and the proof is two lines of counting. To be lossless, the compressor must be reversible: two different inputs can never produce the same output, or the decompressor could not know which one to restore. Now take all inputs of exactly 8 bits. There are 256 of them. How many distinct strings shorter than 8 bits exist? Lengths 0 through 7 give 1 + 2 + 4 + … + 128 = 255. Two hundred fifty-six distinct things cannot map to two hundred fifty-five distinct slots without a collision. So at least one 8-bit input does not get shorter. The same argument runs at every length.

Sit with what that means. Every lossless compressor expands some inputs. This is not a flaw in the algorithm; it is arithmetic. The gain is always a redistribution: shorter codes for some inputs, paid for by longer codes for others. A compressor is therefore a bet — a claim that the files you will actually feed it are drawn from a small, predictable corner of the space of all possible files. Which is true, spectacularly so. English prose, source code, spreadsheets and log files are wildly non-uniform; the astronomically many byte-strings that look like noise are files nobody ever has.

So the question becomes: how much can you win on that bet? Shannon answered it. Suppose the source emits symbols with known probabilities. The entropy of that source — the average, over symbols, of the log of one over each symbol's probability — is a lower bound on the average code length per symbol, and it is achievable to within a bit. A source that emits one symbol with certainty has entropy zero and needs no bits at all. A source emitting eight equally likely symbols has entropy 3 bits, and you cannot do better than 3 bits each, ever.

Now the practical routes, and there are two families, which attack different kinds of redundancy.

The first assigns short codes to frequent symbols. Huffman's construction from 1952 builds this optimally for a known symbol distribution, by repeatedly merging the two least likely items into a subtree, so rare things end up deep and frequent things shallow. Its one weakness is that it must spend a whole number of bits per symbol, which wastes a fraction when a symbol's ideal length is, say, 1.2 bits; arithmetic and range coding remove that constraint by encoding the whole message as a single number in an interval.

The second family exploits repetition rather than symbol frequency. Lempel and Ziv's methods replace a repeated stretch with a reference to where it appeared before — "go back 40 characters and copy 9". No symbol statistics are involved; what is being harvested is that real data repeats itself. The two families combine well, which is why the ubiquitous DEFLATE format runs a Lempel-Ziv pass and then Huffman-codes the result.

Notice what both families are really doing: modelling. Compression is prediction. The better your model predicts the next symbol, the less it costs to record which symbol actually arrived — and the residual, the surprise, is exactly what the entropy bound measures.

Three points keep the picture honest.

First, lossless and lossy are different contracts, not different settings of one dial. Lossless promises exact reconstruction and is bound by the counting argument above. Lossy formats — JPEG, MP3, most video — deliberately discard information judged imperceptible, which makes their mapping non-reversible and frees them from the bound entirely. That is how they reach ratios lossless methods cannot. There is no "lossless setting" that gets you lossy ratios; the difference is in what you agreed to give up.

Second, "it did not compress" is usually informative rather than a failure. A file that resists compression — already-compressed data, encrypted data, good random noise — is telling you it has little structure your compressor can model. Trying twice does not help; the output of a good compressor already looks close to random by construction.

Third, entropy is a property of a model of the source, not of an individual file. Change the model and the number changes. A text has one entropy if you treat letters as independent, a much lower one if you model letter pairs, and lower still with word context. The bound is real, but it is a bound relative to the assumptions you are willing to make — which is why compression research is largely the search for better models rather than better codes.

• Arithmetic coding, and how a message becomes a single number in an interval.
• Kolmogorov complexity: the shortest program that outputs a string, and why it is uncomputable.
• Why encrypted data is incompressible, and what that implies about compressing before encrypting.

Every term the collection defines is gathered in the glossary.