= Huffman coding
{c}
{wiki}
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>. <Symbol Codes by Ben Lynn>{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 $0$ and $1$; 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> $p_A=0.4$, $p_B=0.3$, $p_C=0.2$, $p_D=0.1$. First join $D$ and $C$, creating weight $0.3$. The remaining weights are $0.3$ for $B$, $0.3$ for the $CD$ <subtree>, and $0.4$ for $A$. Join the two $0.3$ weights to make $0.6$, then join $A$ with that $0.6$ <subtree> to make $1$. The merge weights are therefore $0.3,0.6,1$. Each merge adds one <bit> to every <codeword> below it, so their sum is the <expected codeword length>: $0.3+0.6+1=1.9$ <bits> per source symbol. The diagram fixes the <edge> labels to produce the <Huffman code> used below.
\Image[/huffman-merge-tree-example.png]
{title=Huffman merges for probabilities 0.4, 0.3, 0.2, 0.1 and their binary codewords}
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.
Back to article page
