Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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. – yo' Nov 27 '12 at 11:50
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: – Ayrat May 26 '13 at 12:06
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|cite|improve this answer
Thank you. That's what I wanted. – Gricha Nov 27 '12 at 12:14

Your Answer


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.