4
$\begingroup$

I noticed this in my Algorithms class, but just now got around to asking.

$\endgroup$
10
  • 1
    $\begingroup$ The question is not well-defined. What do you mean by “worst”? $\endgroup$ Feb 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$ Feb 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$ Feb 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$ Feb 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$ Feb 16, 2011 at 11:10

2 Answers 2

7
$\begingroup$

This paper may shed some light on the issues: http://www.springerlink.com/content/w32x70520k8jj617/

$\endgroup$
1
  • 5
    $\begingroup$ Its behind a paywall. :( $\endgroup$
    – user3845
    Feb 18, 2011 at 18:33
3
$\begingroup$

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.

$\endgroup$

Your Answer

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

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