Making It Smaller

Every exact compressor does two things. It replaces a run that has appeared

before with a short reference to where it appeared, and it gives the commonest

symbols shorter codes than the rare ones. Both are ways of removing repetition,

and neither invents anything.

So whether a file shrinks is a question about the file. English text repeats

heavily, in letters, in words and in phrases, and compresses to about a third.

A table of a column's worth of the same country code repeated a million times

compresses to almost nothing. A file of already compressed video has had its

repetition removed already and will not shrink again, and a file of random bytes

has no repetition to remove and cannot shrink at all.

These are rough figures from ordinary files rather than measurements of

anything in particular, and the shape is what matters. The second row is why

the previous lesson and this one belong together: a column holds values of one

kind, so values next to each other repeat, and the same table written column by

column compresses several times better than the same table written row by row.

The last row is the honest limit. Nothing shrinks random data, and any claim to

the contrary is a claim to have got something from nothing.

The last row deserves one more sentence, because it is a proof rather than an

observation. If a method shrank every file, then applying it repeatedly would

shrink every file to one byte, and one byte cannot be unpacked into every

possible file. So any compressor makes some inputs larger, and the ones it makes

smaller are exactly the ones with repetition in them.