Huffman Coding
Frequent letters deserve shorter codes. Type a string, merge the two rarest symbols again and again, and watch a Huffman tree grow whose codeword lengths land within a bit of the entropy floor.
Huffman Coding
Spend fewer bits on the letters you use most and you can shrink text below its fixed-width size, with no separators marking where one code ends and the next begins. Huffman coding finds those codes by a stubbornly simple rule: count each character, then keep merging the two rarest nodes until one tree remains. Reading 0 for every left branch and 1 for every right gives each symbol a prefix-free codeword, no codeword the start of another, and it is provably as short as any such code can get.
English text: a handful of common letters dominate, so Huffman shaves real bits.
| Symbol | Freq | Codeword | Bits | Total |
|---|---|---|---|---|
| space | 8 | … | — | — |
| o | 4 | … | — | — |
| e | 3 | … | — | — |
| h | 2 | … | — | — |
| r | 2 | … | — | — |
| t | 2 | … | — | — |
| u | 2 | … | — | — |
| a | 1 | … | — | — |
| b | 1 | … | — | — |
| c | 1 | … | — | — |
| d | 1 | … | — | — |
| f | 1 | … | — | — |
| g | 1 | … | — | — |
| i | 1 | … | — | — |
| j | 1 | … | — | — |
| k | 1 | … | — | — |
| l | 1 | … | — | — |
| m | 1 | … | — | — |
| n | 1 | … | — | — |
| p | 1 | … | — | — |
| q | 1 | … | — | — |
| s | 1 | … | — | — |
| v | 1 | … | — | — |
| w | 1 | … | — | — |
| x | 1 | … | — | — |
| y | 1 | … | — | — |
| z | 1 | … | — | — |
Finish building the tree to read off the codewords.
The greedy merge is optimal. At each step the two least frequent symbols can be placed as deepest siblings without loss, because any optimal tree can be rearranged so they sit there. Merging them into one node of summed frequency and recursing on the smaller problem builds the shortest possible average code.
Prefix-free means uniquely decodable. Every symbol lives at a leaf, so no codeword is a prefix of another. A decoder walks the tree from the root, turning left on 0 and right on 1, and emits a symbol the instant it reaches a leaf. No commas, lengths, or escape characters are needed in the stream.
Entropy is the floor. The source entropy H is the average information per symbol. No prefix-free code can beat it, and Huffman gets within one bit of it. The gap shrinks toward zero when probabilities are close to powers of one half, or when you Huffman-code blocks of symbols at once.