Huffman coding

Deep dive

How it works

In: a block of symbols (bytes) with their counts · Out: canonical code lengths, then a bit stream of codewords · State: none between blocks (the code table travels in the block header) · Cost: build O(n log n) for n symbols; encode and decode O(1) per symbol

1. Count symbol frequencies over a block (e.g., 128 KB).
2. Put all non-zero symbols in a min-heap; pop two lowest, push a parent with the summed weight; repeat until one node is left. A symbol's depth is its code length.
3. Limit lengths to L (15 for DEFLATE). Optimal: package-merge. Common shortcut: flatten frequencies and rebuild, or move leaves up and rebalance (Kraft sum ≤ 1).
4. Assign canonical codes: sort by (length, symbol); codes of one length are consecutive integers; moving to the next length appends a 0 bit.
5. Transmit the lengths (DEFLATE even Huffman-codes the lengths themselves, then run-length codes them).
6. Decode: peek L bits, look up (symbol, length) in a 2^L table, consume length bits.

freq: a=45 b=13 c=12 d=16 e=9 f=5
merge f+e=14, c+b=25, 14+d=30, 25+30=55, a+55=100
lengths: a=1 b=3 c=3 d=3 e=4 f=4
canonical: a=0  b=100 c=101 d=110  e=1110 f=1111

Code

use std::cmp::Reverse;
use std::collections::BinaryHeap;

/// Huffman code lengths per symbol (0 = absent). Unbounded length.
pub fn code_lengths(freq: &[u64]) -> Vec<u8> {
    let mut parent = vec![usize::MAX; freq.len()]; // leaves 0..n, internal nodes appended
    let mut heap: BinaryHeap<Reverse<(u64, usize)>> = freq.iter().enumerate()
        .filter(|&(_, &f)| f > 0).map(|(s, &f)| Reverse((f, s))).collect();
    let mut lens = vec![0u8; freq.len()];
    if heap.len() == 1 { let Reverse((_, s)) = *heap.peek().unwrap(); lens[s] = 1; return lens; }
    while heap.len() > 1 {
        let Reverse((fa, a)) = heap.pop().unwrap();
        let Reverse((fb, b)) = heap.pop().unwrap();
        let id = parent.len();
        parent.push(usize::MAX);
        parent[a] = id;
        parent[b] = id;
        heap.push(Reverse((fa + fb, id)));
    }
    for s in 0..freq.len() {
        let mut v = s;
        while freq[s] > 0 && parent[v] != usize::MAX { v = parent[v]; lens[s] += 1; }
    }
    lens
}

/// Length-limited by flattening: halve counts until max length <= limit (simple, slightly suboptimal).
pub fn limited_lengths(freq: &[u64], limit: u8) -> Vec<u8> {
    let mut f = freq.to_vec();
    loop {
        let lens = code_lengths(&f);
        if lens.iter().all(|&l| l <= limit) { return lens; }
        for x in f.iter_mut().filter(|x| **x > 0) { *x = (*x + 1) / 2; } // stays >= 1
    }
}

/// Canonical codes, DEFLATE rule (RFC 1951 section 3.2.2).
pub fn canonical_codes(lens: &[u8]) -> Vec<u32> {
    let max = *lens.iter().max().unwrap_or(&0) as usize;
    let mut count = vec![0u32; max + 1];
    for &l in lens { if l > 0 { count[l as usize] += 1; } }
    let (mut next, mut code) = (vec![0u32; max + 1], 0u32);
    for bits in 1..=max { code = (code + count[bits - 1]) << 1; next[bits] = code; }
    lens.iter().map(|&l| {
        if l == 0 { return 0; }
        let c = next[l as usize];
        next[l as usize] += 1;
        c
    }).collect()
}

pub fn encode(data: &[u8], lens: &[u8]) -> Vec<u8> {
    let codes = canonical_codes(lens);
    let (mut out, mut acc, mut n) = (Vec::new(), 0u64, 0u32);
    for &b in data {
        acc = (acc << lens[b as usize]) | codes[b as usize] as u64; // MSB-first
        n += lens[b as usize] as u32;
        while n >= 8 { n -= 8; out.push((acc >> n) as u8); }
    }
    if n > 0 { out.push((acc << (8 - n)) as u8); }
    out
}

pub struct Decoder { table: Vec<(u8, u8)>, bits: u32 } // (symbol, length) by next `bits` bits

