= Nonunique optimal prefix code
An <optimal prefix code> can be nonunique in several different senses. Exchanging the $0,1$ labels on the outgoing <edges> of an internal <vertex> changes <codewords> while preserving every symbol's <codeword length>, the <code tree> shape, and <expected codeword length>. This freedom exists even with strictly unequal <probabilities>. Exchanging equal-probability symbols between leaves also preserves <expected codeword length>; if their <leaf depths in a code tree> differ, their individual <codeword lengths> change, though the set of leaf depths does not. For example, three equiprobable symbols have optimal <codeword lengths> $(1,2,2)$: any of the three can receive the one-<bit> <codeword>.<A Method for the Construction of Minimum-Redundancy Codes by David A. Huffman>[p. 1099, Derived Coding Requirements: equal-probability messages may have unequal lengths and may exchange codes without changing the mean]{ref}
Ties between weights of entire <subtrees> during <Huffman coding> can go further and change the <code tree> shape and its collection of <codeword lengths>. Take $(p_A,p_B,p_C,p_D)=(0.4,0.2,0.2,0.2)$ and first merge $C,D$, creating weight $0.4$. Next, $B$ of weight $0.2$ can merge either with $A$ or with the $CD$ <subtree>, both of weight $0.4$. The two resulting <prefix codes> are
$$
\begin{array}{c|cccc|c}
&c(A)&c(B)&c(C)&c(D)&L(c)\\\hline
\text{balanced}&00&01&10&11&2\\
\text{unequal depths}&0&10&110&111&2
\end{array}
$$
For the second <prefix code>, $L=0.4\cdot1+0.2\cdot2+0.2\cdot3+0.2\cdot3=2$ <bits>. Both merge sequences add weights $0.4,0.6,1$, whose sum is $2$. Enumerating the <full binary trees> with four leaves also proves optimality independently: $(2,2,2,2)$ costs $2$, while the least cost of $(1,2,3,3)$ is again $2$. The two <code trees> cannot be obtained from each other merely by relabelling leaves or exchanging <edge> labels: their collections of <leaf depths in a code tree> differ.
\Image[/tied-huffman-weights-distinct-optimal-trees.png]
{title=A tie between a symbol and a merged subtree gives two optimal prefix trees, with depths 2,2,2,2 and 1,2,3,3}
{id=tied-huffman-weights-distinct-optimal-trees}
The quantifier in the <Huffman sibling property> is visible here too. Choose $B,C$ as two least-probability symbols. In the displayed balanced <optimal prefix code>, they are not <sibling leaves in a code tree>. Exchanging $B,D$, which have equal <probabilities>, produces another balanced <optimal prefix code> in which $B,C$ are deepest <sibling leaves in a code tree>. Thus the proof supplies an optimal representative with the chosen pair together. It does not force that labelling on every optimum. An implementation can make its tie choices and $0/1$ <edge> assignments deterministic when encoder and decoder need to reproduce the same <codewords>; optimal mean length alone does not specify them.
Back to article page
