9
$\begingroup$

I am interested in a few algorithms for creating prefix codes:

  1. Shannon coding: we take $l_i=\lceil -\log p_i\rceil$.
  2. 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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Very nice counterexample. I think it's an interesting question. I agree that Cover and Thomas are probably talking about the case where you don't reorder the probabilities. I expect the theorem is true, and that nobody here knows any references to anybody looking at anything similar, and this is why you haven't gotten any answers. $\endgroup$
    – Peter Shor
    Sep 23, 2011 at 12:37
  • $\begingroup$ Thanks for the comment Peter. Glad to know somebody's reading. I'll post something if I ever figure out the answer. $\endgroup$
    – Martin Leslie
    Sep 23, 2011 at 14:15

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

Nice counterexample.

A short "proof" that Shannon-Fano coding is always at least as good as Shannon coding over the long term, even though it may be worse for a few specific letters:

  1. Shannon coding always sets the length $ls_i$ of each codeword to a function of how many times $f_i$ it occurs in some text of length $LN$: $ls_i=\lceil -\log (f_i/LN)\rceil$.
  2. two-symbol Shannon-Fano coding and Huffman coding: always sets the codeword for one symbol to 0, and the other codeword to 1, which is optimal -- therefore it is always better than Shannon coding in this case (or equal, in the case where both probabilities are 1/2).
  3. multi-symbol Shannon-Fano coding and Huffman coding: case (a): sometimes there exists some letter $i$ assigned Fano codeword with a length $lf_i$ 1 bit longer (worse compression) than $ls_i$.
  4. multi-symbol Shannon-Fano coding and Huffman coding: case (b): sometimes there exists some letter $j$ assigned Fano codeword with a length $lf_j$ shorter (better compression) than $ls_j$.
  5. Whenever case (a) occurs, case (b) also occurs at least as many times.
  6. Each letter (if any) $i$ that falls under case (a) can be paired up with some other letter $j$ that not only falls under case (b), but also letter $j$ is more frequent than letter $i$.
  7. Therefore, whenever case (b) occurs, the total number of bits needed to store all the letters $i$ and all the letters $j$ with with Shannon-Fano coding is no worse than with Shannon coding: $f_i lf_i + f_j lf_j \leq f_i ls_i + f_j ls_j$.
  8. Therefore Shannon-Fano coding is always at least as good as Shannon coding.

Alas, there's a lot of hand-waving in this "proof".

I suspect there might be a better proof in the book Yaglom and Yaglom: "Probability and information".

p.s.: You might also be interested in yet another algorithm for generating prefix codes, "Polar coding" developed by Andrew Polar.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for attempting an answer David. Unfortunately I don't really understand what you are saying here :( In points 3 and 4 are you saying that your claims apply to both Shannon-Fano and Huffman coding? Or are you somehow proving something about Shannon-Fano compared to Huffman? I just don't really see reasons for any of points 3-6. $\endgroup$
    – Martin Leslie
    Sep 28, 2011 at 6:28
  • $\begingroup$ I had a look at the Yaglom and Yaglom book and I don't think it had anything to add on this topic: like most books it talks about Shannon-Fano coding but all its proofs are using Shannon coding. $\endgroup$
    – Martin Leslie
    Sep 28, 2011 at 6:29
  • $\begingroup$ Thanks for the polar codes reference. Do you know whether this has anything to do with polar codes as used in channel coding? As far as I know those polar codes are so named because of channel polarisation, not after someone called Polar. The Korada and Urbanke paper linked from the link you gave seems to be about those kind of polar codes, applied to lossy compression. $\endgroup$
    – Martin Leslie
    Sep 28, 2011 at 6:33
  • $\begingroup$ Yes, I'm saying 3 and 4 are true for Shannon Fano coding. (I'm also going on a tangent and mentioning that it is also true for Huffman coding as well, although that is irrelevant to the proof). $\endgroup$
    – David Cary
    Sep 29, 2011 at 1:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.