Prefix codes and Huffman coding
Prefix codes are instantaneously decodable variable-length codes used for lossless data compression; Huffman coding is a greedy algorithm that constructs an optimal binary prefix code for known symbol probabilities.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Engineers use prefix codes and Huffman coding in data compression (file compression, image/audio codecs, network protocols) where we must convert symbols to bits so that decoding is unambiguous and the average bit-rate is small. Huffman coding gives an optimal prefix (instantaneous) binary code when symbol probabilities are known and independent (memoryless source).
Key ideas
Code: a mapping from symbols of a source alphabet to finite sequences (strings) over a target alphabet (typically binary digits 0 and 1). A code assigns each source symbol a codeword (a bit string).
Codeword length: for a codeword x, the length l(x) is the number of bits in x. We write l_i for the length of the codeword for symbol i.
Concatenation of codewords: messages are encoded by writing codewords back-to-back. A decoder sees a long bit sequence and must parse it into codewords.
Uniquely decodable code: a code is uniquely decodable if every finite concatenated sequence of codewords has exactly one decomposition into codewords. This prevents ambiguous decoding of messages.
Prefix code (instantaneous code): a code is a prefix code if no codeword is a prefix of any other codeword. A prefix code is always uniquely decodable. Prefix codes are called instantaneous because decoding can proceed symbol-by-symbol as bits arrive (no lookahead needed).
Binary code tree (trie) representation: represent all binary strings as nodes at their corresponding depths in a full infinite binary tree where left edge = 0, right edge = 1. A prefix code corresponds to selecting a finite set of nodes with no node an ancestor of another; in the resulting pruned tree these selected nodes are the leaves.
Kraft inequality (binary): For any binary prefix code with codeword lengths l1, l2, …, ln (positive integers) we must have sum_{i=1..n} 2^{-l_i} ≤ 1. Conversely, for any set of positive integers satisfying this inequality there exists a binary prefix code with those lengths. This is a necessary and sufficient condition for existence of a binary prefix code with given lengths.
Important assumptions: code alphabet is binary, lengths are positive integers, and we consider instantaneous (prefix) codes. Note: some texts allow l_i = 0 for a one-symbol source; here we assume l_i ≥ 1. By the Kraft–McMillan theorem, the same inequality is necessary for any uniquely decodable binary code; since any feasible length set can be realized by a prefix code, it is without loss of optimality to restrict attention to prefix codes.
Typical proof idea (necessity): Choose a large depth N ≥ max l_i; each codeword at depth l_i occupies 2^{N-l_i} leaves among 2^{N} total leaves, and these occupied leaves are disjoint, so sum 2^{N-l_i} ≤ 2^{N} which simplifies to the Kraft inequality.
(Sufficiency) Constructive proof: use the tree and assign codewords greedily by taking leftmost available leaf positions; because the sum ≤ 1 there is enough room. Equality Σ 2^{-l_i} = 1 corresponds to a complete code (no unused capacity at some common depth), whereas strict inequality indicates unused capacity remains.
Average codeword length: if symbol i has probability p_i, average length L = sum_i p_i l_i. We measure efficiency by L.
Entropy H (binary logarithm): H = - sum_i p_i log2 p_i. H is the theoretical lower bound on average length per symbol for any lossless symbol-by-symbol code (Shannon's source coding bound, for memoryless source).
Bounds: For an optimal binary prefix code we have H ≤ L < H + 1. This assumes the p_i are probabilities summing to 1 and logarithm base 2.
Huffman coding (greedy algorithm): Given symbol probabilities p_i, Huffman's algorithm builds an optimal binary prefix code (minimizes L over prefix codes). Steps:
- Make a forest of nodes, each node representing a symbol with weight = p_i.
- Repeatedly: select two nodes with smallest weights, merge them into a new node whose weight is the sum of the two weights; make the two selected nodes its children.
- Repeat until a single tree (root) remains. Assign bits to edges (convention: left=0, right=1). Codewords are the bit-paths from root to leaves. Tie-breaking can change individual codewords but not the average length. Generalization: for a D-ary code alphabet, at each step merge the D nodes with smallest weights to obtain an optimal D-ary prefix code.
Huffman correctness idea (exchange argument): in any optimal tree, the two least probable symbols appear as sibling leaves at maximum depth. Merging them and solving smaller problem recursively gives optimality. Full formal proof uses induction replacing two least probable leaves by a single symbol with combined probability and comparing costs.
Complexity: Huffman using a binary heap (priority queue) runs in O(n log n) time for n symbols.
Formulas
L = Σ_i p_i · l_i — L is average codeword length (bits per source symbol). p_i is probability of symbol i (unitless), l_i is length in bits, applies to any code.
H = - Σ_i p_i · log2(p_i) — H is entropy in bits per symbol. p_i unitless, log base 2. Assumes discrete memoryless source.
Σ_i 2^{-l_i} ≤ 1 — Kraft inequality for binary prefix codes. l_i are positive integers (bits), necessary and sufficient for existence of a prefix code. More generally, for a D-ary code alphabet: Σ_i D^{-l_i} ≤ 1.
H ≤ L < H + 1 — bound for average length of an optimal binary prefix code. H and L in bits per symbol.
Time complexity: O(n log n) — Huffman algorithm time using a priority queue with n input symbols.
Worked examples
Example 1 — Build a Huffman code and compute average length and entropy.
Given symbols and probabilities: A:0.4, B:0.2, C:0.2, D:0.1, E:0.1. (Probabilities sum to 1.)
- Start with nodes: A(0.4), B(0.2), C(0.2), D(0.1), E(0.1).
- Merge two smallest: D(0.1) + E(0.1) → node DE(0.2).
- Nodes now: A(0.4), B(0.2), C(0.2), DE(0.2). Merge two smallest (choose B and C): B(0.2)+C(0.2) → BC(0.4).
- Nodes: A(0.4), BC(0.4), DE(0.2). Merge two smallest: DE(0.2)+A(0.4) → X(0.6).
- Nodes: BC(0.4), X(0.6). Merge → root(1.0).
Construct tree (convention: left=0, right=1). One valid assignment gives codes: B = 00, C = 01, D = 100, E = 101, A = 11.
Compute average length: L = 0.4·2 + 0.2·2 + 0.2·2 + 0.1·3 + 0.1·3 = 2.2 bits/symbol (final answer in bold: 2.2 bits/symbol).
Compute entropy: H = -[0.4·log2 0.4 + 0.2·log2 0.2 + 0.2·log2 0.2 + 0.1·log2 0.1 + 0.1·log2 0.1] ≈ 2.1219 bits/symbol.
Check bound: H ≤ L < H + 1 → 2.1219 ≤ 2.2 < 3.1219 holds.
Check Kraft: Σ 2^{-l_i} = 2^{-2}+2^{-2}+2^{-2}+2^{-3}+2^{-3} = 0.25+0.25+0.25+0.125+0.125 = 1.0, satisfies equality.
Example 2 — Kraft inequality demonstration and existence.
Given lengths l = {2, 2, 3}. Compute Σ 2^{-l_i} = 2^{-2}+2^{-2}+2^{-3} = 0.25+0.25+0.125 = 0.625 ≤ 1. By Kraft, a prefix code exists. One code with these lengths: 00, 01, 100.
(Show how to assign leaves in a binary tree: draw a full binary tree to depth 3. Pick leftmost unused leaves at depths corresponding to lengths.)
Common mistakes
- Building Huffman tree incorrectly: merging wrong pair (must always pick two smallest weights); tie-breaking is allowed but explain your choice.
- Wrong bit assignment after tree built: be consistent with left/right → 0/1 and compute depths carefully.
- Forgetting to multiply probabilities when computing L, or rounding intermediate values too early when comparing with entropy.
- Using natural log instead of log2 when computing entropy and forgetting to change units.
- Believing Huffman always achieves H exactly; Huffman gives L ≥ H and L < H + 1, not necessarily equal to H.
For your exam
Typical question types:
- Definitions: define prefix code, uniquely decodable, Kraft inequality, entropy.
- Short notes: explain Kraft inequality and its necessity/sufficiency for prefix codes; explain Huffman algorithm and its optimality idea.
- Derivations/proofs: prove Kraft inequality (necessity) for binary prefix codes; outline Huffman optimality using induction/exchange argument.
- Numericals: given a set of symbol probabilities, build Huffman tree, give codewords, compute average length L, entropy H, and verify H ≤ L < H + 1 and Kraft inequality.
- Programs/algorithms: write pseudocode for Huffman and analyse time complexity.
What full-marks answers include:
- Clear definitions with assumptions stated (binary alphabet, discrete memoryless source if entropy is used).
- For proofs, state the lemma, the base case, and induction step (for Kraft or Huffman optimality sketch).
- For numericals, show the priority-queue merges step-by-step, show final codes, compute L with units (bits/symbol) and compute H (use log2). Check Kraft inequality.
Quick check
- What is a prefix code? Give one reason why prefix codes are useful.
- State the Kraft inequality for binary prefix codes.
- Give the main greedy step of Huffman's algorithm (one sentence).
Answers: 1) A prefix code is a code in which no codeword is a prefix of another; useful because it is instantaneously decodable (decode symbol-by-symbol). 2) Σ_i 2^{-l_i} ≤ 1 for codeword lengths l_i (positive integers). 3) Repeatedly merge the two symbols/nodes with smallest weights into a single node whose weight is their sum, until one tree remains.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?