How Does File Compression Work?
A zip file is smaller than what went into it, and nothing was thrown away. The trick is that ordinary data is far more predictable than the way we normally write it down.
Why shorter codes for commoner letters wins
Junior level — plain language, no maths
Normally every letter you store takes the same amount of room - eight bits each, whether it is an e or a q. That is convenient and it is also wasteful, because those two letters are not equally common. In English, e turns up about a hundred times more often than q. Giving them the same amount of space is like using the same size box to post a sofa and a postcard.
So do the obvious thing: give the common letters short codes and the rare ones long codes. Give e three bits and let q have eleven. You lose a little on every q and save a little on every e, and since there are vastly more e's than q's, the total comes out smaller. Nothing has been thrown away - every letter is still there, exactly as it was.
There is one problem to solve. If codes have different lengths, how do you know where one stops and the next begins? The answer is to make sure no code is the beginning of another code. If 10 is a whole letter, then no other code may start with 10. A method called Huffman coding builds exactly that, by repeatedly gluing together the two rarest letters and working upwards - which automatically puts the rare ones deep in a tree and the common ones near the top.
Play with the repetition slider and watch the bars. The more predictable your message, the more there is to save. A page of the same letter compresses to almost nothing. A page of pure randomness compresses to nothing at all, and that turns out to be a deep fact rather than an inconvenience.
Things worth knowing
- In English text, the six commonest letters - e t a o i n - make up about 40% of everything written. That imbalance is the entire source of the saving.
- Morse code is a hand-made version of the same idea: E is a single dot, Q is dash-dash-dot-dash. Samuel Morse counted letters in a printer's type case to work out which should be short.
- A file of genuinely random numbers cannot be compressed at all. If a program claims to shrink any file, it is wrong - there are simply not enough short files to hold all the long ones.
Entropy, prefix codes, and the line between lossless and lossy
Student level — the core equations
The quantity being exploited has a name and a number. Shannon entropy measures the average information per symbol: \(H = -\sum p_i \log_2 p_i\) bits. For English letters with their real frequencies it is about 4.1 bits per character rather than the 8 you spend storing them naively - and if you account for the fact that q is almost always followed by u, it falls to roughly 1.5 bits per character. Entropy is the floor: no lossless method can average fewer bits per symbol than the source's entropy, and Huffman coding gets within one bit of it.
Huffman's algorithm is a greedy build from the leaves. Take the two least frequent symbols, merge them into a node whose weight is their sum, put it back in the pool, repeat until one node remains. Reading the tree from the root, a left branch is a 0 and a right branch a 1, and because every symbol is a leaf, no code is a prefix of another - the decoder can walk the tree bit by bit and always knows when it has arrived.
Real formats layer more tricks on top. Run-length encoding replaces repeats with a count. LZ77, the heart of ZIP and PNG and gzip, replaces a repeated chunk with a backwards reference - go back 214 bytes and copy 9 - which is why text and code compress so well and why a file compressed twice barely shrinks the second time. DEFLATE is simply LZ77 followed by Huffman.
All of that is lossless: the original comes back bit for bit. Photographs and music use lossy methods instead, which throw away information the eye or ear does not notice - JPEG transforms each 8×8 block of pixels into frequencies and coarsens the high ones, MP3 discards sounds masked by louder neighbours. That is why a JPEG saved repeatedly degrades and a ZIP never does.
Key Formulas
| Entropy | \(H = -\sum_i p_i \log_2 p_i\) | bits per symbol, the hard floor |
|---|---|---|
| Ideal code length | \(\ell_i = -\log_2 p_i\) | rarer symbol, longer code |
| Huffman bound | \(H \le \bar{\ell} < H + 1\) | |
| Compression ratio | \(R = \dfrac{\text{original bits}}{\text{coded bits}}\) | |
Things worth knowing
- Huffman coding is provably optimal among methods that give each symbol a whole number of bits. Arithmetic coding beats it by escaping that constraint and encoding the whole message as a single fractional number.
- Compressing an already-compressed file usually makes it slightly bigger, because the container adds headers to data that has no redundancy left to remove.
- PNG is lossless and JPEG is lossy, which is why screenshots belong in PNG and photographs in JPEG. Saving a screenshot as JPEG produces visible fringes around the text for no saving worth having.
Kolmogorov complexity, the counting argument, and modern compressors
Scholar level — full mathematical depth
01Why no compressor can shrink everything
The proof is a counting argument and it takes one line. There are \(2^n\) strings of length \(n\) but only \(2^n - 1\) strings shorter than \(n\). Any lossless compressor is an injection, so it cannot map every string of length \(n\) to a shorter one - some inputs must grow. Compression is therefore never a property of an algorithm alone; it is a bet on the distribution of inputs. A good compressor is one whose implicit model matches the data it is actually given.
02Compression is prediction
Arithmetic and range coders sever the link between symbol and whole bits, encoding a message as a single number in \([0,1)\) whose interval is narrowed by each symbol in proportion to its probability. The consequence is that the modelling and the coding become separate problems, and all the remaining gain is in the model. Context mixing compressors such as PAQ run hundreds of predictive models in parallel and blend them with a neural network; the best text compressors today are, functionally, language models. The equivalence runs both ways: a model that predicts the next token well is a compressor, and compression ratio is a legitimate measure of how well a model understands its data.
03Kolmogorov complexity
The theoretical limit for a particular string is the length of the shortest program that outputs it, \(K(x)\). A string with structure - a billion digits of π - has tiny Kolmogorov complexity despite enormous entropy under any symbol model, because a short program generates it. The catch is that \(K\) is uncomputable: no algorithm can find the shortest program in general, a result that follows from the halting problem. Practical compression is the search for computable approximations to an uncomputable ideal.
04What the modern formats actually do
Zstandard pairs an LZ77-style matcher with finite state entropy, an implementation of asymmetric numeral systems that reaches arithmetic-coding efficiency at table-lookup speed - a genuine advance, since for thirty years the choice was between fast and small. Brotli ships a 120 kB dictionary of common web strings, so short HTTP responses compress against text they never contained. For images, AV1 intra-frame coding underlies AVIF and beats JPEG by roughly half at equal perceived quality, using directional intra-prediction rather than relying on the transform alone.
05Lossy coding as rate-distortion
Formally, lossy compression is the rate-distortion problem: minimise bit rate subject to a distortion bound, where distortion is defined by a perceptual model rather than by squared error. JPEG's quantisation matrix is a hand-tuned model of contrast sensitivity - the eye's falling response to high spatial frequencies - and the modern successors replace hand tuning with learnt perceptual metrics. The important conceptual point is that the discarded information is chosen by a model of the observer, which is why a codec tuned for human eyes damages a medical image in ways a radiologist will notice.
Key Formulas
| Counting bound | \(|\{x : |x| = n\}| = 2^n > 2^n - 1 = |\{y : |y| < n\}|\) | |
|---|---|---|
| Kolmogorov complexity | \(K(x) = \min\{|p| : U(p) = x\}\) | uncomputable |
| Arithmetic coding | \(\text{length} \approx \left\lceil -\log_2 \prod_i p(x_i) \right\rceil + 2\) | |
| Rate-distortion | \(R(D) = \min_{p(\hat{x}|x):\,\mathbb{E}[d] \le D} I(X;\hat{X})\) | |
Things worth knowing
- Kolmogorov complexity is uncomputable, and the proof reduces to the halting problem. Berry's paradox - "the smallest number not describable in fewer than twelve words" - is the same idea in English.
- The Hutter Prize pays for compressing a fixed 1 GB extract of Wikipedia, on the explicit thesis that better compression of text is equivalent to better understanding of it.
- Asymmetric numeral systems, published in 2009, gave arithmetic-coding compression at Huffman-like speed and is now inside Zstandard, LZFSE and AV1. It is one of the rare genuinely new ideas in a mature field.