= Solution
The binary <Huffman coding> algorithm repeatedly merges the two currently least probable symbols into one meta-symbol whose probability is their sum. After recursively constructing a code for the smaller alphabet, append $0$ and $1$ to the meta-symbol's codeword to obtain codewords for the merged pair. The result is a binary <prefix code>.
To prove optimality, begin with an optimal prefix-code tree. It may be taken to be full, since an internal vertex with one child can be suppressed and all codewords below it shortened. Two leaves of maximum depth are siblings. By exchanging labels, without changing lengths, assign two least probable symbols to such a sibling pair: moving a smaller probability to a no-shorter codeword cannot increase the expected length. Contracting this pair to one leaf replaces their contribution $p_i\ell_i+p_j\ell_j$ by $(p_i+p_j)(\ell_i-1)$ plus the constant $p_i+p_j$. If the contracted code were not optimal for the reduced alphabet, replacing it by a better one and then expanding the merged leaf would improve the original code. <Mathematical induction> on the number of symbols now proves that the Huffman construction minimizes expected word length.
Back to article page
