Huffman Coding

Huffman coding maps symbols to variable-length bit strings. A prefix-free code has no codeword that is a prefix of another, so a decoder can walk one binary tree and emit a symbol as soon as it reaches a leaf. Prefix-free codes are uniquely decodable, although uniquely decodable codes do not all have the prefix-free property.

Prefix-Free Codes and Kraft’s Inequality #

For a binary prefix code with codeword lengths lᵢ, Kraft’s inequality is

Σ 2^(-lᵢ) ≤ 1

The inequality counts the fraction of the binary tree occupied by each leaf. Conversely, every positive integer length sequence satisfying it can be realized by a binary prefix code. Equality describes a complete tree; a strict inequality leaves unused branches.

Building a Frequency Tree #

Given symbol frequencies, Huffman’s algorithm repeatedly removes the two lowest-weight nodes, makes them siblings under a node whose weight is their sum, and reinserts that node. The depth of a symbol is its code length. Merging rare symbols deepest in the tree gives an intuitive exchange argument for optimality: moving a frequent symbol above a less frequent one cannot increase the weighted path length. The resulting tree minimizes expected length among binary prefix codes for the supplied frequencies.

while more than one node remains:
    a, b = remove the two lowest-weight nodes
    insert node(weight(a) + weight(b), a, b)

Equal weights permit multiple optimal trees. A deterministic implementation must define tie-breaking, for example by comparing a stable symbol ordinal after frequency. Determinism matters for reproducible output and tests, even though the expected bit count is unchanged. A format that imposes a maximum code length needs a length-limited Huffman algorithm; simply truncating a tree can violate Kraft’s inequality or change the intended symbol ordering.

Codebook overhead can exceed the savings for short or high-entropy input. Huffman coding is a representation choice, not a guarantee that every input gets smaller.

Canonical Reconstruction #

Many formats transmit code lengths rather than left/right tree pointers. Canonical construction sorts active symbols by (length, symbol order) and assigns consecutive integer codes within each length, shifting the next code left whenever the length increases. The decoder repeats that calculation, then inserts each code into a lookup table or decoding tree. Identical lengths therefore produce identical codes without transmitting tree shape.

For example, lengths (1, 2, 3, 3) for symbols A through D produce this canonical table:

The table records the logical code values. A bit-oriented format can serialize those values in a different order; DEFLATE, for example, reverses Huffman bits when packing them into the stream.

A decoder should build the table with checked arithmetic and reject:

• a code length outside the enclosing format’s limit;
• an oversubscribed set, where the lengths require more leaves than the tree contains;
• an incomplete set when the format requires a complete tree;
• duplicate or out-of-range symbols, malformed repeat instructions, and a missing required end-of-block symbol;
• a bit sequence that walks past the table or ends inside a code.

Lookup tables can decode several bits at a time, but the slow path must still validate the code length and remaining input. Treating an invalid table entry as a symbol converts malformed input into silent corruption.

For a concrete canonical format, see DEFLATE and Gzip Formats.

References #

• D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes,” Proceedings of the IRE, 1952.
• RFC 1951: DEFLATE, sections 3.2.1–3.2.2