Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
The question is not well-defined. What do you mean by “worst”? –  Tsuyoshi Ito Feb 15 '11 at 14:43
2  
@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. –  Peter Shor Feb 15 '11 at 14:56
2  
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}$. –  Peter Shor Feb 15 '11 at 14:57
3  
(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. –  Tsuyoshi Ito Feb 15 '11 at 18:44
1  
If we don't get an answer from the OP in a few days, I'll revive the question by asking it myself. –  Peter Shor Feb 16 '11 at 11:10

2 Answers 2

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

share|improve this answer
3  
Its behind a paywall. :( –  user3845 Feb 18 '11 at 18:33

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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