Compression and Information

A file holds as much information as it has surprise, and usually far less than its size. English text stored at 8 bits a character carries only a bit or two of real information per character, so it compresses several times over. A file of random bytes carries 8 bits in every byte and cannot be compressed by anyone, ever.

What follows is the intuition for that limit, the two tricks every lossless compressor uses, and the price of choosing one. Every number on it was measured with Python 3.15's zlib module on data generated for the page: a 10.5-megabyte web access log, 4.8 megabytes of JSON records, the 47 kilobytes of English prose in this book's first chapter, and 10.5 megabytes of random bytes.

Information as Surprise

A fair coin flip carries 1 bit of information: before it lands, heads and tails are equally likely. A coin that lands heads 99 times in 100 carries far less, about 0.08 bits a flip, because the outcome is rarely a surprise. Claude Shannon's entropy measures that average surprise per symbol, and it is also the smallest average number of bits any code can spend per symbol.

Counting letter frequencies alone, the prose of Chapter 1 has an entropy of 4.45 bits per character, well under the 8 it is stored in. Context lowers it much further. In a 1951 paper, Shannon had people guess English text letter by letter and estimated its entropy at roughly 0.6 to 1.3 bits per letter, because after "compres" the next letter is nearly certain. The gap between 8 stored bits and the true content is what compression removes.

Shorter Codes for Common Symbols

The first trick gives frequent symbols short bit patterns and rare ones long patterns. Huffman coding, published in 1952, builds the best such code for known frequencies by repeatedly merging the two least frequent symbols into one node, a greedy choice that Chapter 9 shows is provably optimal. The codes are chosen so that no code is the start of another, so the bit stream decodes without separators.

In "abracadabra", a appears five times, b and r twice, c and d once. The two rarest, c and d, merge first, then b and r, then those two groups, and a joins last. The result gives a 1-bit code to a and a 3-bit code to every other letter: 23 bits for the whole word, against 33 for a fixed 3-bit code and 88 for ASCII.

Back-References for Repeats

The second trick replaces a repeated run with a pointer to an earlier copy: "go back 300 bytes and copy 40". This is why logs, JSON and HTML compress so well: the same keys, paths and phrases recur on every line. DEFLATE, the method inside gzip, zip and PNG, combines back-references with Huffman coding of what remains. Newer compressors make different trades between speed and ratio: zstd uses the same two ideas with a faster coder for the symbols, and lz4 keeps only the back-references, for speed.

The measured ratios follow the repetition. The access log shrank 7.34 times at zlib's default level, the JSON records 4.11 times, and the English prose 2.80 times, reaching 2.86 bits per character: better than letter frequencies alone, because of repeated words, and nowhere near Shannon's estimate, because zlib does not understand English. The random bytes did not shrink at all.

Why Random Data Does Not Compress

The argument is short. There are 2 to the n possible files of n bits. The number of files shorter than n bits, counting every length from zero up to n minus 1, is 2 to the n minus 1: one fewer. A compressor that shrank every n-bit file would have to map 2 to the n different inputs onto fewer outputs, so two inputs would share an output and could not both be recovered. Therefore any method that shrinks some files must leave others the same size or grow them.

Real compressors shrink the files people make, which are full of patterns, and pay on the files with none: random bytes, encrypted data and already-compressed files. Measured, zlib turned 10.5 megabytes of random bytes into 3,221 bytes more than it started with. Compressing the already-compressed log a second time made it 446 bytes bigger.

Lossless and Lossy

Lossless compression returns every bit: archives, logs, source code, database pages and network payloads. Lossy compression, in JPEG, MP3 and video codecs, discards detail a person is unlikely to notice, such as fine colour variation or sounds masked by louder ones, and in exchange reaches ratios lossless methods cannot.

Lossy is only for media a person consumes, never for data a program reads back. A number, a record or a line of code with a detail discarded is wrong.

What Compression Costs

Compression trades CPU for bytes, and the trade gets steep at the top. On the access log, level 1 reached 5.67 times in 43 milliseconds, level 6 reached 7.34 times in 133, and level 9 reached 7.86 times in 346: two and a half times the CPU of the default for 7 percent smaller output. Decompression took about 7 milliseconds at every level, some twenty times faster than compressing at the default, which is why data written once and read many times can afford a slow, high-ratio setting.

Small payloads can grow: a gzip wrapper adds at least 18 bytes of header and trailer, so the five bytes "hello" become 25. Encrypted data looks random, so compression has to happen before encryption or not at all, and compressing secrets together with text an attacker controls lets the attacker learn the secret from the compressed length, which the CRIME and BREACH attacks of 2012 and 2013 did to web traffic. Finally, decompression is where the ratio turns hostile: one layer of DEFLATE turned 1 gigabyte of zeros into about a megabyte, and nested archives multiply those layers, so the well-known 42.zip is about 42 kilobytes and expands to about 4.5 petabytes. An upload endpoint that decompresses without a limit is a denial-of-service vector.