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.
From frequencies to a prefix code
A code is prefix-free when no symbol's bit string prefixes another symbol's code. Decoding can then walk the tree until a leaf without separators. Leaf depth is code length, so minimizing encoded size means minimizing the frequency-weighted external path length.
Fixed-length codes ignore frequency. Huffman uses more bits for rare symbols so common symbols can use fewer, reducing total bits without losing exact decodability.
- Leaves represent symbols
- Depth equals code length
- Prefix-free codes decode unambiguously
The greedy merge
Insert one leaf per positive-frequency symbol into a min-heap. Remove the two lightest trees, attach them below a new parent whose weight is their sum, and insert that parent. Repeating K−1 merges leaves one tree.
Assign zero to one child edge and one to the other. Swapping left and right changes the bit strings but not their lengths or optimal cost. Deterministic tie-breaking is useful for reproducible output but is not required for optimality.
- Two minima become siblings
- Parent weight is their sum
- Ties may yield different optimal codes
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'));
}
}A:5, B:2, C:1Codes: A=1, B=01, C=00Run the example step by step
Why the greedy choice is optimal
In some optimal prefix tree, the two least frequent symbols can be placed as deepest siblings: exchanging a less frequent symbol with a deeper more frequent one cannot increase cost. Contract those siblings into one combined symbol, solve the smaller optimal problem, then expand them.
This exchange-and-induction argument is the reason the local merge produces a global optimum. Greedy choice is not justified merely because it feels economical.
- Least frequencies can be deepest siblings
- Contract to a smaller instance
- Induction proves optimality
Complexity and canonical codes
For K distinct symbols, heap merging is O(K log K); counting frequencies is O(N). The tree and frequency table are metadata the decoder must know. Canonical Huffman stores only code lengths and reconstructs a standardized code assignment compactly.
Huffman minimizes expected code length among symbol-by-symbol prefix codes with integral bit lengths. Arithmetic coding can approach entropy more closely by encoding sequences fractionally, so 'optimal compression' needs this precise boundary.
- Count input in O(N)
- Merge K leaves in O(K log K)
- Optimal within binary prefix codes
Single symbols and corrupted streams
With one distinct symbol, assign a one-bit code such as 0; an empty code would not record repetition count in an ordinary bit stream. Empty input produces no tree. Zero-frequency symbols should not be inserted.
A decoder must also know the original symbol count or an end marker, since padding bits can otherwise resemble data. Real formats add headers, canonical tables, block boundaries, and integrity checks around the core tree algorithm.
- Handle one-symbol alphabets
- Exclude zero-frequency symbols
- Store decoding metadata
Encoding and decoding end to end
Build a symbol-to-code table by walking from the final root to each leaf, then encode by concatenating those bits. Decode by starting at the root, following each bit, emitting a symbol at a leaf, and returning to the root. Reaching the end of the stream inside an internal node indicates truncated or corrupt input. A serialized format must transmit the tree or canonical code lengths before the payload can be interpreted.
Test empty input, one repeated symbol, equal frequencies, non-ASCII symbols, and a stream ending mid-code. Verify prefix freedom by ensuring no leaf code is a prefix of another and verify cost by summing frequency times code length. Heap tie-breaking may change the literal bit strings, so tests should compare decoded data and weighted length unless the implementation promises canonical deterministic codes.
Because frequencies must be known before a static tree is built, Huffman commonly uses two passes or buffers a block. Adaptive variants update a model while streaming, but they require encoder and decoder to perform identical updates and are a different algorithmic contract.
- Decoder resets at every leaf
- Metadata is required with the payload
- Tie-safe tests compare meaning, not arbitrary bits