Question

哈夫曼编码 频率相同的字符编码能互换吗

比如在一段文字中 s 和 i 都出现了4次， 我的程序编码完成后显示结果为 s 被编为了0 ，i被编为了11
但是另外一人所得到的结果是相反的，也就是s被编为11， i被编为了0
我们之间其他所有字符的编码都相同，因为没有其他两个字符出现频率是一样的。
所以我想请问，我和他的这两种编码结果是都为正确的还是只有其中一种是正确的？
非常感谢！！

Answer 1

哈夫曼编码完全依据字符出现概率来构造异字头的平均长度最短的码字，所以频率相同的编码可以互换，两种编码之后的字符串的平均期望长度是相同的。这里你和你同学做出的结果不同是因为哈夫曼树是二叉树，编码频率相同，但插入到二叉树的顺序不同，所以出现了不同的结果。