Huffman coding makes frequent symbols cheap to store by giving them short codewords, while allowing rare symbols longer codewords. For a known probability distribution on a finite alphabet with at least two positive-probability symbols, binary Huffman coding constructs a prefix code minimizing expected codeword length among binary prefix codes that encode one source symbol at a time. The objective is an average under that probability distribution; it does not promise to shorten every message. Encoder and decoder must agree on the resulting Huffman code. [ref]
The construction grows a binary tree from its leaves towards its root of a tree. Start with one leaf per symbol, weighted by its probability. Repeatedly join the two currently smallest weights beneath a new parent in a rooted tree, whose weight is their sum, and replace the pair by that subtree. Include newly formed subtrees when choosing the next pair. When one tree remains, label the two outgoing edges at every internal vertex with and ; the labels on the graph path from the root of a tree to a symbol give its codeword. This is a greedy algorithm: each step makes a locally cheapest merge, yet the result is an optimal prefix code.
For a concrete example, use probabilities , , , . First join and , creating weight . The remaining weights are for , for the subtree, and for . Join the two weights to make , then join with that subtree to make . The merge weights are therefore . Each merge adds one bit to every codeword below it, so their sum is the expected codeword length: bits per source symbol. The diagram fixes the edge labels to produce the Huffman code used below.
The useful insight is that choosing short codewords is a resource allocation problem: the prefix code condition constrains the available codeword lengths through the Kraft inequality. Huffman coding solves this one-symbol problem exactly for the supplied probability distribution. For repeated emissions of a memoryless classical information source, the same Huffman code can be applied symbol by symbol. More general compression can exploit dependencies or encode groups of symbols; the one-symbol optimality statement does not compare all such methods.
Huffman coding is a widely used method for data compression that assigns variable-length codes to input characters, with shorter codes assigned to more frequently occurring characters. The technique was developed by David A. Huffman in 1952 and forms the basis of efficient lossless data encoding. ### How Huffman Coding Works 1. **Frequency Analysis**: First, the algorithm counts the frequency of each character in the given input data.
New to topics? Read the docs here!