Huffman Coding
Huffman coding assigns short bit strings to frequent symbols and longer strings to rare symbols. A min-heap repeatedly combines the two lowest-frequency trees until one prefix-code tree remains.
Why Variable-Length Codes Need a Prefix Rule
A fixed-length encoding gives every symbol the same number of bits — ASCII uses 8 for each. That is wasteful when symbols appear at very different rates: in English text e is far more common than z, yet both cost 8 bits.
Variable-length coding assigns shorter codes to frequent symbols and longer ones to rare symbols, lowering the average bits per symbol. The saving can be substantial — typically 20 to 40% on natural language text.
But variable-length codes create an immediate problem. If a is 0, b is 1, and c is 01, then the bit sequence 01 is ambiguous: it could be c, or a followed by b. Without fixed boundaries, the decoder cannot tell where one code ends.
The solution is the prefix property: no code may be a prefix of another. Given that, a decoder reading bits one at a time knows it has a complete symbol the moment the accumulated bits match a code, because no longer code could begin the same way. Decoding becomes unambiguous with no separators and no lookahead.
A binary tree enforces this structurally. Put every symbol at a leaf, and let the path from the root spell its code — left is 0, right is 1. Since no leaf lies on the path to another leaf, no code can be a prefix of another. The prefix property is not checked; it is guaranteed by the shape.
Huffman coding is the algorithm that builds the tree minimising the total encoded length for a given set of frequencies. Its output is provably optimal among all prefix codes, which is a strong claim worth being able to state precisely.
- Frequent symbols get short codes, rare symbols long ones
- Ambiguity is prevented by the prefix property, not by separators
- Symbols at leaves of a binary tree guarantee that property
- Huffman produces the optimal prefix code for known frequencies
The Greedy Merge
Construction is short and works bottom-up, building the tree from its leaves toward the root.
Count the frequency of every symbol in the input. Create a leaf node for each and place them all in a min-heap keyed on frequency. Then repeat until one node remains: extract the two lowest-frequency nodes, create a new internal node whose frequency is their sum, attach the two as its children, and insert it back into the heap. The final remaining node is the root.
Reading the codes off the finished tree is a single traversal, accumulating 0 for each left branch and 1 for each right, and recording the accumulated string at each leaf.
The intuition behind the merge order is worth stating: the two least frequent symbols end up deepest in the tree, because they are combined first and every subsequent merge adds another level above them. Depth is code length, so the rarest symbols receive the longest codes — which is exactly the objective.
The complexity is O(n log n) for n distinct symbols: n heap insertions to build, then n−1 merges each costing two extractions and one insertion at O(log n). Building the initial heap is O(n) with heapify. Counting frequencies over an input of length m adds O(m), which usually dominates in practice.
Ties in frequency are broken arbitrarily, and different tie-breaks produce different trees with the same total encoded length. All are optimal; none is more correct. This matters when comparing an implementation against a reference, since the trees may legitimately differ.
A special case needs explicit handling: a single distinct symbol. The loop never runs, there is no internal node, and the symbol's code is the empty string — which encodes nothing. Assign it a single bit, 0, by convention.
- Build a min-heap of leaves, then merge the two smallest repeatedly
- The merged node's frequency is the sum of its children's
- Rarest symbols are merged first, so they end up deepest
- O(n log n); a single distinct symbol needs a special case
Why the Greedy Choice Is Optimal
Huffman is greedy, and greedy algorithms are frequently wrong — so the correctness proof matters. It rests on two lemmas, and giving them is what a complete exam answer looks like.
Lemma one. In some optimal prefix code, the two symbols with the lowest frequencies are siblings at the deepest level.
The argument is an exchange. Take any optimal tree, and let x and y be the two lowest-frequency symbols. Let a and b be two siblings at the maximum depth. Swapping x with a and y with b cannot increase the total cost: moving a low-frequency symbol deeper and a higher-frequency symbol shallower changes the total by a non-positive amount, because the frequency differences and depth differences have opposite signs. So an optimal tree with x and y as deepest siblings exists.
Lemma two. Merging x and y into a single symbol with frequency f(x) + f(y) produces a smaller problem whose optimal solution extends to an optimal solution of the original.
This holds because the cost of the original tree equals the cost of the merged tree plus f(x) + f(y) — that sum is the extra bit each of x and y pays for being one level below their merged parent. Since the added term is fixed, minimising the merged problem minimises the original.
Together these give an inductive proof: the greedy merge is safe at every step, and the subproblem after merging is of the same form. Hence Huffman's output is optimal.
The optimality is bounded in a specific way worth stating. Huffman is optimal among prefix codes that assign a whole number of bits per symbol. The information-theoretic limit is the entropy of the distribution, and Huffman's average code length falls within one bit of it. Where a symbol's ideal length is fractional — a symbol of probability 0.9 ideally costs 0.15 bits — Huffman must round up to 1, and arithmetic coding or ANS closes that gap by not requiring integer lengths.
- The two rarest symbols can always be made deepest siblings — by exchange
- Merging them yields a smaller problem whose optimum extends
- Optimal among integer-length prefix codes, within one bit of entropy
- Arithmetic coding beats it by allowing fractional bit lengths
Merge the two least frequent symbols
import heapq
heap = [(1, "C"), (2, "B"), (5, "A")]
heapq.heapify(heap)
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
heapq.heappush(heap, (left[0] + right[0], (left, right)))
codes = {}
def walk(node, prefix=""):
if isinstance(node[1], str):
codes[node[1]] = prefix or "0"
return
walk(node[1][0], prefix + "0")
walk(node[1][1], prefix + "1")
walk(heap[0])
print("Codes: A=" + codes["A"] + ", B=" + codes["B"] + ", C=" + codes["C"])#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;
struct Node
{
int frequency;
char symbol;
Node *left;
Node *right;
};
struct Compare
{
bool operator()(Node *a, Node *b)
{
return a->frequency > b->frequency;
}
};
void buildCodes(Node *node, string prefix, map<char, string> &codes)
{
if (!node->left && !node->right)
{
codes[node->symbol] = prefix.empty() ? "0" : prefix;
return;
}
buildCodes(node->left, prefix + "0", codes);
buildCodes(node->right, prefix + "1", codes);
}
int main()
{
priority_queue<Node *, vector<Node *>, Compare> heap;
for (auto [symbol, frequency] : vector<pair<char, int>>
{
{
'C', 1
}
,
{
'B', 2
}
,
{
'A', 5
}
}
)
{
heap.push(new Node
{
frequency, symbol, nullptr, nullptr
}
);
}
while (heap.size() > 1)
{
Node *left = heap.top();
heap.pop();
Node *right = heap.top();
heap.pop();
heap.push(new Node
{
left->frequency + right->frequency, 0, left, right
}
);
}
map<char, string> codes;
buildCodes(heap.top(), "", codes);
cout << "Codes: A=" << codes['A'] << ", B=" << codes['B'] << ", C=" << codes['C'];
}import java.util.*;
class Main
{
static class Node
{
int frequency;
char symbol;
Node left;
Node right;
Node(int frequency, char symbol, Node left, Node right)
{
this.frequency = frequency;
this.symbol = symbol;
this.left = left;
this.right = right;
}
}
static void buildCodes(Node node, String prefix, Map<Character, String> codes)
{
if (node.left == null)
{
codes.put(node.symbol, prefix.isEmpty() ? "0" : prefix);
return;
}
buildCodes(node.left, prefix + "0", codes);
buildCodes(node.right, prefix + "1", codes);
}
public static void main(String[] args)
{
PriorityQueue<Node> heap = new PriorityQueue<>(Comparator.comparingInt(node -> node.frequency));
heap.add(new Node(1, 'C', null, null));
heap.add(new Node(2, 'B', null, null));
heap.add(new Node(5, 'A', null, null));
while (heap.size() > 1)
{
Node left = heap.remove();
Node right = heap.remove();
heap.add(new Node(left.frequency + right.frequency, ' ', left, right));
}
Map<Character, String> codes = new HashMap<>();
buildCodes(heap.remove(), "", codes);
System.out.print("Codes: A=" + codes.get('A') + ", B=" + codes.get('B') + ", C=" + codes.get('C'));
}
}Step through it
Running on A:5, B:2, C:1
Read all 15 Steps
- Count frequencies The alphabet contains three positive-frequency symbols.
- Push leaf C C has the smallest frequency, one, so it enters the heap first.
- Push leaf B B, frequency two, joins the heap.
- Push leaf A A, frequency five, joins the heap.
- Heapify leaves The min-heap exposes the two lightest roots.
- Pop C Remove C first.
- Pop B Remove B second.
- Merge C and B Make them siblings under a parent of weight three.
- Push weight 3 Return the new subtree to the heap.
- Pop subtree 3 The combined subtree is now the minimum.
- Pop A weight 5 A is the only other root.
- Merge root weight 8 Join them under the final root.
- Assign left-edge zero The weight-3 subtree receives prefix 0; C receives its next left edge.
- Assign right-edge one A receives 1 while B receives 01.
- Read leaf codes No code prefixes another: A=1, B=01, C=00.
Encoding, Decoding, and Real Use
Encoding builds a map from symbol to code string, then emits each input symbol's code. Decoding walks the tree from the root, taking the left child on a 0 and the right on a 1, emitting the symbol and returning to the root each time a leaf is reached. Decoding is O(bits), proportional to the encoded length rather than to the number of symbols.
The practical difficulty is that the decoder needs the tree, and it must come from somewhere. Three approaches exist.
Transmit the tree alongside the data, which costs header space and can outweigh the compression on short inputs. Use a fixed tree agreed in advance, which is what fax encoding does with a standard table, at the cost of adapting to nothing. Or use canonical Huffman, which is what real formats do.
Canonical Huffman exploits a useful fact: only the code lengths matter, not the specific bit patterns. Given the lengths, both sides can reconstruct identical codes by a deterministic rule — sort symbols by length then alphabetically, and assign codes sequentially. So the header carries only a list of lengths, typically a few bytes, instead of a tree structure. DEFLATE — used by gzip, PNG and ZIP — does exactly this, and JPEG's entropy stage is Huffman too.
Two failure modes deserve mention. Huffman cannot compress data that is already uniform or random: with equal frequencies every code is the same length and the output matches the input, plus header overhead. And the encoding is fragile — a single flipped bit desynchronises the decoder, and everything after it decodes as garbage, since there are no boundaries to resynchronise on. Compressed formats add checksums for this reason.
In modern practice Huffman is rarely used alone. DEFLATE runs LZ77 first to replace repeated sequences with references, then Huffman-codes the result — the two attack different redundancies, repetition and symbol imbalance. Newer formats such as Zstandard and Brotli follow the same layering with ANS or arithmetic coding in the entropy stage, which is where Huffman's one-bit rounding penalty is finally recovered.
- Decoding walks the tree from the root, resetting at each leaf
- Canonical Huffman transmits only the code lengths, not the tree
- Uniform or random data cannot be compressed — the output grows
- DEFLATE pairs LZ77 with Huffman; both attack different redundancies