Huffman coding
hardRare symbols end up deepest and get the longest codes. Every symbol sits at a leaf, so no code is a prefix of another - which is what makes the output decodable without separators.
O(n log n)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How huffman coding works
Build the code tree bottom-up: repeatedly pull the two lowest-frequency nodes out of a min-heap and merge them under a new parent. Rare symbols can afford long codes, so they belong deepest, and every merge pushes its pair one level further down. In abracadabra, a accounts for 5 of the 11 letters and ends one edge from the root, while c and d, one occurrence each, sink three levels deep.
The greedy step survives an exchange argument. Take any optimal tree and find its deepest pair of siblings. Swapping the two rarest symbols into those two slots cannot raise the total cost, because whatever occupied them was at least as frequent and moves up. So some optimal tree starts with exactly the greedy merge, and induction on the merged alphabet carries the argument to the whole tree.
What the tree buys you is the prefix property: every symbol lives at a leaf, so no code is the beginning of another, and a decoder reads bit by bit knowing exactly where each symbol ends - no separators. The result is provably the best among all prefix codes for the given frequencies; beating it means abandoning whole bits per symbol, which is what arithmetic coding does.
Step by step
- Count abracadabra: a=5, b=2, r=2, c=1, d=1. Five leaves go into a min-heap keyed by frequency.
- Pop the two rarest, c and d, and hang them under a new internal node of frequency 2.
- Now b and r are the cheapest pair. Merge them into a node of frequency 4.
- Three roots remain, weighing 2, 4, and 5. Merge the 2 and the 4 into a node of frequency 6.
- Merge a, frequency 5, with that 6. The root weighs 11 and the letter a sits one edge below it.
- Walk root to leaf writing 0 for left and 1 for right: a=0, c=100, d=101, b=110, r=111.
- The encoded text needs 23 bits against 33 for fixed three-bit codes - a 30 percent saving, with no code a prefix of another.
Complexity
| Worst case time | O(n log n) |
|---|---|
| Space | O(n) |
Optimal among all prefix-free codes for the given frequencies.
Reference implementation
Python
import heapq
from collections import Counter
def huffman(text):
freq = Counter(text)
heap = [[f, i, ch, None, None] for i, (ch, f) in enumerate(freq.items())]
heapq.heapify(heap)
nxt = len(heap)
while len(heap) > 1:
a = heapq.heappop(heap)
b = heapq.heappop(heap)
heapq.heappush(heap, [a[0] + b[0], nxt, None, a, b])
nxt += 1
codes = {}
def walk(node, prefix=""):
if node[2] is not None: # leaf
codes[node[2]] = prefix or "0"
return
walk(node[3], prefix + "0") # left = 0
walk(node[4], prefix + "1") # right = 1
walk(heap[0])
return codesJavaScript
function huffman(text) {
const freq = new Map();
for (const ch of text) freq.set(ch, (freq.get(ch) ?? 0) + 1);
let heap = [...freq].map(([ch, f]) => ({ f, ch }));
while (heap.length > 1) {
heap.sort((a, b) => a.f - b.f);
const [a, b] = heap.splice(0, 2);
heap.push({ f: a.f + b.f, left: a, right: b });
}
const codes = {};
(function walk(node, prefix) {
if (node.ch !== undefined) { codes[node.ch] = prefix || "0"; return; }
walk(node.left, prefix + "0");
walk(node.right, prefix + "1");
})(heap[0], "");
return codes;
}Worth noticing
Merging the two rarest symbols is the greedy choice
The two least frequent symbols must end up deepest in the tree, so they can safely be combined first. Every merge pushes them one level down, and rare symbols can afford long codes.
The prefix property is what makes it decodable
Every symbol sits at a leaf, so no code is a prefix of another. A decoder can therefore read bit by bit and know exactly when a symbol ends - no separators, no lengths, no ambiguity.
Optimal among prefix codes, provably
No other prefix-free code assigns a smaller expected length for these frequencies. Better compression requires abandoning per-symbol codes entirely, which is what arithmetic coding and modern compressors do.
The compression ratio comes from skew
Uniform frequencies give every symbol nearly the same code length and save almost nothing. The more lopsided the distribution, the more the common symbols shrink - watch the ratio change as you edit the text.
Common pitfalls
- Merging the two most frequent nodes instead of the two rarest. The construction depends on burying rare symbols deepest; reversing it hands the longest codes to the commonest letters.
- Forgetting the one-symbol alphabet. The root is a leaf, the walk emits an empty code, and encoding breaks - both implementations here default that code to 0.
- Storing codes as numbers. Leading zeros vanish - 001 and 1 collapse into the same integer - so codes must live as strings or explicit bit lengths.
- Expecting one canonical answer. Frequency ties can be merged either way, so two correct implementations emit different codebooks with identical total length - compare costs, not trees, in tests.
- Assuming compression always follows. Uniform frequencies give every symbol nearly the same depth and save almost nothing; the 30 percent on abracadabra comes entirely from skew.
Where it is used
- DEFLATE, the format inside zip, gzip, and PNG, entropy-codes its symbol streams with Huffman tables.
- JPEG and MP3 compress their quantised coefficients with Huffman coding as the final stage.
- HTTP/2 header compression, HPACK, ships a fixed Huffman table for header text.
- The interview classic merge files at minimum total cost is this exact repeated cheapest-pair merge.
Frequently asked questions
What is the time and space complexity of Huffman coding?
O(n log n) time and O(n) space for n distinct symbols. Building the tree takes n minus 1 merges, each popping twice and pushing once on a heap of at most n nodes; the finished tree and codebook hold O(n) entries.
Why can Huffman codes be decoded without separators?
No code is a prefix of another, because symbols sit only at leaves. A decoder follows bits from the root - 0 left, 1 right - emits a symbol whenever it lands on a leaf, and restarts at the root. Ambiguity is structurally impossible.
Is Huffman coding optimal?
Among prefix codes that spend a whole number of bits per symbol, yes - no such code beats it for the given frequencies. Arithmetic coding and modern compressors do better by dropping the whole-bit constraint and encoding the stream as one long fraction.
When does Huffman coding compress badly?
When frequencies are nearly uniform. Every symbol then sits at almost the same depth, so the variable-length codes degenerate toward fixed width. The 30 percent saving on abracadabra exists because the letter a alone supplies 5 of the 11 characters.