Huffman Coding: How to Compress Text by Giving Frequent Letters Shorter Names

Suppose you want to write down a long string of letters from some alphabet — perhaps the text of a novel, or the symbols emitted by a measurement device — and you want to store or send it using as few bits as possible. The simplest plan is to give every symbol a fixed-length code. An alphabet of $n$ symbols needs $\lceil \log_2 n \rceil$ bits per symbol that way: five symbols need three bits each, since $2^2 = 4$ is not enough but $2^3 = 8$ is plenty.

But that wastes space whenever the symbols are not equally common. In an English novel the letter “e” appears about thirteen percent of the time, and the letter “z” about a tenth of a percent. Paying the same number of bits to write “e” as to write “z” is, intuitively, throwing bits away. A better plan would be to assign short codes to common symbols and long codes to rare ones, the way Morse code does — “E” is a single dot, “Q” is dash-dash-dot-dash.

This is the idea of a variable-length code. It immediately raises a subtler question: when codewords have different lengths, how does the receiver tell where one codeword ends and the next begins? And, having answered that, how do you find the best such code? Huffman coding, invented by David Huffman in 1952 while he was a graduate student at MIT, answers both questions in a single short algorithm. Despite being seventy years old, it sits inside almost every modern compressor — ZIP, JPEG, MP3, PNG, HTTP/2 — and is still the standard against which alternatives are measured. This article is about how it works and why.

Prefix codes: making variable-length unambiguous

The first thing to settle is the boundary problem. If codes have different lengths, the decoder must be able to tell when each codeword ends. Huffman’s trick is to use a prefix code: no codeword is allowed to be the start of any other codeword. Once that rule is in force, the decoder simply reads bits from left to right; the moment the bits read so far form a valid codeword, it must be the only one possible, since no longer codeword can start the same way. The bits can then be decoded and the next codeword begins.

A prefix code has a natural representation as a binary tree. Internal nodes branch left for $0$ and right for $1$; leaves are the codewords. The path from the root to a leaf gives the bit string. Because leaves cannot have descendants, no codeword is a prefix of another by construction.

The Huffman recipe

Suppose the alphabet has symbols with probabilities (or counts) $p_1, p_2, \dots, p_n$, and we want the prefix code that minimises the average codeword length $\sum p_i \ell_i$, where $\ell_i$ is the length of the codeword assigned to symbol $i$. Huffman’s algorithm is:

1. Treat each symbol as a leaf node with weight $p_i$.
2. Repeat: pick the two nodes with the smallest weights, combine them under a new parent node whose weight is the sum of the two, and put the parent back into the pool.
3. Stop when only one node — the root — remains.

The tree built this way is the optimal Huffman tree. The codes are read off as the binary paths from root to each leaf. The whole construction is greedy — at each step it makes the locally best decision — and remarkably, this greedy choice produces a globally optimal code.

A worked example

Take an alphabet of five symbols with probabilities $A: 0.35$, $B: 0.20$, $C: 0.20$, $D: 0.15$, $E: 0.10$. Apply the algorithm.

Step 1: the two smallest are $D = 0.15$ and $E = 0.10$. Combine them into a parent of weight $0.25$.

Step 2: the pool is now $\{A: 0.35, B: 0.20, C: 0.20, DE: 0.25\}$. The two smallest are $B$ and $C$. Combine them into $BC$ of weight $0.40$.

Step 3: the pool is $\{A: 0.35, DE: 0.25, BC: 0.40\}$. The two smallest are $DE$ and $A$. Combine into $ADE$ of weight $0.60$.

Step 4: the pool is $\{ADE: 0.60, BC: 0.40\}$. Combine into the root of weight $1.00$.

The resulting tree:

Reading off the codes by tracing root-to-leaf paths gives

$B \to 00, \quad C \to 01, \quad A \to 10, \quad D \to 110, \quad E \to 111.$

The most common symbol, $A$, gets a two-bit code; the rarest, $D$ and $E$, get three-bit codes. The average codeword length is

$0.35(2) + 0.20(2) + 0.20(2) + 0.15(3) + 0.10(3) = 2.25\text{ bits per symbol}.$

A naive fixed-length code would need three bits per symbol for five letters, so Huffman saves $0.75$ bits per symbol — about a $25\%$ reduction. Over a long text, that adds up to a substantial saving.

How close to optimal is this really?

There is a fundamental lower bound. The Shannon entropy of the source,

$H = -\sum_i p_i \log_2 p_i,$

is the theoretical minimum average number of bits per symbol that any compression scheme can achieve in the limit of long messages. For our example $H \approx 2.20$ bits per symbol. Huffman achieved $2.25$, just $0.05$ bits per symbol away from the absolute floor. In general Huffman comes within one bit per symbol of the entropy and usually much closer, and a theorem of Huffman’s own paper shows there is no integer-length prefix code that does any better. So among integer-length prefix codes, Huffman is exactly optimal.

