HuffmanCodes

HuffmanCodes, commonly known as Huffman coding, is a widely used lossless data compression scheme developed by David A. Huffman in 1952. It assigns variable-length binary codes to symbols based on their frequencies in a source, producing shorter codes for more frequent symbols.

Construction: Given a set of symbols with probabilities, create a leaf node for each symbol. Repeatedly select the two nodes with smallest weights, merge them into a new node whose weight is the sum, and insert it back. When one node remains, the resulting binary tree is the Huffman tree. The code for a symbol is the sequence of edge labels along the path from the root to its leaf; the prefix-free property ensures decodability.

Optimality and limitations: For a fixed source distribution, Huffman coding produces an optimal prefix code that minimizes expected code length among all prefix codes. It is not universally optimal for unknown or changing distributions, and its efficiency depends on the accuracy of the symbol probabilities. If several symbols share the same frequency, multiple optimal trees may exist. Dynamic or adaptive Huffman coding variants handle streaming data without a fixed distribution.

Complexity and usage: Building the tree for n symbols takes O(n log n). Encoding and decoding use the Huffman tree; decoding is linear in the length of the encoded data and typically requires a lookup or traversal. Huffman coding is a component of many compression formats, such as DEFLATE used in gzip and PNG, and is often paired with other techniques like LZ77.