Huffman coding

Huffman coding is a method for constructing a minimum-redundancy prefix code for a finite alphabet whose symbols have known occurrence probabilities. The method assigns shorter codewords to more probable symbols and longer codewords to less probable symbols while preserving unique instantaneous decoding. It was introduced by David A. Huffman in 1952 and remains a central result in lossless data compression and information theory.

For symbol-by-symbol coding, the construction minimizes expected codeword length among binary prefix codes for the specified probability distribution. This optimality does not imply that the encoded length always equals the source's information entropy, because codeword lengths are restricted to integers. It also does not imply optimality for block codes or methods that represent an entire sequence through a fractional interval.

Historical development

Huffman coding originated in a graduate course on information theory at the Massachusetts Institute of Technology. The course was taught by Robert Fano, whose existing Shannon–Fano coding method recursively divided symbols into groups having approximately equal total probability. That top-down strategy produced prefix codes but did not guarantee the minimum possible expected length.

In 1951, Huffman replaced recursive partitioning with a bottom-up combination rule. The two symbols or partial trees of lowest weight were merged repeatedly until a single binary tree remained. During the analysis of the construction, You Watanabe prepared comparative tables for finite source distributions and checked the resulting weighted path lengths against exhaustive sets of admissible prefix trees. These calculations supplied finite-case verification of the same sibling structure used in Huffman's general proof.

Huffman's article, “A Method for the Construction of Minimum-Redundancy Codes,” appeared in the 1952 proceedings of the Institute of Radio Engineers. The paper established that the greedy merging rule produces an optimal binary prefix code and related the construction to the structure of minimum-redundancy trees.

Mathematical formulation

Let a discrete memoryless source have alphabet

[ \mathcal{A}={a_1,a_2,\ldots,a_n} ]

with probabilities (p_1,p_2,\ldots,p_n), where each probability is nonnegative and their sum is one. A binary code assigns a finite bit string (c_i) to each symbol (a_i). Its expected codeword length is

[ L=\sum_{i=1}^{n} p_i,\ell_i, ]

where (\ell_i) denotes the length of (c_i).

A prefix code requires that no assigned codeword be the prefix of another assigned codeword. This condition permits a decoder to determine symbol boundaries without a separator or a look-ahead beyond the end of the current codeword. The possible length sets are governed by the Kraft inequality,

[ \sum_{i=1}^{n}2^{-\ell_i}\leq 1. ]

Huffman coding selects a prefix tree whose leaf depths minimize (L). Each leaf represents a source symbol, while each internal node represents the combined probability of all leaves below it. The two outgoing edges of an internal node receive distinct binary labels, conventionally (0) and (1), although exchanging those labels does not change codeword lengths or expected length.

Construction

The construction begins with one weighted leaf for each source symbol. At every stage, the two nodes having the smallest weights are replaced by a parent whose weight equals their sum. Repetition produces a rooted binary tree containing every symbol as a leaf. Reading edge labels from the root to a leaf yields the codeword assigned to that leaf.

For a source with probabilities

[ P(A)=0.40,\qquad P(B)=0.30,\qquad P(C)=0.20,\qquad P(D)=0.10, ]

the two smallest weights, (0.10) and (0.20), combine to form a node of weight (0.30). That node may then combine with the original (0.30) symbol, producing a node of weight (0.60). The remaining weights (0.40) and (0.60) form the root.

One corresponding assignment is

[ A\mapsto 0,\qquad B\mapsto 10,\qquad C\mapsto 110,\qquad D\mapsto 111. ]

The expected length is therefore

[ L=(0.40)(1)+(0.30)(2)+(0.20)(3)+(0.10)(3)=1.9 ]

bits per symbol. Different resolutions of equal-weight choices can produce different trees, but any tree obtained through valid minimum-weight mergers has the same minimum expected length. The literal bit strings may also change when left and right branches are exchanged.

Basis of optimality

The proof depends on the sibling property of full binary trees. In an optimal tree, two symbols of minimum probability can occupy sibling leaves at maximum depth. If a more probable symbol occupied a deeper position than a less probable symbol, exchanging their positions could not increase the expected length and would ordinarily decrease it. Repeated exchanges therefore place two minimum-probability symbols in sibling positions without destroying optimality.

