哈夫曼编码规则与优化

Question

我读过的所有来源都引用了以下过程来获取霍夫曼代码：

• 按频率升序排列元素。
• 通过重复地将两个最不频繁的元素组合成一个节点来创建二叉树，它们的频率之和作为新节点的频率。
• 在每一步将“0”分配给左分支，将“1”分配给右分支。
• 每个元素的哈夫曼编码是通过从树的根遍历到各自的叶节点，记录所走的路径（0为左，1为右）来获得的。

让我们尝试以下频率图：

A -> 1 B -> 2 C -> 3 D -> 4

制作树

        (ABCD, 10)
       /          \
   (ABC, 6)         D:4
   /     \
 (AB, 3)  C:3
 /    \
A:1   B:2

按照这棵树获取代码：

A -> 000 B -> 001 C -> 01 D -> 1

显然，最大深度和最大代码长度不遵循 log2(nElement) 的逻辑规则，在本例中应该是 2。

最佳代码是：

A -> 00 B -> 01 C -> 10 D -> 11

那么这是怎么回事？我做错了什么？

Answer 1

想象编码字符串“ABBCCCDDDD” - 每个符号以给定频率出现的示例字符串。

您提出的霍夫曼编码将其编码为

0000010010101011111

- 19 个字符。

针对最大代码长度进行优化的编码给出

00010110101011111111

- 20 个字符。

您的错误是认为最大深度是正在优化的（或需要优化的） - 但霍夫曼编码针对编码文本长度进行了优化。

作为旁注，正如我在评论中提到的，霍夫曼产生“一个”最佳解决方案，而不是“那个”最佳解决方案，我认为较低深度的解决方案可能同样好，但它不会变得更好。