# Information theory - is every optimal prefix code a Huffman code?

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.

-
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: anyserver.cityu.edu.hk/weijia/2003/DY_Long.pdf – Ayrat May 26 '13 at 12:06

## 1 Answer

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.}$$

-
Thank you. That's what I wanted. – Gricha Nov 27 '12 at 12:14