On this page
Some letters turn up far more often than others. If every symbol gets a code of the same length, you waste bits on the common ones. David Huffman worked out, as a graduate student, how to build the shortest possible code for a known set of symbols. This post covers his life, the method from his 1952 paper, a full worked example and the habits behind it.
Who was David Huffman?
The UC Santa Cruz obituary, published in October 1999, gives the outline. Huffman was a native of Ohio and earned his bachelor's degree in electrical engineering from Ohio State University at the age of 18. He served in the U.S. Navy as a radar maintenance officer on a destroyer that helped clear mines in Japanese and Chinese waters after the Second World War. He then took a master's degree at Ohio State and a doctorate at MIT, both in electrical engineering.
He joined the MIT faculty in 1953 and in 1967 moved to UC Santa Cruz as the founding faculty member of its computer science department, which he chaired from 1970 to 1973. He also worked on switching circuits and signal design, and developed his own techniques for folding paper into curved sculptures. He died on 7 October 1999, aged 74. That year the IEEE gave him the Richard W. Hamming Medal.
The obituary says his coding procedure was "the result of a term paper he wrote while a graduate student" at MIT.
What problem did his 1952 paper solve?
The paper, A Method for the Construction of Minimum-Redundancy Codes, appeared in the Proceedings of the IRE in September 1952. Its summary is one sentence: "An optimum method of coding an ensemble of messages consisting of a finite number of members is developed." A minimum-redundancy code is one where the average number of coding digits per message is as small as possible.
Huffman notes in the introduction that Claude Shannon and R. M. Fano had developed coding procedures to prove that the average number of binary digits per message approaches the average amount of information from above. Those procedures were not optimum. Our post on Claude Shannon and information explains the information measure itself.
He also set a rule: no extra signal should be needed to show where one code ends and the next begins. In practice, no code may be the start of another code. This is called a prefix code.
How does the method work?
Write the symbols with their frequencies. Take the two least frequent and join them into one combined item whose frequency is their sum. Repeat with the new list until one item is left. Then read the codes back down the tree you have built: one branch of each join gets a 0, the other a 1. Rare symbols are joined early and end up deep in the tree with long codes; common ones are joined late and get short codes.
Worked example: coding a 20-symbol message
Use sample numbers for a made-up message of 20 symbols: A appears 8 times, B 5, C 4, D 2 and E 1.
Join the two rarest, E (1) and D (2), into DE (3). List: DE 3, C 4, B 5, A 8.
Join DE (3) and C (4) into CDE (7). List: B 5, CDE 7, A 8.
Join B (5) and CDE (7) into BCDE (12). List: A 8, BCDE 12.
Join A (8) and BCDE (12). Done.
Reading down the tree, labelling one branch 0 and the other 1, gives A = 0, B = 10, C = 111, D = 1101, E = 1100. Code lengths are 1, 2, 3, 4 and 4 bits.
Total bits: 8 × 1 + 5 × 2 + 4 × 3 + 2 × 4 + 1 × 4 = 8 + 10 + 12 + 8 + 4 = 42 bits, an average of 2.1 bits per symbol. A fixed-length code for five symbols needs 3 bits each, so 60 bits. Huffman coding saves 18 bits, or 30%.
Shannon's formula for this sample gives about 2.04 bits per symbol, the floor no symbol-by-symbol code can beat. Huffman's 2.1 is close to it.
Decoding works because no code is the start of another. Read 0101110 from the left: 0 is A, 10 is B, 111 is C, 0 is A. The message is ABCA, with no separators needed.
Common mistakes:
Not re-sorting after a join. The combined item goes back into the list at its new frequency.
Merging the most frequent symbols first. Always join the two smallest.
Breaking the prefix rule by hand. If you assign codes without the tree, check that no code starts another.
Where are Huffman codes used?
The UC Santa Cruz obituary describes Huffman codes as used in nearly every application that involves compressing and sending digital data, naming fax machines, modems, computer networks and high-definition television. The same idea, counting how often things occur and spending fewer bits on the common ones, sits behind the binary counting ideas in our post on Pingala and binary numbers.
If tree diagrams and counting arguments are where you get stuck, the Fermi Concept Library covers concepts across mathematics and computing, explained one step at a time.
What can a student take from how he worked?
A class assignment can be real research. His method began as a term paper.
Look for the step that repeats. The whole algorithm is one move done again and again.
Check against the limit. Comparing 2.1 bits with Shannon's 2.04 tells you how much room is left.
Try it now: count the letters in your own name, build the Huffman tree, and work out how many bits it saves over a fixed-length code.
