Huffman Coding, Explained
After reading, you will be able to build a Huffman tree by hand, read codewords off it, compute the average bits per symbol, and judge how much compression a given text actually allows.
What Huffman coding does
Huffman coding assigns a short binary codeword to each symbol in your text. Common symbols get short codes, rare ones get long codes. The codes are chosen so no codeword is a prefix of another, which lets a decoder split the bitstream back into symbols without any separators.
Here is the hook. Take the word banana. Fixed 8-bit ASCII spends 48 bits on it. Huffman notices that a appears 3 times, n twice, and b once, then hands out codes like a = 0, n = 10, b = 11. The encoded string 110100100 is 9 bits long. That is an 81% reduction, and every bit is recoverable.
The trick is greedy. Repeatedly take the two least frequent symbols, merge them into one node whose frequency is their sum, and repeat until a single node remains. That node is the root of a binary tree, and the path from root to each leaf spells its codeword.
When to reach for it, and when not
Huffman coding is the right tool when you know the symbol frequencies and want an optimal prefix code over whole symbols. It is fast to build (dominated by the sort, so O(n \log n) for n symbols) and trivial to decode.
It has real limits. Huffman assigns each symbol a whole number of bits, so it cannot capture the fractional bit that a symbol's true information content often requires. If one symbol has probability 0.9, its ideal code length is -\log_2 0.9 \approx 0.152 bits, but Huffman must spend at least 1 bit. On such skewed sources, arithmetic coding beats it. Huffman also assumes fixed frequencies: on text whose statistics drift, adaptive methods do better.
Huffman is provably optimal among prefix codes over single symbols. It is not the shortest possible encoding in general. Grouping symbols into blocks, or switching to arithmetic coding, can go lower.
The formula and the intuition
The quantity Huffman minimises is the average code length, weighted by frequency:
Here p_i is the probability (relative frequency) of symbol i, and \ell_i is the length in bits of its codeword. The greedy merge rule provably makes L as small as any prefix code can.
The floor that L can never break is the Shannon entropy:
Entropy is the average number of bits per symbol that an ideal code would use. Huffman satisfies H \le L \lt H + 1. The gap comes from rounding each length to a whole number. When every probability is an exact power of \tfrac{1}{2}, the gap closes and L = H exactly.
A worked example with the demo text
Encoding "abracadabra"
The demo starts with the string abracadabra, which has 11 characters. Count the letters first.
| Symbol | Count | p |
|---|---|---|
| a | 5 | 0.4545 |
| b | 2 | 0.1818 |
| r | 2 | 0.1818 |
| c | 1 | 0.09091 |
| d | 1 | 0.09091 |
- Start with five leaves carrying counts 5, 2, 2, 1, 1.
- Merge the two lightest,
c(1) andd(1), into a node of weight 2. Nodes now weigh 5, 2, 2, 2. - Merge two of the weight-2 nodes. Take
b(2) andr(2) into a node of weight 4. Nodes now weigh 5, 4, 2. - Merge the weight-4 node with the (c,d) weight-2 node into a node of weight 6. Nodes now weigh 6, 5.
- Merge the last two into the root of weight 11.
Reading left edges as 0 and right edges as 1 gives one valid assignment: a = 0 (length 1), b = 100, r = 101, c = 110, d = 111 (each length 3).
Now compute the total bits: a costs 5×1 = 5, and each of b, r, c, d costs its count times 3, giving 2×3 + 2×3 + 1×3 + 1×3 = 24. Total is 29 bits. Fixed 8-bit encoding would spend 11×8 = 88 bits, so the ratio is 29/88 = 0.330, a 67% reduction.
The average code length is L = 29/11 \approx 2.636 bits per symbol. The entropy is H \approx 2.040 bits per symbol. The gap of about 0.6 bits is the rounding penalty, and it sits comfortably inside the guaranteed H + 1.
a, gets the shortest code. The four rare symbols all sink to depth 3.Reading and interpreting the tree
Depth in the tree is code length. A leaf at depth d has a d-bit codeword, and the path spells the bits. Frequent symbols float near the root; rare ones sink. If two symbols share the same depth, they cost the same number of bits, which is why b, r, c, and d above all landed at depth 3.
The compression ratio shown as you type is L_{\text{Huffman}} divided by the fixed cost. Watch how it responds. Type aaaaaaaa and the ratio collapses toward its structural floor, because one symbol needs only a single-symbol code. Type abcdefgh with eight equal letters and the ratio sits at exactly 3/8, since eight equally likely symbols need \log_2 8 = 3 bits each and Huffman achieves that with no waste.
To see Huffman hit the entropy floor exactly, use symbols whose frequencies are powers of one half. Four symbols with counts 8, 4, 2, 2 give codes of length 1, 2, 3, 3 and L = H = 1.75 bits with zero rounding loss.
Common mistakes
The first trap is forgetting the header cost. The 29 bits for abracadabra assume the decoder already knows the tree. In a real file you must also store the code table, which for a short string can dwarf the payload. Huffman only pays off once the text is long enough to amortise that overhead.
The second trap is expecting a unique tree. When several nodes tie in weight, the choice of which pair to merge is free, so different implementations produce different but equally optimal trees. The individual codewords may differ while L stays identical. Do not treat one specific code table as canonical.
The third trap is comparing against the wrong baseline. Comparing Huffman to 8-bit ASCII flatters it, because ASCII wastes space on an alphabet of 256 when your text uses five letters. The honest floor is the entropy H, not the fixed 8-bit cost.
Watch the code length track the frequencies
Related tools
Huffman coding is the entropy stage that runs after other steps in real compressors. To see the sorting that the greedy merge relies on, watch the Sorting Algorithm Visualizer. For a different error-handling view of bits, flip a bit in the Hamming Code Playground and watch the parity checks locate it. Since Huffman is a greedy tree algorithm, the Graph Algorithm Playground shows the same greedy spirit in Prim's minimum spanning tree. To feel why the O(n \log n) build cost matters, race it in the Big-O Complexity Race.
Frequently asked questions
Why can Huffman codes be decoded without separators?
Because no codeword is a prefix of another. Once the decoder reads a complete codeword, no longer valid codeword could start with those same bits, so it can stop and emit the symbol immediately. For abracadabra, seeing 0 means a at once, and no other code begins with 0.
Is Huffman the best possible compression?
It is the best prefix code over single symbols, but not the best possible in general. When probabilities are not powers of one half, Huffman rounds each length up to a whole bit. Arithmetic coding spends fractional bits and can beat it, especially on skewed sources like the two-symbol case where Huffman wastes up to 0.531 bits per symbol at p = 0.9.
What happens with only one distinct symbol?
A single symbol produces a degenerate tree with one leaf. By convention it gets a 1-bit code, so encoding aaaa takes 4 bits plus the table. This is the case where Huffman looks worst relative to entropy, since the true information content is near zero.
Why do different tools show different trees for the same text?
Ties. When several nodes share the lowest weight, the algorithm may merge any two of them. Each choice yields a valid, equally optimal tree, so the average code length L matches even though the individual codewords differ.
Does the compression ratio include the code table?
The live ratio shown here counts only the encoded payload against fixed 8-bit encoding. A real file must also store the tree or frequency table. For short strings that header can exceed the savings, so treat the displayed ratio as the payload's ceiling, not the whole-file result.
Related tools
Dynamic Programming Visualizer
Watch edit distance and knapsack fill their tables cell by cell — dynamic programming with the lid off.
Graph Algorithm Playground
Build a graph by clicking, then watch BFS, DFS, Dijkstra and Prim explore it live.
Pathfinding Visualizer
Draw walls and watch A*, Dijkstra, greedy and breadth-first search hunt for the shortest path.
Sorting Algorithm Visualizer
Watch bubble, insertion, merge, quick and heap sort race through the same shuffled bars.
Turing Machine Simulator
Watch a Turing machine read, write and shuffle along its tape — computation stripped to its atoms.
Hamming Code Playground
Flip any bit of a Hamming-encoded message and watch the parity checks point straight at the culprit.