Huffman Coding Algorithm

Huffman coding is an algorithm for building an optimal prefix code, used for lossless data compression, that assigns shorter bit sequences to the more frequently occurring symbols in a message and longer sequences to rarer ones, so the average encoded length is minimized. The algorithm builds a binary tree from the bottom up: it repeatedly joins the two least frequent remaining symbols or partial trees under a new parent node, continuing until a single tree remains, then reads each symbol's code from the path taken from the root to its leaf. David A. Huffman devised the method in 1951 as a doctoral student at MIT, after being set a term paper on finding the most efficient binary code, and published it in 1952 in "A Method for the Construction of Minimum-Redundancy Codes," where his bottom-up tree construction outperformed the earlier top-down Shannon-Fano coding it was compared against. Huffman coding remains a standard building block inside later compression formats such as ZIP, JPEG and MP3 files, prized for its simplicity and speed even where more elaborate methods can compress slightly further.