Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm not sure about it but it seems true for me. I know that for every optimal code there exists a prefix code that is optimal, but I'm not sure if it's Huffman code.

Thanks in advance.

share|improve this question
1  
I was under the impression that a Huffman code is by definition an optimal prefix code. What's your definition of a Huffman code? –  joriki Nov 27 '12 at 11:48
    
Yes, I believe so. If by optimal you mean "maximizing per-byte information" then yes. –  tohecz Nov 27 '12 at 11:50
2  
Yes, Huffman Code indeed is an optimal prefix code, but I'm not sure if there exists optimal prefix codes that are not Huffman Codes. For me a Huffman Code is any code that we can retrieve from a tree in Huffman Algorithm (or any automorphic tree) –  Gricha Nov 27 '12 at 11:58
    
this paper claims that not: anyserver.cityu.edu.hk/weijia/2003/DY_Long.pdf –  Ayrat May 26 '13 at 12:06
add comment

1 Answer 1

up vote 1 down vote accepted

It is proved somewhere that every optimal prefix code can be retrieved by Huffman Algorithm. There can be more of them because sometimes the nodes of computation have the same probability and you can re-order them.

Consider e.g. the probabilities $p(a)=p(b)=p(c)=1/3$. Then all the following codes are Huffman codes:

$$ a\to 0, b\to10, c\to 11$$ $$ a\to 00, b\to 01, c\to 1$$ $$ a\to 10, b\to 0, c\to 11$$ $$ \text{etc.} $$

share|improve this answer
    
Thank you. That's what I wanted. –  Gricha Nov 27 '12 at 12:14
add comment

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.