Huffman Coding Visualizer

Some letters turn up far more often than others. Any code that spends the same number of bits on a rare letter as on a common one is wasting space. That much is easy to see.

The hard part was never the idea. It was proving that a particular code is the best one possible, so that nobody need look further. That proof arrived in 1952 in a paper four pages long, written by a graduate student who had been offered a way out of an exam.

A term paper instead of a final

The story, as it is usually told, begins in 1951 in an information theory class at the Massachusetts Institute of Technology. The professor, Robert Fano, let his students choose between a final exam and a term paper. The paper had a deceptively plain subject: find the most efficient binary code.

David Huffman chose the paper and got nowhere. He could build codes, but he could not prove that any of them was the most efficient, and he was close to giving up and revising for the exam after all. Then he thought of arranging the symbols in a binary tree sorted by how often each occurs, and the proof followed quickly.

There is some comedy in this. Fano himself had worked with Claude Shannon on a code for the same purpose, and that code, now called Shannon-Fano coding, does not always reach the lowest possible average length. It builds its tree from the top down, splitting the symbols into two groups of nearly equal weight. Huffman went the other way, from the leaves up, and the student’s method beat the teacher’s.

The result appeared in the Proceedings of the IRE in 1952 as “A Method for the Construction of Minimum-Redundancy Codes”. Huffman, born in Ohio in 1925, took his doctorate at the same institute the following year with a thesis on switching circuits, and by one account he was prouder of that thesis than of the code that carries his name.

Why the rarest two go first

The method fits in a sentence. Take the two symbols with the lowest counts, join them under a new node whose count is their sum, treat that node as one symbol, and repeat until a single tree is left. Reading the path from the top to a symbol, 0 for one branch and 1 for the other, gives that symbol’s code.

Why is this greedy habit safe? Picture any best possible tree. Its longest codes sit at the bottom, and a symbol at the bottom always has a partner beside it, because a branch with only one child could be shortened for free. If the two rarest symbols were not down there, swapping them with whatever was could only help: the rare ones would get the long codes and something more common would get a shorter one. So some best tree has the two rarest symbols side by side at the deepest level.

Once that is settled, the pair can be glued together and regarded as a single symbol with the combined count. The same argument then applies to the smaller alphabet, and to the one after that. Each merge is forced, in the sense that refusing it can never produce something better.

Ties are the one loose end. When several counts are equal there is more than one valid choice, and different choices give different trees, sometimes with different code lengths for particular symbols. They never give a different total. Every Huffman tree for the same counts spends the same number of bits overall, which is worth remembering when a worked answer in a textbook does not match yours digit for digit.

No separators needed

A code with words of different lengths has an obvious problem: where does one word stop and the next begin? A gap or a special marker would cost bits of its own. A Huffman code needs neither, because of where its symbols live. They are all at the tips of the tree, never partway along a branch, so no code is the beginning of another. Such a code is called a prefix code, and a receiver can cut the stream into words as the bits arrive, without any marker between them.

There is a budget behind this. A code of length one uses up half of all possible bit patterns, a code of length two a quarter, and so on. For any prefix code the fractions add up to at most one, a rule published by Leon Kraft in 1949 and extended by Brockway McMillan in 1956 to every code that can be decoded without ambiguity. A Huffman tree spends the budget exactly, with nothing left over.

The same fact makes a tidy trick possible. If only the lengths matter, the actual bit patterns can be reassigned in a fixed order: shorter codes first, and codes of equal length counting upward in alphabetical order. This canonical form means a compressor need only send the list of lengths, and the receiver rebuilds the identical code from it.

The limit, and a sentence to try

How good can any code be? Shannon answered that in 1948, four years before Huffman, with a quantity he called entropy. A symbol of probability p carries log base 2 of 1/p bits of information, and the entropy is the average of that over all the symbols. A fair coin has an entropy of exactly one bit. No lossless code can average fewer bits per symbol than the entropy of its source.

Huffman’s code lands within one bit of that floor. Its average length is never below the entropy and always less than the entropy plus one. The gap closes completely when every probability is a power of one half, since then each symbol deserves a whole number of bits and gets it.

Here is an example to reproduce. Take the sentence “this is an example of a huffman tree”, which has 36 characters drawn from 16 different ones, the space included. A fixed code needs 4 bits for each of 16 symbols, so 144 bits in all. The Huffman code gives the space, which occurs seven times, a 3-bit code and gives the letters that occur once 5-bit codes, for a total of 135 bits. That is an average of 3.75 bits per character against an entropy near 3.71. Stored as ordinary 8-bit characters the sentence would take 288 bits.

Two honest footnotes belong to that figure. The 135 bits do not include the table, and the receiver cannot decode without it. And a different tie-break will hand some of the equally common letters different codes while arriving at 135 all the same.

Where it runs today, and where it loses

The method is everywhere, usually out of sight. The DEFLATE format, the method of the PKZIP archiver, first replaces repeated strings with pointers back to an earlier copy and then codes what remains with Huffman codes, either a fixed set or a set built for the block and sent as a list of code lengths in canonical order. The PNG image format stores its pixels as a DEFLATE stream. The original JPEG standard specifies Huffman coding for its baseline process and ships no default tables, so that applications can choose their own.

Newer formats kept it. HTTP/2 compresses header text with a fixed Huffman code that its designers generated from statistics on a large sample of real headers. Zstandard uses Huffman codes for literal bytes alongside a second entropy coder.

Real formats also bend the pure method. DEFLATE describes code lengths with numbers from 0 to 15, so no code may be longer than 15 bits, and the specification admits that this constraint complicates the calculation. The limit matters for lopsided data: when the counts grow like the Fibonacci numbers, each the sum of the two before, the codes come out as long as Huffman codes can be.

And the method has a ceiling. It is the best code only among those that give every symbol its own whole number of bits. A symbol that turns up nine times in ten deserves a small fraction of a bit, and a Huffman code must still spend a full one. Arithmetic coding escapes by turning the entire message into a single number, so that its effective code lengths need not be whole. The JPEG standard offers it as the alternative to Huffman coding, and the basic algorithms date from 1976. It is slower and more intricate, and for years patents discouraged its use.

So the term paper endures for a practical reason. It is simple, fast, provably optimal within its limits, and good enough that a great many of the files and pages people touch each day still pass through it.