Huffman coding

Huffman's algorithm repeatedly combines the $D$ least weights for a $D$-ary prefix code and yields an optimal expected length.

Some optimal prefix tree places the two least probable symbols as sibling leaves of maximum depth, which is the inductive basis of Huffman's algorithm.

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.

For a largest binary-symbol probability $p_1$, $p_1<1/3$ prevents a length-one word, while $p_1>2/5$ forces one in a Huffman tree.