The gap between $2.20$ and $2.25$ comes from a hard structural constraint: Huffman must give each symbol a whole number of bits, but the “ideal” number of bits for symbol $i$ is $-\log_2 p_i$, which is rarely an integer. The most common symbol $A$ ideally carries $-\log_2 0.35 \approx 1.51$ bits of information — but a codeword cannot have $1.51$ bits, so Huffman rounds up to $2$. The cumulative round-up across all symbols accounts for the small but persistent gap to entropy. Arithmetic coding sidesteps this by allowing fractional bits, which is why it is preferred when the last few percent of compression really matter.

Why the greedy choice is optimal

The proof that Huffman’s bottom-up construction produces the best possible tree has a short and surprising structure. It hinges on two observations.

First, in any optimal tree, two symbols of smallest probability can always be placed as siblings at the deepest level. If not, swapping them with whatever two siblings are at the deepest level can only decrease the average codeword length, since the deepest leaves get the largest $\ell_i$. So we lose nothing by committing, at the start, to put the two least-frequent symbols together as siblings.

Second, once those two symbols are paired, replacing them with a single combined symbol of weight equal to their sum leaves the rest of the optimisation problem of the same shape, just on a smaller alphabet. This is exactly the move the Huffman algorithm makes. By induction the merged problem is solved optimally, and that optimal solution lifts back to an optimal tree on the original alphabet.

The argument is short and clean, and the fact that a greedy algorithm gives a provably global optimum is one of the most-cited examples of when greed succeeds in algorithm design.

What Huffman cannot do

The integer-bit limitation is the main one, and arithmetic coding overcomes it at the cost of more arithmetic per encoded symbol. Huffman also cannot adapt automatically to a source whose probabilities change as the data flows by — though adaptive Huffman variants update the tree on the fly, with some efficiency cost. And Huffman cannot exploit correlations between successive symbols: it treats each symbol as independent, so a source where letters are highly predictable from context (e.g. natural language) needs an additional modelling step before Huffman can compress it well. The DEFLATE format used by gzip and ZIP couples Huffman with a sliding-window dictionary that captures repeated phrases — the first stage finds the patterns, the second stage Huffman-codes whatever is left.

A foundational pebble

David Huffman’s algorithm is small enough to be sketched on a napkin yet powerful enough that it has not been displaced in seventy-three years for the basic task of compressing a known distribution of symbols. Inside every ZIP file you have ever made, inside every JPEG image, every MP3 song, every PNG screenshot, every HTTP header passing through the modern web, a small Huffman tree is doing its quiet work — giving short codes to common things and long codes to rare ones, exactly as Huffman saw was possible in a sudden moment of insight when he was supposed to be preparing for a final exam.

Frequently asked

Who was Huffman and how did he discover the algorithm?

David A. Huffman was a graduate student at MIT in 1951 when his professor, Robert Fano, offered the class a choice: take the final exam, or solve the open problem of finding the most efficient prefix code for a given set of letter frequencies. Huffman attempted the open problem for months, gave up, and was about to start studying for the exam when the idea suddenly came to him — a simple bottom-up tree construction that was provably optimal. He published it in 1952 and it has been the standard ever since.

What is a prefix code, and why does it matter?

A prefix code is one where no codeword is a prefix of any other. So if 'A' is encoded as 10, no other letter's code can start with 10. The benefit is that the decoder can read a bitstream from left to right and unambiguously split it into codewords, with no need for separators between symbols. Huffman codes are always prefix codes by construction — each codeword traces out a unique root-to-leaf path in a binary tree, and no leaf can be an ancestor of another leaf.

Is Huffman coding optimal?

It is optimal among the codes that assign a whole number of bits to each symbol. For an alphabet whose symbols have probabilities p_i, the Shannon entropy H = −Σ p_i log_2(p_i) gives the theoretical minimum average bits per symbol, and Huffman gets within one bit of this — usually much closer. But because Huffman must use integer-length codewords, it cannot represent, say, 'this symbol carries 1.5 bits of information' efficiently. Arithmetic coding overcomes that limitation and is the modern standard when the last fraction of a bit really matters.

Where is Huffman coding used today?

Just about everywhere data is compressed. The DEFLATE algorithm at the heart of ZIP, gzip, and PNG uses Huffman as one of its two stages. JPEG compresses the quantized DCT coefficients of an image with Huffman. MP3 and AAC encode quantized audio coefficients with Huffman. HTTP/2 uses a static Huffman table to compress HTTP headers. Even the file formats of fonts and the encoded streams in PDFs lean on Huffman. Seventy years on, it is still the workhorse first step of nearly every compressor in daily use.

Continue reading

Blog

Hamming Codes: How Computers Catch and Fix Their Own Mistakes

Every bit sent across a wire or stored on a chip can flip. A clever scheme from 1950 lets a receiver not only notice the flip but pinpoint exactly which bit went wrong, and silently correct it.

Read →Blog

Dynamic Programming: Solving Hard Problems by Remembering Easy Ones

Many problems repeat the same subproblems over and over. Storing each answer the first time you compute it can turn an exponential algorithm into a polynomial one — sometimes a stunning speedup.

Read →Blog

Information Theory and the Mathematics of Surprise

Claude Shannon's 1948 paper introduced a single equation that quantifies what information actually is. Compression, communication, and modern AI all rest on it.

Read →