Every letter you type is stored as the same number of bits. In ASCII that is 8 bits for an e and 8 bits for a z, even though e shows up constantly and z almost never. That is wasteful, and a graduate student found the fix in 1951.
Morse code already had the idea: the very common letter E is a single dot, while rare letters like Q get four symbols. If frequent symbols get short codes and rare symbols get long ones, the total length of a message drops.
There is a catch. If E were 0 and T were 01, then the bits 01 could mean "E then something" or "T". Morse solves this with pauses. A computer has no pauses, so the codes must be prefix-free: no code may be the beginning of another. Then a stream of bits can only be read one way.
A binary tree guarantees this. Put the symbols at the leaves, read 0 for "go left" and 1 for "go right", and the path to each leaf is its code. No leaf sits on the path to another leaf, so no code can be a prefix of another.
The question is which tree gives the shortest total message. In 1951, David Huffman was a doctoral student at MIT in Robert Fano's information theory class. Fano offered a choice: take the final exam, or write a term paper on finding the most efficient binary code. Huffman could not prove that any code he found was the best, and was about to give up and study for the exam when he had the idea that now carries his name. His method was published in 1952 as A Method for the Construction of Minimum-Redundancy Codes.
The recipe is short. Count how often each symbol appears. Take the two least frequent items, join them under a new parent whose count is their sum, and put the parent back in the pile. Repeat until one tree is left. Rare symbols get merged first, so they end up deepest in the tree, with the longest codes.
| Char | Count | Code |
|---|
Try the presets. A message that is nearly all one letter shrinks dramatically. Try abcdefgh, where every letter appears once: every code comes out exactly 3 bits long, the same as a plain fixed-length code for 8 symbols. Huffman gains nothing there, because there is no imbalance to exploit (the 8-bit ASCII comparison flatters it, since ASCII has room for 256 symbols). The real saving comes from how uneven the counts are.
Huffman's tree is optimal among codes that give each symbol its own whole number of bits: no other prefix code can encode the same message in fewer bits. Merging the two rarest symbols first is safe, because in an optimal tree the two rarest symbols can always be placed as siblings at the bottom.
Claude Shannon showed that the average code length can never fall below the message's entropy, a measure of how unpredictable the symbols are. Huffman codes get close to that floor but usually not exactly on it, because a symbol must use a whole number of bits. A symbol that deserves 0.2 bits still costs 1. Methods such as arithmetic coding can squeeze past that limit by coding several symbols together.
Huffman coding is a stage inside many everyday formats. DEFLATE, the algorithm behind ZIP and PNG files, uses it, and so do JPEG images and MP3 audio. In several of these the codes are predefined or stored compactly in the file rather than rebuilt from scratch, but the idea is the same: spend few bits on what is common, and many on what is rare.
The decoder needs the same tree as the encoder, so the file must carry the code table or enough information to rebuild it. For a long message that overhead is tiny. For a very short one, such as the 17 characters above, it would eat into the saving, which is why the counter here ignores it.