Huffman coding

Huffman coding is an algorithm for lossless data compression that assigns variable-length codewords to symbols according to their frequencies or probabilities. In its binary form, frequent symbols receive shorter sequences of bits, while less frequent symbols receive longer sequences. It constructs a prefix code with the smallest average codeword length for a specified symbol distribution. David A. Huffman introduced the method in his September 1952 paper, “A Method for the Construction of Minimum-Redundancy Codes.” (compression.ru)

Coding model

The input is a finite alphabet of symbols with a known or estimated probability distribution. Symbols may represent characters, bytes, or larger units. If symbol $i$ has probability $p_i$ and codeword length $\ell_i$, the quantity minimized is the expected value of the length:

Using occurrence counts instead of probabilities gives an equivalent optimization problem, because normalizing all counts by the same total does not change the minimizing code. (ocw.mit.edu)

The prefix condition means that no complete codeword is the beginning of another. Consequently, a decoder can recognize each symbol immediately upon reaching the end of its codeword, without separators. A binary tree represents this structure: symbols occupy leaves, branches carry 0 or 1, and each root-to-leaf path spells a codeword. Its length equals the leaf’s depth. (ocw.mit.edu)

Construction and decoding

Huffman’s method is a greedy algorithm. Initially, every symbol forms a separate node weighted by its probability or frequency. The construction repeatedly:

1. Selects the two nodes with the smallest weights.
2. Makes them children of a new parent.
3. Assigns the parent the sum of their weights.
4. Returns the parent to the collection of available nodes.

For $n$ symbols, $n-1$ merges produce a single tree. Assigning 0 and 1 to its branches then determines the codewords. Equal weights permit alternative choices, so the optimal code need not be unique. (ocw.mit.edu)

A priority queue, commonly implemented with a binary heap, supports selecting and reinserting nodes. The construction has time complexity $O(n\log n)$, expressed in big-O notation. When weights are already sorted, construction can take $O(n)$ time. These bounds concern building the code, rather than processing the entire message. (ocw.mit.edu)

To decode, start at the root and follow the branch indicated by each incoming bit. Reaching a leaf produces its symbol and resets traversal to the root for the next symbol. (datatracker.ietf.org)

Example

Consider four symbols with probabilities $A=0.5$, $B=0.25$, $C=0.125$, and $D=0.125$. Applying the construction first combines $C$ and $D$, giving weight $0.25$. Combining this node with $B$ produces weight $0.5$, which is finally combined with $A$. One resulting assignment is: (ocw.mit.edu)

For this illustrative distribution, the average length is

bits per symbol, compared with two bits for a fixed-length representation. The message “ABCD” becomes 010110111. This comparison excludes any information required to communicate the codebook.

Optimality and entropy

The proof of optimality uses an exchange argument: there exists an optimal tree in which the two least probable symbols are sibling leaves at maximum depth. Replacing those leaves with their combined parent reduces the problem to an alphabet with one fewer symbol. Solving that reduced problem optimally and restoring the leaves yields an optimal solution to the original problem. Repetition establishes the correctness of the greedy construction. (math.mit.edu)

Within information theory, Shannon entropy measures the distribution’s average information:

For a finite alphabet with at least two positive-probability symbols, binary Huffman coding satisfies

Thus, its average length is less than one bit above entropy. When every probability is an exact negative power of two, codeword lengths can equal each symbol’s self-information, achieving $L=H(X)$. (ocw.mit.edu)

This relationship connects Huffman coding with the source coding theorem. Coding blocks of $k$ independent, identically distributed symbols reduces the excess length per original symbol to less than $1/k$. However, the block alphabet grows exponentially with $k$. (ocw.mit.edu)

Practical forms and limitations

A canonical Huffman code preserves codeword lengths but assigns bit patterns according to a standardized ordering. Given the symbol order and lengths, the decoder can reconstruct the code without receiving an explicit tree. This changes the representation, not its average encoded length. Formats may also impose maximum codeword lengths, requiring a constrained construction rather than the unrestricted algorithm. (datatracker.ietf.org)

Huffman optimality applies to the specified distribution and symbol-by-symbol prefix-coding model; it does not imply the smallest possible compressed file. Coding individual symbols does not directly exploit dependencies between successive symbols. Arithmetic coding instead encodes sequences and can avoid assigning an integral number of bits separately to every symbol. (ocw.mit.edu)

The DEFLATE format illustrates Huffman coding within a broader data compression system. It combines LZ77 matching with Huffman codes for literal values, match lengths, and backward distances. DEFLATE supports both predefined code tables and dynamically transmitted tables, and uses canonical ordering to reconstruct codes from their lengths. (datatracker.ietf.org)

References

1. A Method for the Construction of Minimum-Redundancy Codescompression.ru
2. 046J Complete Lecture Notesocw.mit.edu
3. 441S16: Course Notesocw.mit.edu
4. MITOCW: 18.200 Lecture 17 Transcriptocw.mit.edu
5. Finding Efficient Compressions; Huffman and Hu-Tucker Algorithmsmath.mit.edu
6. RFC 1951: DEFLATE Compressed Data Format Specification version 1.3datatracker.ietf.org