Huffman Encoding — Header Order Bug Corrupts Data

Every time you compress a file with gzip, zip, or bzip2, Huffman coding is running somewhere in the pipeline. JPEG uses Huffman for its DCT coefficients. MP3 uses a Huffman variant for quantised audio data. The algorithm is from 1952 and is still in active production use in 2026 because it achieves optimal prefix-free codes — you cannot do better with fixed codes.

David Huffman invented this as a term paper assignment at MIT. His professor (Robert Fano) had worked on an earlier approach (Shannon-Fano coding) and assigned the problem thinking it was unsolvable. Huffman's insight — build the tree bottom-up from the least frequent symbols using a min-heap — was simpler and more elegant than Fano's top-down approach and provably optimal.

The Greedy Strategy — Min-Heap Merging

Build a min-heap from (frequency, character) pairs. Repeatedly extract the two minimum nodes and merge them into a new node with combined frequency. Repeat until one node remains — the root.

This bottom-up construction guarantees that the two least frequent symbols become siblings at the deepest level, which is the key to optimal prefix codes.

import heapq
from collections import Counter

class HNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = self.right = None
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(text: str) -> HNode:
    freq = Counter(text)
    heap = [HNode(ch, f) for ch, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HNode(None, left.freq + right.freq)
        merged.left, merged.right = left, right
        heapq.heappush(heap, merged)
    return heap[0]

def get_codes(root: HNode) -> dict[str, str]:
    codes = {}
    def dfs(node, code):
        if node.char is not None:
            codes[node.char] = code or '0'
            return
        dfs(node.left,  code + '0')
        dfs(node.right, code + '1')
    dfs(root, '')
    return codes

text = 'huffman encoding'
tree = build_huffman_tree(text)
codes = get_codes(tree)
for ch, code in sorted(codes.items()):
    print(f'{repr(ch)}: {code}')

Encoding and Decoding

Encoding: replace each character with its Huffman code. Decoding: traverse the tree bit by bit.

Decoding is done without lookahead: start at the root, read one bit at a time, go left on 0 and right on 1. When a leaf is reached, output the character and reset to the root. This works because no code is a prefix of another — the prefix-free property guarantees unambiguous parsing.

def huffman_encode(text: str, codes: dict) -> str:
    return ''.join(codes[ch] for ch in text)

def huffman_decode(encoded: str, root: HNode) -> str:
    result = []
    node = root
    for bit in encoded:
        node = node.left if bit == '0' else node.right
        if node.char is not None:
            result.append(node.char)
            node = root
    return ''.join(result)

encoded = huffman_encode('huffman', codes)
print(f'Encoded: {encoded}')
print(f'Bits: {len(encoded)} vs naive {len("huffman")*8}')
print(f'Decoded: {huffman_decode(encoded, tree)}')

Why Greedy is Optimal

Huffman's algorithm produces the optimal prefix-free code. Proof sketch: if two characters x, y have the lowest frequencies, there exists an optimal code where x and y are siblings at the deepest level (exchange argument). Merging them first maintains this property at each step. This is a classic greedy proof by exchange argument.

Complexity and Performance

Build tree: O(n log n) — n heap operations Encode: O(m) — m = text length Decode: O(m)

Compression ratio depends on entropy of the source. For English text, Huffman achieves ~4.5 bits/character vs 8 bits ASCII — about 44% compression.

Memory: tree size O(n) where n is alphabet size. For ASCII text, that's at most 256 leaves — negligible. For large alphabets (Unicode), tree overhead grows linearly.

Canonical Huffman Codes and DEFLATE

Instead of transmitting the entire Huffman tree (which can be larger than the compressed data for small files), DEFLATE uses canonical Huffman codes. The tree is reconstructed from a list of code lengths only — one length per symbol in alphabet order.

Canonical codes impose an ordering: codes of the same length are assigned in symbol order (e.g., 'a' gets 000, 'b' gets 001). This allows the decoder to rebuild the tree without any tree structure, just the lengths.

from collections import Counter
import heapq

def build_canonical_codes(text: str) -> dict[str, str]:
    # Step 1: get code lengths from Huffman tree
    freq = Counter(text)
    heap = [[f, ch, None, None] for ch, f in freq.items()]  # simulate HNode
    heapq.heapify(heap)
    while len(heap) > 1:
        l = heapq.heappop(heap)
        r = heapq.heappop(heap)
        heapq.heappush(heap, [l[0]+r[0], None, l, r])
    root = heap[0]

    lengths = {}
    def get_len(node, depth):
        if node[1] is not None:   # leaf
            lengths[node[1]] = depth
            return
        if node[2]: get_len(node[2], depth+1)
        if node[3]: get_len(node[3], depth+1)
    get_len(root, 0)

    # Step 2: assign canonical codes
    sorted_symbols = sorted(lengths.keys())  # symbol order
    # Group by length? For simplicity, just assign via standard algorithm:
    # ... (canonical code generation omitted for brevity; see full code in repo)
    return {}  # placeholder

# For a complete example, see the article's GitHub repository.

Huffman vs Arithmetic Coding

Huffman codes assign an integer number of bits per symbol. Arithmetic coding can assign fractional bits, achieving compression closer to the Shannon entropy limit. For highly skewed distributions (e.g., one symbol appears 90% of the time), arithmetic coding can outperform Huffman by a wide margin.

However, arithmetic coding is slower and more complex to implement — patents historically limited its use. JPEG and MPEG still use Huffman; newer codecs like HEVC use arithmetic coding (CABAC).