Huffman

Huffman coding is a lossless data compression algorithm named after American computer scientist David A. Huffman, who introduced it in 1952. It assigns variable-length codes to symbols based on their frequencies of occurrence, with more frequent symbols given shorter codes. The set of codes forms a prefix code, meaning no code is a prefix of any other, enabling unambiguous decoding.

The method works by building a binary tree: each leaf represents a symbol, and the path to a leaf yields its code. Start with a forest of leaves keyed by symbol probability, repeatedly merge the two least-probable nodes into a new internal node whose probability is the sum of the two, until only one tree remains. The code for a symbol is the sequence of left/right choices from the root to its leaf.

Huffman coding is optimal among all prefix codes for a given set of symbol probabilities, minimizing the expected code length. In practice, probabilities may be estimated or adaptively updated. Canonical Huffman codes store only code lengths and a predefined symbol order to simplify decoding. Adaptive Huffman coding updates frequencies as data are encoded or decoded.

Applications are widespread in lossless compression, notably as the entropy coding step in the Deflate algorithm used in ZIP and gzip, and in JPEG for compressing the quantized coefficients. Huffman coding is often combined with other compression techniques such as Lempel-Ziv.

Limitations include the need to know or estimate symbol probabilities; when statistics change, the code may become suboptimal. Large alphabets can also lead to inefficiencies or large header overhead to transmit the tree or code lengths.