Huffman Coding

Lossless text compression by Huffman coding. Frequent characters get short binary codes and rare ones long codes, and no code is a prefix of another, so the compressed stream decodes back to the original with no ambiguity.

The codes come from a binary tree built bottom up. Start with one leaf per character, keyed by its frequency, and repeatedly merge the two lowest-frequency nodes under a new parent whose frequency is their sum, until a single tree remains. Reading the tree root-to-leaf — 0 for a left branch, 1 for a right — gives each character its code.

Because every symbol lands on a leaf, no codeword is a prefix of another, and the compressed stream needs no separators between symbols. Decoding walks the tree from the root, branching left on a 0 and right on a 1; the moment it reaches a leaf it emits that symbol and jumps back to the root. Each input bit is read once, so decoding is linear in the length of the stream.

The greedy choice turns out to be optimal, and the reason is structural. A prefix code is exactly a labeling where every character is a leaf, so no code sits on the path to another. The cost of a tree is the expected code length

where $\ell (c)$ is the depth of leaf $c$. Merging the two rarest symbols first is safe because they can always be pushed to the deepest level of some optimal tree without raising $\bar{L}$; induction on the merges then gives a globally optimal code. No prefix code beats it.

The theoretical floor sits just below that. Shannon's source coding theorem sets the entropy

as the average number of bits per symbol no lossless code can undercut, where $p[c]$ is the symbol's probability. Huffman coding lands within one bit of it,

the slack being the cost of using a whole number of bits per symbol when the ideal length $-{\log }_{2}p[c]$ is usually fractional. The gap shrinks to nothing when the probabilities are exact powers of $\frac{1}{2}$, and it is amortized away in practice by coding blocks of symbols at once.