impl Decoder {
    pub fn new(lens: &[u8]) -> Self {
        let bits = *lens.iter().max().unwrap() as u32;
        let mut table = vec![(0u8, 0u8); 1 << bits];
        for (s, (&l, &c)) in lens.iter().zip(&canonical_codes(lens)).enumerate() {
            if l == 0 { continue; }
            let shift = bits - l as u32; // every suffix of the code maps to this symbol
            let start = (c as usize) << shift;
            table[start..start + (1 << shift)].fill((s as u8, l));
        }
        Decoder { table, bits }
    }
    /// Symbol count must be known (or use an end-of-block symbol, as DEFLATE does).
    pub fn decode(&self, input: &[u8], count: usize) -> Vec<u8> {
        let (mut acc, mut n, mut pos) = (0u64, 0u32, 0usize); // acc is left-aligned
        let mut out = Vec::with_capacity(count);
        while out.len() < count {
            while n <= 56 { acc |= (*input.get(pos).unwrap_or(&0) as u64) << (56 - n); n += 8; pos += 1; }
            let (sym, len) = self.table[(acc >> (64 - self.bits)) as usize];
            out.push(sym);
            acc <<= len;
            n -= len as u32;
        }
        out
    }
}

Complexity and constants

• Build: O(n log n); n = 256 takes microseconds, irrelevant next to a 128 KB block.
• Decode: one table load + shift per symbol. Table of 2^11 two-byte entries = 4 KB, stays in L1. A 15-bit single-level table (64 KB) spills L1, so zlib uses two levels (9-bit root for literal/length, 6-bit for distance).
• Redundancy: average length L̄ satisfies H ≤ L̄ < H + 1. Gallager's tighter bound: L̄ − H ≤ p_max + 0.086 (for p_max < 0.5).
• Header cost: about 100-200 bytes for 256 code lengths, which is why tiny blocks should fall back to raw or a predefined code (DEFLATE "fixed Huffman" blocks).

Efficiency

• Cost: build O(n log n), microseconds for n = 256. Decode is one table load and shift per symbol; an 11-bit table of two-byte entries is 4 KB and stays in L1, while a 15-bit single-level table (64 KB) spills it, so zlib uses two levels. Header: about 100-200 bytes for 256 code lengths. Zstd's Huff0 with 4 interleaved streams decodes at order of 1-2 GB/s per core. Bound: latency, because each symbol's length decides the next shift.
• Levers:
  • 4 interleaved bitstreams (Huff0 jump table) — 4 dependency chains in parallel — large blocks
  • multi-symbol tables (libdeflate, Huff0 X2) — one lookup emits 2+ symbols — short codes, large L
  • two-level tables (zlib: 9-bit root, 6-bit second level) — keeps the hot table in L1 — L above 11
  • branch-free refill (8-byte unaligned read, advance by (63 - n) >> 3) — no refill branch — all decoders
  • predefined codes for tiny blocks (DEFLATE fixed Huffman) — skips the header — blocks under a few KB
• Naive → standard → state of the art:
  • walk the code tree bit by bit · one data-dependent branch per bit
  • canonical code, single-stream table lookup · one load per symbol, latency-bound
  • interleaved streams plus multi-symbol tables · order of 1-2 GB/s per core (zstd Huff0)

Implementation notes

• Decode speed is latency-bound: each symbol's length decides the next shift. Interleave 4 independent bitstreams (Huff0 splits literals into 4 streams with a jump table) to run 4 dependency chains in parallel.
• Multi-symbol tables: when L is large and codes short, one lookup can emit 2+ symbols (libdeflate, Huff0 "X2" decoder).
• Refill branch-free: read 8 bytes unaligned, shift in, advance by (63 - n) >> 3 bytes; requires 8 bytes of input padding.
• Bit order: DEFLATE packs LSB-first and stores Huffman codes bit-reversed; JPEG and the code above are MSB-first. Mixing them is the classic bug.
• Length limiting: package-merge (Larmore and Hirschberg) is optimal in O(nL). zstd and zlib use heuristics that redistribute depth while keeping the Kraft sum at exactly 1.

Pitfalls

• A single-symbol alphabet gets length 0 from the tree; force length 1 (the code above does).
• Unbounded depth: Fibonacci-like frequencies give depth n − 1; always length-limit before building a fixed-size table.
• Incomplete codes (Kraft sum < 1) leave table holes; validate lengths from untrusted headers or the decoder reads garbage.
• Forgetting to transmit symbol count or an end marker; trailing padding bits decode as phantom symbols.
• Per-block headers dominate for blocks under a few KB.

Variants and alternatives

In production

File formats and archives: DEFLATE (gzip, zlib, PNG, ZIP), zstd literals (Huff0), Brotli prefix codes. Media: JPEG baseline, MP3/AAC spectral data. Web and networking: HPACK/QPACK static Huffman for HTTP header strings (RFC 7541, RFC 9204).

Implementations

Sources

• D. A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proc. IRE, 1952. paper
• R. G. Gallager, Variations on a Theme by Huffman, IEEE Trans. Information Theory, 1978. paper
• L. L. Larmore, D. S. Hirschberg, A Fast Algorithm for Optimal Length-Limited Huffman Codes, JACM, 1990. paper
• P. Deutsch, RFC 1951: DEFLATE Compressed Data Format Specification 1.3, 1996. RFC
• H. Peon, H. Ruellan, RFC 7541: HPACK: Header Compression for HTTP/2, 2015. RFC