4
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ I was under the impression that a Huffman code is by definition an optimal prefix code. What's your definition of a Huffman code? $\endgroup$
    – joriki
    Nov 27, 2012 at 11:48
  • $\begingroup$ Yes, I believe so. If by optimal you mean "maximizing per-byte information" then yes. $\endgroup$
    – yo'
    Nov 27, 2012 at 11:50
  • 2
    $\begingroup$ 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) $\endgroup$
    – Gricha
    Nov 27, 2012 at 11:58
  • $\begingroup$ this paper claims that not: anyserver.cityu.edu.hk/weijia/2003/DY_Long.pdf $\endgroup$
    – Ayrat
    May 26, 2013 at 12:06

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you. That's what I wanted. $\endgroup$
    – Gricha
    Nov 27, 2012 at 12:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .