The encyclopedia · Engineering & Operations · Technical decision · 1951–1952
Huffman solved an open coding problem as a term paper
In 1951 an MIT grad student built a frequency-sorted tree from the bottom up and proved it optimal.
Massachusetts Institute of Technology
the move
In 1951 David Huffman and his MIT information-theory classmates were given the choice of a term paper or a final exam, and their professor Robert Fano set the term paper on the problem of finding the most efficient binary code. Huffman could not prove any code was the most efficient and was about to give up and study for the exam.
He then hit on building a frequency-sorted binary tree from the bottom up, repeatedly merging the two least-common symbols, and quickly proved the result optimal. Building from the least-frequent end guaranteed optimality, whereas the top-down approach Fano had developed with Claude Shannon did not.
The result is a prefix code: because each symbol's code is never a prefix of another's, a decoder can reconstruct the message unambiguously, and the most frequent symbols get the shortest representations, so the average message shrinks toward the information-theoretic limit.
why it works
- Merging the two least-common symbols first keeps the most frequent symbols nearest the root with the shortest codes.
- The code is a prefix code, so a decoder can split the bitstream without separators.
- Bottom-up construction makes optimality easy to prove, which top-down Shannon-Fano coding could not guarantee.
what transfers
On a hard problem, try reversing the direction everyone else is going; building from the least-common end up can turn an optimum that looks unprovable into one that follows immediately.
what came after
Huffman coding became one of the most widely used data-compression methods, underpinning JPEG, MP3 and the Deflate algorithm inside gzip and PNG, and Huffman's term-paper solution outdid his own professor; the method remains a standard building block for lossless compression.
references
spotted an error? The archive wants to know.