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?