Optimal prefix code

An optimal prefix code minimizes probability-weighted codeword length among all prefix codes for the source.

For a source symbol $X$ and a code $c$, the expected codeword length is

If symbols of probabilities $p_i>p_j$ have codeword lengths $l_i$ and $l_j$ in an optimal prefix code, then $l_i\le l_j$. Otherwise, exchanging their codewords preserves the prefix property and changes the expected length bycontradicting optimality.

Every optimal binary prefix code has two codewords of maximal length that differ only in their final bit. Indeed, choose a deepest leaf in the prefix tree. If its sibling were not a codeword, maximality of the depth would make that sibling subtree empty, so the chosen word could be shortened by deleting its final bit. This would preserve prefix-freeness and reduce expected length.

Distinct tree shapes can have the same minimum expected length, particularly when Huffman merges have ties.