Question

When does shannon fano coding become terrible?

Answer 1

Answer:

You are confusing "Shannon coding" from "Shannon–Fano coding" (terminology could vary across sources). Per Wikipedia, Shannon–Fano coding is the algorithm you mention, while Shannon coding is any coding assigning a symbol occurring with probability $p_i$ a codeword of length $\ell_i = \lceil \log_2 \frac{1}{p_i} \rceil$. Per Wikipedia, Shannon–Fano coding always leads to codewords whose lengths are within one bit of $\log_2 \frac{1}{p_i}$. This is also a feature of Shannon coding, but the two need not be the same. In particular, Shannon–Fano coding always saturates the Kraft–McMillan inequality, while Shannon coding doesn't.