Comparing Shannon-Fano and Shannon coding I am interested in a few algorithms for creating prefix codes:


Shannon coding: we take $l_i=\lceil -\log p_i\rceil$.
Shannon-Fano coding: list probabilities in decreasing order and then split them in half at each step to keep the probability on each side balanced. Then codes/lengths come from resulting binary tree.


My question is whether one of these algorithms always provides a better $L=\sum p_i l_i$? In a few examples I've done, Shannon-Fano seems better. Is this always true? Do you have any references or proofs? I realize these aren't the two best algorithms (Huffman coding is optimal). I'm just interested in comparing them.

Edit: Well, no interest so far? I guess this stuff isn't all that exciting, but I'd still like to know. Here's what I've come up with after some more google searching/playing around with numbers.

Practically, Shannon-Fano is often optimal for a small number of symbols with randomly generated probability distributions, or quite close to optimal for a larger number of symbols. I haven't found an example yet where Shannon-Fano is worse than Shannon coding.

In Shannon's original 1948 paper (p17) he gives a construction (equivalent to Shannon coding above) and claims that Fano's construction (Shannon-Fano above) is substantially equivalent, without any real proof. I haven't been able to find a copy of Fano's 1949 technical report to see whether it has any analysis.

Thomas and Cover's Elements of Information Theory says that Fano codes give $L \leq H +2$ and Shannon codes give $L \leq H+1$. However the reference they give for the Fano code analysis I think applies to alphabetical codes where you're not allowed to reorder the probabilities.

Stefan Moser's Information Theory Lecture Notes (pp 50-59) agree with my historical analysis above and purport to prove that for Fano codes we have $l_i \leq \lceil -\log p_i \rceil$ which would be sufficient to prove they are better than Shannon codes. However I don't follow the proof and I think I have a counterexample:

Take probabilities $(0.4, 0.26, 0.02, 0.02, 0.02, \ldots, 0.02)$ (we have 17 0.02's so that probabilities add to 1). Then Shannon coding has lengths $(2,2,6,6,6,\ldots,6)$ while Fano coding splits between 0.4 and 0.26 and then for the 0.6 probability on the right it splits between the second and third 0.02. Continuing on we see that 0.26 is encoded with a length of 3, larger than Shannon length. However, the average length is still less for Fano than for Shannon (according to my program implementing Fano coding).

So, am I doing something wrong? Can you see how to construct a probability distribution to make Shannon code perform better than Fano, or a way to prove it's not possible?
Unfortunately, I also don't have an exact answer. After an initially wrong statement in my lecture notes, currently I do not provide a good bound on the Fano code (version 3.1 of lecture notes). I do, however, have a proof that shows that the Fano codes has an expected average codeword length of less than H(U)/log(2) + 1 - 2p_{min}. Unfortunately, I only have the proof for the case of a binary code, not a general D-ary code. This is why I haven't included this yet into the lecture notes. But I'm still working on it and hope that I will eventually be able to fix it in my lecture notes.

Note, however, that my result does NOT compare Shannon codes with Fano codes. It only gives a general upper bound on the Fano codes. I think it is very difficult to compare the two codes directly. In particular, I do not understand the proof given above and I have my doubts that it can be made rigorous, particularly not for D>2.