1
$\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.

  • 0
    this paper claims that not: http://anyserver.cityu.edu.hk/weijia/2003/DY_Long.pdf2013-05-26

1 Answers 1

1

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

  • 0
    Thank you. That's what I wanted.2012-11-27