= Huffman code
{c}
A Huffman code is the <prefix code> returned by <Huffman coding>; the <algorithm> chooses a <code tree>, while the code specifies the actual symbol-to-<codeword> assignment. For the <probability distribution> $(0.4,0.3,0.2,0.1)$ in symbol order $A,B,C,D$, the illustrated <binary tree> gives
$$
c(A)=0,\qquad c(B)=10,\qquad c(C)=110,\qquad c(D)=111.
$$
The <codeword lengths> are $1,2,3,3$. This is a <prefix code> because no complete <codeword> is an initial segment of another complete <codeword>. Thus a decoder can start at the <root of a tree>, follow one <edge> per <bit>, emit a symbol on reaching its leaf, then restart at the <root of a tree>. In particular, `011010111` splits as `0 | 110 | 10 | 111` and decodes to $A,C,B,D$. No separators are transmitted: the leaf tells the decoder where a <codeword> ends.
The <expected codeword length> is
$$
L(c)=\sum_xp_x\,|c(x)|=0.4\cdot1+0.3\cdot2+0.2\cdot3+0.1\cdot3=1.9
$$
<bits> per source symbol. Four symbols would require $2$ <bits> each if all <codewords> had the same length, so this <Huffman code> saves $0.1$ <bit> per symbol on average, or $5\%$ of that fixed-length payload. A particular message can grow: $A,C,B,D$ uses nine <bits> here instead of eight. These lengths count the encoded symbols only; transmitting a code description or message framing can add further cost.
The <Kraft inequality> is saturated by this <Huffman code>:
$$
2^{-1}+2^{-2}+2^{-3}+2^{-3}=1.
$$
Its <Shannon entropy> is
$$
H(X)=-\sum_xp_x\log_2p_x\approx1.846439
$$
<bits> per symbol, slightly below the <expected codeword length> $1.9$. The <entropy lower bound for prefix codes> applies to every binary <prefix code> for this <probability distribution>. It need not be attainable with integer <codeword lengths> for individual symbols; <Huffman coding> reaches the best mean within that class. https://web.iitd.ac.in/~sumeet/mackay.pdf[David J. C. MacKay, Information Theory, Inference, and Learning Algorithms, chapter 5, section 5.4: symbol-code bounds]{ref}
\Image[/huffman-code-length-and-entropy.png]
{title=Probability-weighted codeword lengths sum to 1.9 bits per symbol, between entropy and fixed length}
A <Huffman code> need not be unique. In the first example, the tied $B$ and $CD$ weights can exchange their $0/1$ <edge> labels, changing <codewords> but preserving their <codeword lengths>. Ties can also change the lengths themselves. For a second <probability distribution> $(0.4,0.2,0.2,0.2)$, first merge $C,D$ to weight $0.4$. The next merge can join $B$ with either $A$ or the $CD$ <subtree>, since both have weight $0.4$. Joining $B$ with $A$ permits $A\mapsto00,B\mapsto01,C\mapsto10,D\mapsto11$, with all lengths $2$. Joining $B$ with the $CD$ <subtree> permits $A\mapsto0,B\mapsto10,C\mapsto110,D\mapsto111$, with lengths $1,2,3,3$. Both are <optimal prefix codes> with <expected codeword length> $2$: for the latter, $0.4\cdot1+0.2\cdot2+0.2\cdot3+0.2\cdot3=2$. Tie choices can change the <code tree> without changing the minimum mean.
// Target: algebra.bigb
Back to article page
