= Solution
<Shannon-Fano coding> orders symbols by decreasing <probability> and recursively splits each consecutive block into two groups with <probability> totals as close as possible, appending bits zero and one. <Huffman coding> instead repeatedly merges the two least probable nodes, constructs a binary tree upwards, and then assigns the branch bits. Both yield <prefix codes>, so a concatenation can be decoded without separators; <Huffman coding> minimizes expected length among binary <prefix codes>.
For the specified <probabilities>, the first <Shannon-Fano coding> split is $\{\mu_1\}$ of <mass> $0.45$ versus the remaining <mass> $0.55$. Split the latter into $\{\mu_2\}$ of <mass> $0.25$ and $\{\mu_3,\mu_4,\mu_5\}$ of <mass> $0.30$, and then split off $\mu_3$. One resulting code is
$$
\boxed{\mu_1:0,\quad\mu_2:10,\quad\mu_3:110,\quad\mu_4:1110,\quad\mu_5:1111.}
$$
Its expected word length is $0.45+2(0.25)+3(0.20)+4(0.05+0.05)=\boxed{1.95\text{ bits}}$.
The <Huffman coding> merges are $0.05+0.05=0.10$, $0.10+0.20=0.30$, $0.25+0.30=0.55$, and $0.45+0.55=1$. Reading the resulting tree gives the same code lengths $1,2,3,4,4$, and it may give exactly the displayed code if the branch bits are chosen accordingly. Its expected length is also \b[$1.95$ bits]. The methods agree here; their agreement on this particular distribution is not a claim that the two procedures always coincide.
Back to article page
