HuffmanCode

HuffmanCode, more commonly known as Huffman coding, is a lossless data compression method that assigns variable-length binary codes to input symbols based on their frequencies. In a Huffman code, more frequent symbols receive shorter codes and less frequent symbols receive longer codes. The code is prefix-free, meaning no codeword is a prefix of another, which ensures unique and unambiguous decoding.

Construction of a Huffman code starts with the symbol frequency distribution. A binary tree is built by repeatedly merging the two least-frequent nodes into a new node whose frequency is the sum of the two. The resulting tree yields a code: following left edges may denote 0 and right edges denote 1, and the codeword for a symbol is the sequence of edge labels from the root to that symbol. The process produces a compact, decodable set of codes tailored to the source distribution.

Optimality and limitations: Huffman coding minimizes the expected codeword length among all prefix-free codes for a given discrete source distribution with known probabilities, assuming integer-length codewords. It is not universal optimal if the source distribution changes; adaptive Huffman methods address changing statistics by updating the tree as data is encoded or decoded.

Variants and usage: Canonical Huffman codes standardize codeword representations to reduce storage overhead. Adaptive Huffman coding and related schemes allow real-time updates. In practice, Huffman coding is widely used as a component of larger compression systems, such as the DEFLATE algorithm in gzip and PNG, where it is combined with other techniques like LZ77 to achieve overall compression.

History: The method was introduced by David A. Huffman in 1952, as part of his doctoral work at MIT, providing a practical approach to near-optimal prefix codes without exhaustive search.