= Optimal prefix code
{title2=$\min_c L(c)$}
An optimal prefix code minimizes <expected codeword length> for a fixed source <probability distribution>. Here the source <alphabet> is finite, has $n\geq2$ symbols, and has $p_x>0$ for every symbol; each source symbol receives one <codeword> over the binary output <alphabet> $\{0,1\}$. Its <code tree> puts the symbols at leaves. Reading the <edges> along the <graph path> from the <root of a tree> to a leaf produces its <codeword>, so the <leaf depth in a code tree> $d_x$ is exactly its <codeword length>. Thus
$$
L(c)=\sum_xp_xd_x,\qquad
L^*(p)=\min_{c\text{ a binary prefix code}}L(c).
$$
For unnormalized positive weights, minimize $C(T)=\sum_xw_xd_x$ instead; the corresponding <expected codeword length> is $C(T)/\sum_xw_x$. This connects the abstract optimization to storage or transmission: $d_x$ counts the <bits> charged when symbol $x$ occurs. <Huffman coding> attains this minimum; the <Huffman sibling property> and <Huffman sibling contraction> explain why. <Symbol Codes by Ben Lynn>{ref}
For $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$, a balanced <code tree> charges every symbol two <bits>, giving $L=2$. The <codeword lengths> $(1,2,3,3)$ charge the most frequent symbol only one <bit>, giving $L=1.9$. The choice concerns weighted cost, not just the greatest <codeword length>: increasing that maximum from two to three can improve the average.
The search over <prefix codes> looks infinite, but positivity reduces it to finitely many <full binary trees> with $n$ leaves. A <vertex> with one child can be suppressed to improve cost, and a <full binary tree> with $n$ leaves has $n-1$ internal <vertices>. There are consequently finitely many such shapes and symbol assignments, so the minimum exists. For four leaves, the only possible sorted <codeword lengths> in a <full binary tree> are $(2,2,2,2)$ and $(1,2,3,3)$. <Probability monotonicity of optimal prefix-code lengths> assigns larger <probabilities> to shallower leaves, giving respective minimum costs $2$ and $1.9$ in this example. This is an independent small-instance check of the <Huffman code>.
These hypotheses matter. With zero weights, suppressing a <subtree> carrying only zero weight need not strictly improve cost, so an <optimal prefix code> need not have a <full binary tree>. A one-symbol source raises the convention of whether an empty <codeword> is allowed. Both cases are outside the original statement here. Encoding groups of symbols changes the source <alphabet> and the optimization problem; the minimum here concerns one source symbol per <codeword>.
Back to article page
