A Method for the Construction of Minimum-Redundancy Codes
Give common symbols short codes, rare ones long — and you reach the shortest code of all.
What if you could squeeze a message smaller for free, just by giving your most common letters the shortest codes — the way Morse gave “E” a single dot?
The big idea
A computer stores everything as bits — 0s and 1s. The lazy way is to give every letter the same number of bits, say eight for each. But letters are not equally common: in English, “e” and space appear constantly while “q” and “z” are rare. So why spend the same room on each?
Huffman's method hands out short codes to frequent symbols and long codes to rare ones, in just the right proportion to make the average message as short as it can possibly be. And there is a beautiful guarantee: no other code that can be read back unambiguously can do better. It is not a clever trick that usually works — it is provably the best.
How it came about
In 1951 David Huffman was a graduate student at MIT, taking an information-theory course from Robert Fano — a colleague of Claude Shannon, who three years earlier had founded the whole field. Fano offered his students a choice: sit the final exam, or write a term paper solving an open problem. The problem was exactly this one: find the most efficient such code. Fano and Shannon had each found good methods, but nobody had proved one was best.
Huffman struggled for weeks and had nearly given up — about to throw his notes away — when the key idea arrived: build the code from the bottom up, starting by merging the two rarest symbols, instead of splitting from the top down as his teachers had. That inversion was the whole solution. The student had solved what his famous professor could not.
Why it mattered
Huffman coding became one of the most widely used algorithms ever written. Every time you open a ZIP file, view a JPEG photo, or play an MP3, a Huffman tree is quietly at work, packing symbols into the fewest bits. Because it is simple, fast, and provably optimal among codes of its kind, it became the default building block of compression — and it still is, seventy years on.
A way to picture it
Think of packing a suitcase. The things you use every day — phone, toothbrush — you want right on top, easy and quick to reach; the things you rarely touch can go to the bottom, harder to get at. Huffman does the same with symbols: the ones you “reach for” most often get the shortest codes, the rarities sink to the deepest, longest paths. Arrange it just so, and the whole suitcase packs as tightly as it possibly can.
Where it sits
Huffman stands on Claude Shannon, whose 1948 theory (also in this Library) defined entropy — the true floor on how few bits a message needs — and proved that floor can be approached. Shannon and Fano found codes that came close; Huffman found the one that reaches the best a symbol-by-symbol code can. After him came arithmetic coding and, more recently, ANS, which press still closer to Shannon's limit. From the telegraph through ZIP to streaming video, this is the lineage of squeezing more meaning into fewer bits.
Summary & the problem
An optimum method of coding an ensemble of messages consisting of a finite number of members is developed. A minimum-redundancy code is one constructed in such a way that the average number of coding digits per message is minimized.