Huffman Coding, in depth: optimal prefix codes, canonical codes, length limits and table-driven decoding

The problem: prefix codes and their limits

You know how often each symbol appears and want binary codewords that make the message as short as possible and decodable without separators. A prefix code achieves the second goal: no codeword is a prefix of another, so a decoder reading left to right knows the moment a codeword ends. Every prefix code is a binary tree with symbols at the leaves; a codeword is the root-to-leaf path and its length is the leaf's depth.

Two facts bound what is possible. The Kraft inequality says a prefix code with lengths l1, l2, and so on exists if and only if the sum of 2 to the power minus li is at most 1. When the sum is exactly 1 the code is complete: every bit pattern eventually lands on a symbol. And Shannon's source coding theorem says the average length can never fall below the entropy H, the sum of minus p times log2 p over the symbols. Huffman's code achieves the smallest possible average among all prefix codes with integer lengths, and that average is always below H plus 1 bit per symbol.

The greedy construction

Put every symbol into a min-priority queue keyed by frequency. Repeatedly remove the two lightest items, make them siblings under a new node whose weight is their sum, and push the new node back. When one item remains it is the root. Each merge pushes every symbol in both subtrees one level deeper, so a symbol's code length is simply the number of merges it took part in. With a binary heap the whole build is O(n log n) for n symbols; see heap operations for the queue itself. If the input is already sorted by frequency, a two-queue method builds the same code in O(n).

Why is this optimal? Some optimal tree has the two rarest symbols as siblings at the deepest level, since moving a rarer symbol deeper never increases cost; merging them leaves a smaller problem of the same shape. Exchange argument plus optimal substructure is the whole proof.

import heapq, itertools

def code_lengths(freqs):
    """Return {symbol: code length}. Ties break on a counter, so output is deterministic."""
    if not freqs:
        return {}
    if len(freqs) == 1:                       # one symbol still needs a 1-bit code
        return {next(iter(freqs)): 1}
    tick = itertools.count()
    heap = [(w, next(tick), [s]) for s, w in sorted(freqs.items())]
    heapq.heapify(heap)
    depth = dict.fromkeys(freqs, 0)
    while len(heap) > 1:
        w1, _, a = heapq.heappop(heap)
        w2, _, b = heapq.heappop(heap)
        for s in a + b:                       # every symbol under the merge goes one level deeper
            depth[s] += 1
        heapq.heappush(heap, (w1 + w2, next(tick), a + b))
    return depth

Worked example: six symbols

Take a stream of 100 symbols with counts A 40, B 20, C 15, D 12, E 8 and F 5. A fixed-length code needs 3 bits per symbol for six symbols, so 300 bits. The merges run as follows.

Counting merges per symbol gives lengths A 1, B 3, C 3, D 3, E 4, F 4. The Kraft sum is 1/2 + 3/8 + 2/16 = 1, so the code is complete. The encoded size is 40 + 60 + 45 + 36 + 32 + 20 = 233 bits, or 2.33 bits per symbol. The entropy of this distribution is about 2.278 bits, so no symbol-by-symbol code could do better than about 227.8 bits; Huffman lands within 2.3 percent of the floor and saves 22 percent against fixed-length.

What was not decided is which child gets 0 and which gets 1, so two encoders can emit different bits from the same frequencies. Canonical codes remove that ambiguity.

Canonical codes: send lengths, not trees

A decoder needs to know the code, and sending a tree is wasteful and fiddly. Canonical Huffman codes fix this: given only the length of each symbol's code, both sides assign codewords by the same rule. Sort symbols by length, then by symbol value. The first gets all zeros; each next code is the previous code plus one, shifted left whenever the length increases. The result is still a prefix code with exactly the same lengths, so it is still optimal.

def canonical(lengths):
    """{symbol: length} -> {symbol: (code, length)}, assigned in (length, symbol) order."""
    order = sorted((l, s) for s, l in lengths.items() if l > 0)
    if not order:
        return {}
    codes, code, prev = {}, 0, order[0][0]
    for l, s in order:
        code <<= (l - prev)
        prev = l
        codes[s] = (code, l)
        code += 1
    return codes

For the example this yields A = 0, B = 100, C = 101, D = 110, E = 1110, F = 1111. The header needs one small integer per alphabet entry, 0 meaning unused; DEFLATE even Huffman-codes that list of lengths. Because codes of one length form a contiguous numeric range, decoders can also work from a per-length first-code table instead of a tree, much as a trie walk becomes a range check.

Limiting code length

Unrestricted Huffman codes can get long. Frequencies that grow like the Fibonacci sequence produce a code whose maximum length is n minus 1, and real data with a long tail of rare symbols can exceed what a format allows. Formats cap lengths for a practical reason: the decoder's lookup table has 2 to the power L entries and its bit buffer must hold a full codeword. DEFLATE limits literal, length and distance codes to 15 bits; baseline JPEG limits codes to 16 bits.

Two standard ways respect a limit L. Package-merge (Larmore and Hirschberg, 1990) computes the optimal length-limited code in O(nL) time. The common engineering route, used by zlib, builds the normal code and repairs it: clamp overlong codes to L, which over-subscribes the Kraft sum, then lengthen shorter codes until the sum is exactly 1 again. The repair is not always optimal, but it only touches rare symbols, so the loss is tiny.

On the example, a 3-bit limit forces lengths of 2 or 3. The best assignment satisfying Kraft is A 2, B 2 and the other four at 3, costing 240 bits: 7 bits (3 percent) more, for an 8-entry decode table instead of 16.

