= Huffman sibling contraction
{c}
{title2=$C^*(w)=C^*(w')+w_a+w_b$}
Replace <sibling leaves in a code tree> labelled $a,b$ by their common <parent in a rooted tree>, now a leaf labelled $m$ of weight $w_m=w_a+w_b$. All other <codewords> stay fixed; each of $a,b$ loses one <bit>. For any such <code tree> $T$ and the contracted <code tree> $T'$, their weighted costs satisfy
$$
C(T)=C(T')+w_a+w_b.
$$
If $a,b$ have two least weights, the <Huffman sibling property> gives an <optimal prefix code> containing this pair. Its contracted <prefix code> must be optimal for the reduced weights $w'$: any cheaper reduced <prefix code> could be expanded at $m$ by appending $0,1$, giving a cheaper original <prefix code>. Conversely, expanding any optimal reduced <prefix code> adds precisely $w_a+w_b$ and attains the original minimum. This is <optimal substructure>, the justification for repeating the merge in <Huffman coding>. <Symbol Codes by Ben Lynn>{ref}
In the exchange diagram, $C,D$ contract to weight $0.3$ at <leaf depth in a code tree> $2$. The reduced <expected codeword length> is $0.4\cdot1+0.3\cdot2+0.3\cdot2=1.6$ <bits>; expanding restores $1.6+0.3=1.9$ <bits>. For $n=2$, the reduction leaves one symbol: allow its temporary <codeword> to be empty, of cost zero, so expansion gives the two one-<bit> <codewords>. This convention is only the terminal reduced problem; the original source has at least two symbols.
Back to article page