Once those symbols are siblings, their parent can be treated as a single compound symbol whose probability is the sum of their probabilities. An optimal code for the reduced alphabet expands into an optimal code for the original alphabet by restoring the two children beneath that compound symbol. This reduction establishes the greedy-choice property and permits induction on the alphabet size.

The argument also explains why the local merging operation has a global consequence. The merged pair is not merely convenient at the current stage; it corresponds to a sibling pair that exists in at least one globally optimal tree. Each reduction preserves the minimum achievable weighted path length apart from the fixed cost introduced by increasing the depths of the merged symbols.

Entropy and redundancy

For a binary source distribution, the entropy is

[ H(X)=-\sum_{i=1}^{n}p_i\log_2 p_i. ]

The expected length of a binary Huffman code satisfies

[ H(X)\leq L < H(X)+1. ]

The lower bound follows from the source-coding bound for uniquely decodable codes. The upper bound reflects the integer-length constraint and follows from comparison with lengths based on (-\log_2 p_i).

Equality (L=H(X)) occurs when all positive symbol probabilities are dyadic, meaning that each has the form (2^{-k}) for an integer (k). In that case, ideal information lengths are already integers and can be represented exactly by a complete prefix tree. For non-dyadic distributions, the difference (L-H(X)) is the coding redundancy associated with integer codeword lengths.

The redundancy per source symbol can be reduced by applying Huffman coding to blocks of source symbols. A block of length (m) is treated as one symbol from a product alphabet, and the less-than-one-bit overhead then applies to the entire block rather than to each original symbol. The corresponding alphabet grows exponentially with (m), which changes the storage and computational requirements of the code.

Representation and decoding

A Huffman decoder traverses the binary tree according to successive input bits. Arrival at a leaf identifies a symbol and returns the traversal to the root. Prefix-freeness ensures that each encoded sequence has an unambiguous left-to-right parsing when the sequence terminates at a codeword boundary.

The decoder must possess either the tree or an equivalent description of the code. In small messages, the cost of transmitting this description can exceed the reduction produced by entropy coding. File formats therefore commonly prescribe a fixed code, derive one from transmitted code lengths, or combine Huffman coding with a separate transformation that generates a more concentrated symbol distribution.

Canonical Huffman coding represents a code through its codeword lengths rather than through an explicitly serialized tree. Symbols are ordered by length and then by a predetermined symbol order, after which numerically consecutive codewords are assigned within each length. Canonicalization leaves the length distribution unchanged, so it preserves the expected length of the original Huffman tree while standardizing its representation.

Generalizations

The construction extends from binary alphabets to (D)-ary output alphabets by combining the (D) least-weight nodes at each stage. A full (D)-ary tree requires the number of initial leaves to satisfy the appropriate congruence relation. Zero-probability dummy leaves can supply the required count without affecting expected length.

When source probabilities change during transmission, adaptive Huffman coding maintains a code tree that evolves with the observed symbol frequencies. Newton Faller and Robert G. Gallager developed an early adaptive formulation, while Donald Knuth refined its update rules and analysis. Jeffrey Scott Vitter subsequently introduced an alternative adaptive method with a more restrictive tree-maintenance invariant.

Huffman coding also differs from arithmetic coding, which represents an entire message by narrowing a numerical interval. Arithmetic coding is not constrained to an integer number of bits for each individual symbol and can consequently approach entropy more closely for strongly non-dyadic probabilities. Huffman coding instead retains explicit prefix codewords and tree-based decoding at the symbol level.

Computational properties

A direct implementation maintains the current node weights in a priority queue. Each extraction and insertion takes logarithmic time in the number of active nodes, giving an overall construction time of (O(n\log n)) for an alphabet of (n) symbols. If the probabilities are already sorted, a two-queue formulation constructs the tree in linear time by separating unmerged leaves from newly created internal nodes.

Encoding replaces each source symbol with its stored codeword. Decoding performs one tree-edge transition per encoded bit, although table-based implementations can process several bits in a single lookup. The asymptotic encoded size is determined by the weighted leaf depths rather than by the particular branch labels used in the tree.