How Huffman coding works

What problem does Huffman coding solve?

Computers usually store text with a fixed number of bits per character. That is simple, but wasteful, because some characters appear far more often than others. If a common letter could be written with two bits and a rare one with eight, the same text would take up less space overall.

The difficulty is decoding. If codes have different lengths and nothing marks where one ends, a reader could split the bits in more than one way. Huffman's answer is a prefix code: no symbol's code is ever the beginning of another symbol's code. Reading bit by bit, the decoder always knows exactly when a symbol is complete, so no separators are needed and nothing is lost.

How does the algorithm work, step by step?

Start by counting how often each symbol appears. Each symbol becomes a small node carrying its count, called its weight. Put all the nodes in a list ordered from least to most frequent.

Now repeat one move. Take the two nodes with the lowest weights and join them under a new parent node whose weight is their sum. Put the parent back into the list. Each round removes two nodes and adds one, so the list shrinks until a single node remains. That last node is the root of the Huffman tree.

To read off the codes, walk from the root to each symbol, writing 0 for every step to a left child and 1 for every step to a right child. Symbols that were merged late, the common ones, sit close to the root and get short codes. Symbols merged early, the rare ones, sit deep in the tree and get long codes. With an ordinary priority queue the construction takes time proportional to n log n for n symbols, and if the weights arrive already sorted it can be done in linear time using two queues.

What does a worked example look like?

Take the 11-letter word ABRACADABRA. A appears 5 times, B and R twice each, and C and D once each. Written with a fixed code, five different letters need 3 bits apiece, so the word costs 33 bits.

Build the tree. The two rarest letters, C and D, merge into a node of weight 2. The lowest weights are now B, R and that new node, all at 2; joining the C-D node with B gives a node of weight 4. Next, R (2) joins that node to make 6. Finally A (5) joins the 6 to form the root of weight 11. Reading the paths gives A = 0, R = 10, B = 110, C = 1110 and D = 1111.

Count the cost: five A's at 1 bit, two R's at 2 bits, two B's at 3 bits, and one each of C and D at 4 bits. That adds up to 23 bits instead of 33, and the bit string still decodes in exactly one way, because no code begins another. Breaking the tie between B, R and the C-D node differently would give different codes of the same total length; Huffman codes are not unique, but every version is equally short.

Where did it come from, and where is it used?

David A. Huffman developed the method in 1951 while studying for a doctorate (Sc.D.) at MIT. His professor, Robert M. Fano, let students choose between a term paper and a final exam, and set the paper's problem: find the most efficient binary code. Huffman could not prove any existing code was best and was close to giving up when he hit on building the tree from the bottom up, sorted by frequency. That approach was provably optimal, which the top-down Shannon-Fano method developed by Fano and Claude Shannon was not. The paper was published in 1952.

Huffman coding became so common that the phrase Huffman code is often used for any prefix code. It appears as a stage inside larger compression schemes: Lempel-Ziv methods replace repeated strings with table entries, and that table is often Huffman encoded. Fax machines use a modified form of Huffman coding together with run-length encoding, which first counts runs of repeated symbols.

Where does it fall short?

Huffman coding is optimal only under its own rules: each symbol coded separately, with known and independent frequencies. Every code must be a whole number of bits, so when one symbol is very common, far more than half of the data, it still costs at least one bit each time, and the waste can be large. Arithmetic coding avoids the whole-bit restriction and generally compresses better, especially when frequencies shift within a stream, though it is usually slower.

There is also overhead. The decoder needs the tree, so either a standard tree is agreed in advance, at some cost in efficiency, or the tree is sent along with the data. And no code can compress data where every symbol is equally likely and the alphabet size is a power of two; there, a plain fixed-length code is already the best possible.

What does Huffman coding teach about thinking?

The core idea is to spend effort in proportion to frequency. Things that happen constantly deserve the cheapest representation; things that happen rarely can afford to be expensive. That is the logic behind short words for common ideas and well-worn paths for daily tasks.

Its origin carries a second lesson. Fano's method worked from the top down, splitting symbols into groups; Huffman's worked from the bottom up, starting with the smallest pieces. Changing the direction of attack on a problem turned a good approximation into a proven best answer.

Questions people ask

The thinking behind it

• signal vs noise
• entropy
• pareto principle
• first principles thinking

More algorithms, explained

• How A/B testing works
• How cache replacement policies work
• How Dijkstra's algorithm finds the shortest path
• How gradient descent works