Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 3I / a / Solution

In Shannon-Fano coding, a symbol of probability $p_i$ is assigned lengthand 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.