Huffman coding explained
Computers usually store every letter in the same number of bits, eight in plain ASCII. That is simple but wasteful, because some letters are far more common than others. In 1951 a student found the best way to give each symbol a code of its own length, frequent symbols short and rare ones long, with a construction so simple it fits in a few lines. Huffman coding is now inside almost every compressed file, image and sound you open.
Short codes for common symbols
Morse code already used the idea in the 1830s: E, the commonest letter in English, is a single dot, while Q is dash dash dot dash. A code like that saves time and space whenever some symbols occur more often than others. But variable lengths raise a problem Morse solved with pauses: how do you know where one code ends and the next begins? And which lengths should each symbol get to make the total as small as possible?
Prefix codes
The first problem disappears if no code is the beginning of another one. With the codes A = 0, B = 10, C = 110 and D = 111, the bits 0101100 can only be read as A B C A: as soon as the bits read so far form a code, that code is complete. Such prefix codes correspond exactly to binary trees with the symbols at the leaves, where each left branch stands for 0 and each right branch for 1. Choosing a code is choosing a tree.
Huffman's construction
Start with one leaf per symbol, weighted by how often it occurs. Take the two lightest trees and join them under a new node whose weight is their sum, and repeat until a single tree is left. That is the whole algorithm. Rare symbols are joined first and end up deep in the tree, with long codes; common ones are joined last and stay near the top, with short codes. With a priority queue it takes time proportional to n log n for n symbols.
Why it is optimal
In a best possible tree, the two rarest symbols can always be placed as siblings at the deepest level: swapping them with whatever is there can only shorten the total. Join them into one symbol with their combined weight and the rest is the same problem with one symbol fewer, so the greedy step never closes off the best answer. The total number of bits used equals the sum of the weights of all the inner nodes, which the joining keeps as small as possible.
A term paper instead of an exam
In 1951 David Huffman, a graduate student at MIT, took Robert Fano's course on information theory. Fano gave his students a choice: sit the final exam or write a term paper on finding the most efficient binary code. Huffman nearly gave up on the paper, then saw that building the tree from the bottom up, rather than splitting from the top down as in the Shannon–Fano method, always gives the best result. He published it in 1952; the student's method beat the one his professor had worked out with Claude Shannon.
Close to the entropy
Claude Shannon showed that no code can use fewer bits per symbol, on average, than the entropy of the source. A Huffman code reaches the entropy exactly when every probability is a power of one half, and is never a full bit per symbol above it. The gap matters when one symbol is very common: a symbol with a 99% share still needs at least one whole bit, although it carries only about 0.015 bits of information. Arithmetic coding and the asymmetric numeral systems of newer compressors avoid that limit.
Huffman codes everywhere
Huffman coding is rarely used alone but forms the last stage of many formats. Deflate, inside ZIP, gzip and PNG, first replaces repeats with references and then writes the result with Huffman codes. JPEG uses them for the numbers left after its transform of the image, MP3 for its audio data, and fax machines for the lengths of black and white runs. Formats usually send a canonical Huffman code, in which only the code lengths need to be stored, because the codes themselves can be rebuilt from them.
Explore it
Open the Huffman coding builder to build the tree of ABRACADABRA, MISSISSIPPI RIVER, a sentence of your own or any other text, one step at a time. Watch the two lightest trees join at every step, click a leaf to see its code, follow a symbol through the encoded bits, and compare the total with a fixed-length code, UTF-8 and the entropy.
Frequently asked questions
What is the difference between Huffman and Shannon–Fano coding?
Shannon–Fano coding builds the tree from the top, splitting the symbols into two groups of nearly equal weight again and again. It is often good but not always optimal. Huffman builds the tree from the bottom by joining the two lightest trees, and always gives the shortest possible prefix code.
Does the decoder need the tree?
Yes, it needs the same code. Compressed files therefore store it, usually as a list of code lengths for a canonical code, which takes only a few dozen bytes. For short texts that overhead can outweigh the saving; the builder counts only the encoded bits.
Can Huffman coding make a file larger?
The encoded symbols never take more bits than a fixed-length code for the same symbols. But the code table has to be stored too, so for very short or nearly random data the result can be slightly larger than the original.
What does the Kraft inequality say?
That a prefix code with code lengths l₁, l₂, … exists exactly when the sum of 2 to the power −l over all symbols is at most 1. For a complete tree, such as every Huffman tree with at least two symbols, the sum is exactly 1.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Open the Huffman coding builder