Huffman Coding

Huffman coding constructs a binary prefix code that minimizes weighted codeword length for a known set of symbol frequencies:

$$\min \sum_s f_s\,\ell_s,$$

where $f_s$ is a symbol frequency and $\ell_s$ its code length.

Construction

1. Put one leaf per positive-frequency symbol into a min-priority queue.
2. Remove the two least frequent nodes.
3. Join them under a parent whose weight is their sum.
4. Reinsert the parent and repeat until one tree remains.
5. Label left/right edges with bits; each root-to-leaf path is a codeword.

Leaves cannot prefix one another, so concatenated codewords decode unambiguously given the tree or an equivalent canonical-code description.

Why the greedy merge is safe

In some optimal full binary prefix tree, two least frequent symbols can be made deepest siblings by exchanging leaf labels without increasing weighted length. Contracting those siblings produces the same problem on one combined frequency, which justifies the recursive greedy step.

Cost and boundary

For $k$ symbols, heap construction and merging take $O(k\log k)$ time and $O(k)$ space. Ties can produce different but equally optimal code lengths.

The encoded stream must also represent the codebook, padding, and original length as needed. Huffman coding is optimal for the stated prefix-code model, not universally optimal compression; block structure and richer probabilistic models can exploit dependencies it ignores.

Source

• Princeton Algorithms: Data Compression