Compression works by spending short codes on the things that happen often and long codes on the things that do not. That is the whole idea, and Claude Shannon showed in 1948 exactly how far it can go: there is a number, measured in bits per symbol, below which no lossless scheme can ever get. Everything below is computed from whatever you type into the box — the frequencies, the tree, the actual bits. At the end is the short and slightly annoying proof that a compressor which shrinks every possible file cannot exist.
A symbol that turns up half the time carries one bit. One that turns up a quarter of the time carries two. In general a symbol of probability p carries −log₂p bits, and the entropy is just the average of that over everything you might see. It is the honest lower bound: no lossless code can beat it, ever. Type something very repetitive and watch it fall toward zero; type something with every symbol equally likely and it climbs to log₂ of the alphabet size, which is the worst case.
Huffman coding is embarrassingly simple: take the two rarest symbols, join them under a new node whose weight is their sum, put it back in the pile, repeat until one tree is left. Left branch is 0, right is 1, and every symbol gets the path to its leaf. The result is provably the best possible code that assigns whole numbers of bits — and that "whole numbers" is exactly why it cannot quite reach the entropy. The gap is below one bit per symbol, always.
| symbol | times | share | ideal bits | Huffman code | bits used |
|---|
The simplest compressor of all: instead of writing a symbol twenty times, write "20" and then the symbol. On a run of identical values it is spectacular. On alternating values it is a disaster — it makes the data twice as long, because every run has length one and you are now storing a count for each of them. This is not a flaw in run-length encoding. It is the counting argument in section 4 showing up early: any scheme that shortens some inputs must lengthen others.
Suppose a lossless compressor shrinks every file by at least one bit. There are 2n files of length n, and only 2n − 1 possible shorter files of every length below n put together. So two different inputs must produce the same output, and you cannot decompress them both. That is the whole proof. Worse, the good cases are rare: at most one file in two can save even a single bit, one in 1024 can save ten, and one in a million can save twenty. Compression works only because the files people actually care about are a vanishingly small and very unusual corner of all possible files.
| you want to save | at most this fraction of files can | which is |
|---|
Counting letters one at a time gives 4.18 bits per letter for English. Real compressors get nowhere near that badly — because letters are not independent. After a q comes a u. After "th" comes e about a third of the time. Once you condition on what came before, the uncertainty collapses: Shannon estimated by experiment in 1951 that English carries only about 1.1 bits per letter to someone who knows the language, and modern language models get close to that. The bars below measure exactly that collapse on your own text.
Everything responds to the box at the top. The entropy is −Σ p log₂ p over the symbols actually present; the Huffman tree is built by the real algorithm and the bit string shown is the genuine encoding of your text with that tree. Two checks that the implementation is honest: on the standard English letter frequencies the entropy comes out at 4.1758 bits per letter against a uniform alphabet of 26 at log₂26 = 4.7004, and the Huffman code averages 4.2051 bits — which satisfies Shannon bound H ≤ L < H+1 with 0.0293 bits of overhead. The Kraft sum of 2^−(code length) over all codes comes to exactly 1, as it must for a complete tree.
Three ways these numbers flatter themselves. First, the compressed sizes here exclude the dictionary: to decompress, you also need the tree, which for a short sentence can easily be larger than the message. That is why nobody Huffman-codes a tweet. Second, the conditional entropies in section 5 are measured on your text, and with only a few hundred characters they are badly biased downward — with enough context every sequence looks perfectly predictable in hindsight, so a short input can appear to reach near zero bits per letter while carrying no real predictability at all. Shannon 1.1 bits came from human experiments on unseen text, which is a much harder test. Third, Huffman is not what your computer actually uses: modern compressors combine a dictionary method that spots repeated phrases, not just repeated symbols, with arithmetic coding that escapes the whole-number-of-bits restriction, and the best of them use neural networks to predict the next symbol. The lower bound in section 1 still holds over all of them. It is just that the true entropy of real data is far lower than counting single letters can ever reveal.