Mathematics
The Huffman Coding Algorithm for Data Compression
Quick fact
Huffman coding produces the most efficient prefix code possible for a given set of symbol frequencies, and it is the algorithm behind many compression tools like ZIP and GZIP. It was invented by David A. Huffman in 1952 while he was a graduate student at MIT.
Why this is interesting
Why is it that the letter 'e' appears as a short beep in Morse code, but 'z' as a long one? Could there be a mathematically perfect way to minimize the average length of such codes?
Read the full explanation
Understanding The Huffman Coding Algorithm for Data Compression
Think of a file as a string of symbols, each with a frequency. To compress it, we want to encode frequent symbols with short codes and rare ones with longer codes. For example, in 'aabac', 'a' appears 3 times, 'b' once, 'c' once. A fixed-length code (like 2 bits per symbol) would use 10 bits total. But with variable-length coding, we could assign 'a' a 1-bit code '0', and 'b' and 'c' longer codes '10' and '11', respectively. The compressed string becomes '001011', using only 6 bits. But we must ensure the code is 'prefix-free': no code is a prefix of another, so we can decode uniquely. Huffman coding builds such a prefix-free code by repeatedly merging the two least frequent symbols into a new 'combined' symbol whose frequency is the sum. Each merge creates an internal node of a binary tree, and the leaves are the original symbols. The path from the root to a leaf gives the binary code: left move = '0', right move = '1'. This process continues until a single root remains. The result is a tree that minimizes the weighted path length, i.e., the average code length.
A deeper explanation
The Huffman algorithm is a greedy algorithm because at each step it makes a locally optimal choice—combining the two smallest frequencies—and this myopic choice leads to a globally optimal solution. The optimality property can be proved by exchange arguments: for any optimal prefix code, we can assume that the two least frequent symbols are the deepest leaves and siblings. By building the tree from the bottom up, we ensure that the most frequent symbols end up with the shortest codes. The tree is a full binary tree with each internal node having exactly two children. The cost of the code is the sum over all symbols of frequency times code length, which equals the total number of bits used. Huffman coding achieves the optimal cost among all prefix codes for a given frequency distribution. This connects directly to information theory: the optimal average code length is between the entropy of the source and the entropy plus one bit. Huffman coding is used in many compression formats, such as DEFLATE in ZIP and GZIP, and in image formats like JPEG, where it encodes quantized coefficients. Although Huffman coding is optimal for symbol-by-symbol coding, it can be outperformed by arithmetic coding when the source has high order dependencies because arithmetic coding can encode entire messages with fractional bits per symbol. However, Huffman coding remains fundamentally important due to its simplicity, speed, and provable optimality for the given model.