I noticed this in my Algorithms class, but just now got around to asking.
$\begingroup$
$\endgroup$
10
-
1$\begingroup$ The question is not well-defined. What do you mean by “worst”? $\endgroup$– Tsuyoshi ItoFeb 15, 2011 at 14:43
-
2$\begingroup$ @Ito: The obvious definition of "worst" is the difference between the average codeword length of the Huffman code and the Shannon entropy of the probability distribution. I don't know if this is what the OP had in mind. See my next comment. $\endgroup$– Peter ShorFeb 15, 2011 at 14:56
-
2$\begingroup$ Change the probability distribution in my previous comment to start with $\phi^2$, so the sum is 1. This certainly produces a maximum depth Huffman encoding. I don't know whether that qualifies as worst. Certainly it isn't the worst, using the definition in my previous comment, if you are allowed probabilities close to 1. But maybe it's worst-case if you are restricted to distributions with probabilities $< \frac{1}{2}$. $\endgroup$– Peter ShorFeb 15, 2011 at 14:57
-
3$\begingroup$ (1) @Peter: That definition of “worst” sounds reasonable (under the restriction on the maximum probability of a symbol, as you wrote), and I think that that question is interesting. (2) I had voted the question down because of the underspecification. When the asker edits the question to clarify what “worst” in the question means, I will reconsider the vote. $\endgroup$– Tsuyoshi ItoFeb 15, 2011 at 18:44
-
1$\begingroup$ If we don't get an answer from the OP in a few days, I'll revive the question by asking it myself. $\endgroup$– Peter ShorFeb 16, 2011 at 11:10
|
Show 5 more comments
2 Answers
$\begingroup$
$\endgroup$
1
This paper may shed some light on the issues: http://www.springerlink.com/content/w32x70520k8jj617/
answered Feb 17, 2011 at 4:12
-
5
$\begingroup$
$\endgroup$
The Huffman algorithm considers the two least frequent elements recursively as the sibling leaves of maximum depth in code tree. The Fibonacci sequence (as frequencies list) is defined to satisfy F(n) + F(n+1) = F(n+2). As a consequence, the resulting tree will be the most unbalanced one, being a full binary tree.