Bit I/O and table-driven decoding

Two details decide whether an implementation interoperates: bit order and padding. This article packs codes most-significant bit first into bytes, which is the natural order for the table lookup below. DEFLATE is different: it fills bytes from the least significant bit and stores Huffman codes with their bits reversed relative to that order, which trips up many first implementations. Whatever you choose, write it down in the format specification.

Padding is the other trap. The last byte is padded with zeros, and zeros can look like a valid codeword. The decoder must know where to stop, either from a symbol count in the header or from a dedicated end-of-block symbol, which is what DEFLATE uses.

class BitWriter:
    def __init__(self):
        self.acc, self.n, self.out = 0, 0, bytearray()

    def write(self, code, length):            # append `length` bits, MSB first
        self.acc = (self.acc << length) | code
        self.n += length
        while self.n >= 8:
            self.n -= 8
            self.out.append((self.acc >> self.n) & 0xFF)
        self.acc &= (1 << self.n) - 1

    def flush(self):
        if self.n:
            self.out.append((self.acc << (8 - self.n)) & 0xFF)
        return bytes(self.out)

def build_table(codes, max_len):
    """Every max_len-bit window whose prefix is a codeword maps to (symbol, length)."""
    table = [None] * (1 << max_len)
    for s, (code, l) in codes.items():
        start = code << (max_len - l)
        for i in range(start, start + (1 << (max_len - l))):
            table[i] = (s, l)
    return table

def decode(data, codes, n_symbols):
    max_len = max(l for _, l in codes.values())
    table = build_table(codes, max_len)
    bits, total, pos, out = int.from_bytes(data, "big"), len(data) * 8, 0, []
    for _ in range(n_symbols):
        avail = total - pos
        if avail >= max_len:
            window = (bits >> (avail - max_len)) & ((1 << max_len) - 1)
        else:                                  # near the end, pad the window with zeros
            window = (bits & ((1 << avail) - 1)) << (max_len - avail)
        entry = table[window]
        if entry is None or entry[1] > avail:
            raise ValueError("corrupt stream")
        out.append(entry[0])
        pos += entry[1]
    return out

The decoder peeks max_len bits, does one lookup, emits the symbol and advances by its real length. The big-integer reader keeps the example short but is quadratic on large inputs; a real decoder refills a 64-bit buffer. For long codes, decoders use two levels: a primary table of 9 to 11 bits resolves the common short codes and stays in L1 cache, and rare long codes fall through to small secondary tables.

Validating headers from untrusted input

Treat a length table from a file as hostile. Check every length is between 0 and the format's maximum, then compute the Kraft sum in integers: the sum of 2 to the power (L minus li) over used symbols. Above 2 to the power L, the code is over-subscribed: codewords overlap and the table builder silently overwrites entries. Below it, the code is incomplete and some windows map to nothing, so the decoder must check for empty entries. Some formats allow incomplete codes in narrow cases, such as a single used symbol, so follow the specification exactly.

Failure modes

• Zero or one distinct symbol. With no symbols the heap loop never runs and some implementations index an empty list; with one symbol the naive build returns length 0 and encodes the message as no bits at all. Give a lone symbol a 1-bit code, or encode the run length directly.
• Non-deterministic ties. Pushing raw tuples of weight and subtree into a heap compares subtrees on ties, which can raise a TypeError in Python or depend on memory addresses elsewhere. Break ties on a counter or symbol value so the same input always yields the same output, which reproducible builds and golden-file tests need.
• Length overflow. A skewed sample, such as a small block with a long tail, quietly produces a 17-bit code in a format that allows 15. Always run the length limiter, even if typical data never needs it.
• Stale statistics. A static table built from last month's data can lose to fixed-length codes today; per-block tables, as in DEFLATE, avoid this for the price of a header each.
• Header overhead on tiny inputs. The header can cost more than it saves; compare against a stored or fixed-code fallback, as DEFLATE's block types do.

Trade-offs: Huffman, arithmetic coding and ANS

Huffman's weakness is integer lengths. A symbol with probability 0.9 ideally costs about 0.15 bits but must cost at least 1, so for highly skewed sources, like binary flags or the output of a good context model, the loss is large. Arithmetic coding and asymmetric numeral systems (ANS) assign fractional bits and approach the entropy almost exactly. Huffman's strengths are speed and simplicity: decoding is a table lookup with no multiplications, it is unencumbered, and every platform already has a tested implementation.

A useful rule: if the largest symbol probability stays well below one half and decode speed matters, Huffman is the right default; if a few symbols dominate or you are coding an adaptive model's output, use ANS or arithmetic coding. And if codewords must keep the symbols' sort order (alphabetic codes, optimal binary search trees), greedy merging no longer works and you need dynamic programming.

What to do next

1. Run the code_lengths and canonical functions on the six-symbol example and confirm you get lengths 1, 3, 3, 3, 4, 4, 233 bits, and codes 0, 100, 101, 110, 1110, 1111.
2. Round-trip a real file through BitWriter and decode, with the symbol count in a header, and assert the output equals the input.
3. Add a Kraft check to the decoder path and fuzz it with random length tables; every input must decode or raise ValueError, never crash or loop.
4. Implement the clamp-and-repair length limiter for a 15-bit cap and measure the size loss on a skewed sample against the unlimited code.
5. Replace the big-integer reader with a 64-bit buffer and a two-level table, and benchmark decode throughput.
6. Read the DEFLATE specification's section on Huffman codes and note exactly where its bit order differs from the MSB-first packing used here.