= Solution
In <Shannon-Fano coding>, a symbol of probability $p_i$ is assigned length
$$
\ell_i=\left\lceil-\log_2p_i\right\rceil,
$$
and codewords of those lengths are chosen in lexicographic probability intervals; the <Kraft inequality> guarantees that a binary <prefix code> exists. <Huffman coding> repeatedly merges the two least probable current symbols, builds a binary tree from the resulting merges, and labels its two branches by zero and one. Reading from the root to each leaf gives an optimal prefix code.
Back to article page
