algorithm - 非二进制字母的霍夫曼编码

Question

我正在研究在非二进制字母表上构建最优霍夫曼码。

这个问题是在 Huffman trees for non-binary alphabets? 中提出的.该解决方案建议使用一次组合 n 个最低频率符号的霍夫曼编码程序(维基百科也建议这样做)。然而，这似乎不是最优的。假设我有 4 个带频率的字母表，

 A --> 0.4

 B --> 0.25

 C --> 0.2

 D --> 0.15

此处使用此导出的三元霍夫曼代码将是

A --> 0

B --> 10

C --> 11

D --> 12

然而，以下代码的预期长度会更短:

A --> 0

B --> 1

C --> 20

D --> 21

我是不是漏掉了什么？

PS 我将此作为问题发布，因为我无法对之前的帖子发表评论。

Answer 1

维基百科文章指出“请注意，对于大于 2 的 n，并非所有源词集都可以正确地形成霍夫曼编码的 n 叉树。在这种情况下，必须添加额外的 0 概率占位符。 “我认为对于 3 元树来说，3 片叶子之后的下一个完整树有 5 片叶子，所以我认为你应该在运行 3 元霍夫曼代码算法之前添加一个 0 概率字符，这会给你 {0, C, D}作为第一阶段，它会生成您喜欢的编码。