Huffman coding
Huffman coding: optimal variable-length prefix codes, tree construction with a min-priority queue, average code length, entropy bounds, canonical codes, and encode/decode procedures.
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
Key ideas
- Definition: A code maps each symbol s ∈ Σ to a finite binary string c(s) made of bits '0' and '1'. The code length ℓ(s) is the number of bits in c(s).
- Definition: A prefix code (also called a prefix-free code) is a code in which no codeword is a prefix of any other codeword. Assumption: binary alphabet D = 2 unless stated otherwise. Exact statement: A code C is prefix-free if and only if for any s ≠ t in Σ, c(s) is not a prefix of c(t).
- Definition: A Huffman code is a binary prefix code produced by Huffman's algorithm that minimizes average code length for a given set of symbol probabilities (or positive weights). Exact statement: For a given discrete memoryless source with probabilities p(s), the Huffman algorithm constructs an optimal prefix code C that minimizes L_avg = ∑ p(s)·ℓ(s).
- Definition: A Huffman tree is a full binary tree (every internal node has exactly two children) whose leaves correspond to symbols; each edge is labeled 0 or 1; the codeword for a symbol is the sequence of edge labels from root to its leaf; each leaf carries the symbol’s weight (probability or frequency); each internal node’s weight is the sum of its children’s weights.
- Definition: A priority queue (min-heap) is an abstract data type that supports insert and extract-min in O(log n) time; Huffman’s algorithm uses a min-priority queue keyed by node weights.
- Law (Kraft–McMillan inequality): For any binary prefix code over n symbols with code lengths ℓ1, ℓ2, …, ℓn, the following holds: ∑ 2^(−ℓi) ≤ 1. Conversely, for any set of positive integers ℓi satisfying this inequality, there exists a binary prefix code with those lengths. Assumptions: binary D = 2, instantaneous decoding.
- Theorem (Optimality of Huffman coding): For a given set of symbol probabilities (or weights), the prefix code produced by Huffman’s algorithm has minimum average length L_avg among all binary prefix codes. Assumptions: independent symbol draws (memoryless source), finite alphabet, positive probabilities/weights.
- Greedy choice property (used in proof): There exists an optimal code in which two least-probable symbols are siblings at the maximum depth. Therefore, merging the two least weights first is safe and leads to an optimal solution.
- Optimal substructure (used in proof): If two least-probability symbols are merged into a compound symbol, an optimal code for the reduced set, expanded by splitting the compound symbol into two children, yields an optimal code for the original set.
- Algorithm (Huffman construction):
- Make a leaf for each symbol with its weight (frequency or probability).
- Insert all leaves into a min-priority queue keyed by weight.
- While the queue has more than one node: extract the two nodes u and v with smallest weights; create a new internal node w with weight w(u)+w(v), set its left child to u (edge label 0) and right child to v (edge label 1), and insert w back into the queue.
- The remaining node is the root. Read codes from root to leaves. Note: The particular 0/1 assignment to left/right children does not change code lengths; it may change exact bit patterns but not optimality.
- Complexity: If n = |Σ|, using a binary heap: O(n log n) time and O(n) extra space. If the weights are presorted and a two-queue method is used, O(n) time is possible (not commonly required in exams but good to know).
- Average code length: L_avg = ∑ p(s)·ℓ(s) bits/symbol. For an optimal prefix code over a binary alphabet, Shannon’s bound applies: H(X) ≤ L_avg < H(X) + 1, where H(X) is source entropy in bits/symbol.
- Definition: Entropy H(X) is the expected information content: H(X) = −∑ p(s)·log2 p(s). It is a lower bound on average code length for any uniquely decodable binary code.
- Definition: Redundancy R = L_avg − H(X). For a Huffman code, 0 ≤ R < 1 bit/symbol.
- Uniquely decodable vs. prefix: All prefix codes are uniquely decodable; not all uniquely decodable codes are prefix-free. Huffman yields prefix-free, hence instantaneously decodable, codes.
- Canonical Huffman coding: A canonical code is a standardized way to assign the actual bit patterns given only the multiset of code lengths. Procedure: sort symbols by (ℓ, symbol order), assign the smallest binary value to the shortest code length, then increment in lexicographic order, left-padding with zeros to fit each length. This reduces the overhead of storing the codebook (store just lengths) and allows fast decoder table generation.
- Decoding: Bit-by-bit traversal from the root to a leaf; when a leaf is reached, output the symbol and return to root. With canonical codes, table-based decoding over fixed lookahead can speed this up.
- Ties and deterministic outputs: When frequencies tie, any consistent tie-breaking yields an optimal-length code. Different tie-breaks can give different bit patterns but the same lengths and L_avg.
- Extension to non-binary D-ary Huffman: The algorithm generalizes by merging D least weights at each step; the optimality and Kraft inequality adapt by replacing 2 with D. (Mention only; exams here usually use binary.) Additionally, to obtain a full D-ary tree with all internal nodes of degree D, if (n - 1) mod (D - 1) != 0, add zero-weight dummy symbols until (n' - 1) is divisible by (D - 1).
- Practical notes engineers face:
- You must transmit (or store) the codebook (tree or lengths) along with the compressed data unless a fixed code is agreed.
- Huffman is optimal among prefix codes at the single-symbol level. Better compression is possible by modeling (e.g., arithmetic coding, or Huffman on symbol blocks) or by dictionary methods (LZ family) plus Huffman.
Diagram to draw and label (when asked “draw the Huffman tree”):
- Draw leaves at the bottom, each labeled with the symbol and its weight (e.g., A: 45).
- Show internal nodes with their combined weights (sum of children).
- Connect edges upward when merging. Label left edges as 0 and right edges as 1.
- Finally, show codewords beside each leaf by reading 0/1 labels from root to leaf.
Proof sketch commonly asked (2–4 marks):
- Claim: In an optimal prefix code, two least probable symbols are siblings at maximum depth. If not, exchange codeword positions to reduce or not increase L_avg (exchange argument), contradicting optimality. Thus the greedy merge is safe.
- By merging two least weights into one, the reduced problem has optimal solution by induction; expanding back yields an optimal solution for the original.
Formulas
H(X) = −∑ p(s)·log2 p(s)— entropy of source X; unit: bit per symbol; applies to discrete memoryless source.H(X) ≤ L_avg < H(X) + 1— Shannon bound for optimal binary prefix codes; unit: bits per symbol; applies to Huffman or any optimal prefix code lengths.∑ 2^(−ℓi) ≤ 1— Kraft–McMillan inequality; ℓi are code lengths (bits); necessary and sufficient for existence of a binary prefix code.Time(Huffman) = O(n log n), Space = O(n)— with a binary min-heap; n: number of symbols.
Programming syntax to remember (Python heapq, often used for implementations):
import heapqheapq.heappush(heap, item)heapq.heappop(heap)heapq.heapify(list)
Worked examples
Example 1 (Theory/Numerical): Build Huffman code and compute L_avg and compare with entropy. Given symbols and probabilities: A: 0.4, B: 0.2, C: 0.15, D: 0.15, E: 0.1.
Steps:
- Initialize leaves with weights: A(0.40), B(0.20), C(0.15), D(0.15), E(0.10).
- Use a min-priority queue. Extract two smallest, merge, and reinsert. We will label left=0, right=1 each time for concreteness (any consistent choice yields the same lengths).
- Extract E(0.10) and C(0.15) → merge to node N1(0.25). Assign E as left (0), C as right (1).
- Extract D(0.15) and B(0.20) → merge to node N2(0.35). Assign D as left (0), B as right (1).
- Now we have A(0.40), N1(0.25), N2(0.35). Extract N1(0.25) and N2(0.35) → merge to N3(0.60). Assign N1 left (0), N2 right (1).
- Now A(0.40) and N3(0.60) remain. Merge to root R(1.00). Assign A left (0), N3 right (1).
- Read codes from root to leaves (0 for left, 1 for right):
- A: path 0 → code 0, ℓ(A)=1.
- N3: path 1 → continue.
- N1 is left of N3: path 10 → continue.
- E is left of N1: path 100 → code 100, ℓ(E)=3.
- C is right of N1: path 101 → code 101, ℓ(C)=3.
- N2 is right of N3: path 11 → continue.
- D is left of N2: path 110 → code 110, ℓ(D)=3.
- B is right of N2: path 111 → code 111, ℓ(B)=3.
- N1 is left of N3: path 10 → continue.
- Average code length: L_avg = 0.40·1 + 0.20·3 + 0.15·3 + 0.15·3 + 0.10·3 = 0.40 + 0.60 + 0.45 + 0.45 + 0.30 = 2.20 bits/symbol.
- Entropy:
H(X) = −[0.40·log2(0.40) + 0.20·log2(0.20) + 0.15·log2(0.15) + 0.15·log2(0.15) + 0.10·log2(0.10)]
Compute each term (log2 values rounded to 4 decimals):
- log2(0.40) ≈ −1.3219 → term ≈ 0.40·1.3219 = 0.5288
- log2(0.20) ≈ −2.3219 → term ≈ 0.20·2.3219 = 0.4644
- log2(0.15) ≈ −2.7360 → term ≈ 0.15·2.7360 = 0.4104 (same for both 0.15 terms)
- log2(0.10) ≈ −3.3219 → term ≈ 0.10·3.3219 = 0.3322 Sum: 0.5288 + 0.4644 + 0.4104 + 0.4104 + 0.3322 = 2.1462 bits/symbol (rounded to 4 decimals).
- Compare with Shannon bound: H(X) ≈ 2.1462 ≤ L_avg = 2.20 < H(X) + 1 ≈ 3.1462, satisfied.
- Redundancy: R = L_avg − H(X) ≈ 2.20 − 2.1462 = 0.0538 bits/symbol.
Model diagram description: Draw leaves for A(0.40), B(0.20), C(0.15), D(0.15), E(0.10). Show merges E+C → 0.25, D+B → 0.35, (0.25)+(0.35) → 0.60, A + 0.60 → 1.00. Label left edges 0, right edges 1, and annotate codes at leaves as above.
Example 2 (Programming): Python program to build a Huffman code, encode and decode a string, and also print average code length and entropy estimated from frequencies.
Complete Python code:
import heapq
from collections import Counter
from math import log2
class Node:
__slots__ = ("w", "sym", "left", "right")
def __init__(self, w, sym=None, left=None, right=None):
self.w = w
self.sym = sym
self.left = left
self.right = right
def __lt__(self, other):
# Break ties deterministically by (weight, symbol or id)
return (self.w, self.sym if self.sym is not None else "") < (other.w, other.sym if other.sym is not None else "")
def build_huffman(freq):
# freq: dict {symbol: frequency (positive int)}
heap = [Node(w, sym=s) for s, w in freq.items()]
if not heap:
return None, {}
heapq.heapify(heap)
if len(heap) == 1:
# Edge case: single symbol gets code "0"
only = heap[0]
root = Node(only.w, left=only, right=None)
codes = {only.sym: "0"}
return root, codes
while len(heap) > 1:
a = heapq.heappop(heap)
b = heapq.heappop(heap)
parent = Node(a.w + b.w, left=a, right=b)
heapq.heappush(heap, parent)
root = heap[0]
codes = {}
def dfs(n, path):
if n.sym is not None and n.left is None and n.right is None:
codes[n.sym] = path
return
if n.left is not None:
dfs(n.left, path + "0")
if n.right is not None:
dfs(n.right, path + "1")
dfs(root, "")
return root, codes
def encode(data, codes):
return "".join(codes[ch] for ch in data)
def decode(bits, root):
out = []
n = root
for b in bits:
n = n.left if b == "0" else n.right
if n.sym is not None and n.left is None and n.right is None:
out.append(n.sym)
n = root
return "".join(out)
def average_code_length(freq, codes):
total = sum(freq.values())
return sum((freq[s] / total) * len(codes[s]) for s in freq)
def entropy(freq):
total = sum(freq.values())
ps = [w / total for w in freq.values()]
return -sum(p * log2(p) for p in ps if p > 0)
if __name__ == "__main__":
data = input().rstrip("\n")
freq = Counter(data)
root, codes = build_huffman(freq)
if root is None:
print("Empty input")
else:
bits = encode(data, codes)
rec = decode(bits, root)
L = average_code_length(freq, codes)
H = entropy(freq)
print("Codes:")
for k in sorted(codes):
print(f"{repr(k)} -> {codes[k]}")
print("Encoded:")
print(bits)
print("Decoded:")
print(rec)
print("L_avg:", round(L, 6))
print("H(X):", round(H, 6))
print("Bounds OK:", (H <= L < H + 1))
Sample input:
BANANA
Exact output:
Codes:
'A' -> 1
'B' -> 00
'N' -> 01
Encoded:
001011011
Decoded:
BANANA
L_avg: 1.5
H(X): 1.459148
Bounds OK: True
Explanation of output:
- Frequencies: A:3, N:2, B:1 (total 6) → probabilities 0.5, 0.333333…, 0.166666…
- Huffman codes produced by the program (one optimal assignment): A:1 (1 bit), N:01 (2 bits), B:00 (2 bits).
- Average length L_avg = 0.5·1 + 0.333333…·2 + 0.166666…·2 = 1.5 bits/symbol.
- Entropy H(X) = −[0.5·log2 0.5 + (1/3)·log2 (1/3) + (1/6)·log2 (1/6)] ≈ 1.459148.
- Encoding BANANA using these codes gives bits: B(00) A(1) N(01) A(1) N(01) A(1) → 001011011.
Example 3 (Short theory): State and apply Kraft–McMillan inequality. Question: The code lengths for five symbols are {1, 3, 3, 3, 3}. Is a binary prefix code with these lengths possible? If yes, sketch a valid code. Solution:
- Compute sum 2^(−ℓi) = 2^(−1) + 4·2^(−3) = 1/2 + 4/8 = 1/2 + 1/2 = 1 ≤ 1, so the lengths are feasible.
- One valid code (consistent with Example 1): {A: 0, B: 111, C: 101, D: 110, E: 100} (any permutation of the 3-bit codes is acceptable). This satisfies prefix-free property and matches the lengths.
Common mistakes
- Forgetting to reinsert the merged node into the priority queue; or merging more than two nodes in the binary case.
- Assigning code bits but then writing them reversed (top-down vs. bottom-up confusion). Always derive codes as root-to-leaf paths.
- Believing the exact bit patterns are unique. Only lengths are fixed by optimality; different tie-breaks give different codes of the same lengths.
- Violating prefix-free property when manually inventing codes; always verify no codeword is a prefix of another.
- Forgetting the special case: if only one symbol exists, it must still get a codeword (commonly “0”) so decoding is unambiguous.
- Reporting L_avg in “bits” for a specific message instead of “bits per symbol.” Keep units clear: bits/symbol for averages; bits for a concrete encoded message.
- Not checking Shannon bound H ≤ L_avg < H + 1 when asked to compare with entropy.
- Calculating entropy with log base 10 or natural log without converting to base 2.
For your exam
- Short notes: steps of Huffman algorithm; complexity; canonical Huffman coding; why Huffman is optimal (greedy choice and optimal substructure in 3–5 lines).
- Derivations/proofs: sketch the exchange argument for the two least probable symbols being siblings; state and apply Kraft–McMillan inequality.
- Numericals: build the Huffman tree for given frequencies/probabilities; list codewords; compute L_avg; compute H(X) and comment on Shannon bound; compute compression ratio vs. fixed-length code where ℓ_fixed = ⌈log2 n⌉.
- Programs: write a program to construct codes, encode and decode; show sample I/O; handle edge cases (single symbol, empty input if allowed).
- Diagrams: draw and label the Huffman tree with weights and 0/1 on edges; show merges in correct order with combined weights.
- Comparison: short note comparing fixed-length coding vs. Huffman; mention that Huffman is optimal among prefix codes but not necessarily globally optimal vs arithmetic coding.
To get full marks:
- Write the steps of the algorithm clearly, show the priority queue contents after each merge, and annotate the final tree.
- Show all intermediate calculations for L_avg and H(X) with at least 3–4 decimal places, and conclude with a clear statement checking the inequality.
- If coding, provide complete, runnable code and sample I/O that matches exactly.
Quick check
- Define a prefix code and state the Kraft–McMillan inequality for binary codes.
- List the main steps of Huffman’s algorithm and its time complexity with a binary heap.
- A source has probabilities {0.5, 0.25, 0.25}. What are possible Huffman code lengths, and what is L_avg?
Answers: 1) Prefix code: no codeword is a prefix of another; Kraft–McMillan: ∑ 2^(−ℓi) ≤ 1. 2) Create leaves, push into min-heap, repeatedly extract two minima, merge, reinsert, repeat until one node; complexity O(n log n) time, O(n) space. 3) Code lengths can be {1,2,2}; L_avg = 0.5·1 + 0.25·2 + 0.25·2 = 1.5 bits/symbol.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?