java - 对霍夫曼树感到困惑

Question

生成霍夫曼树的快速教程

对霍夫曼树感到困惑。在上面那个链接的末尾附近，它显示了剩下 2 个元素的树，然后是完整的树。我对它的分支方式感到困惑。哈夫曼树是否有特定的分支方式？

例如，57:* 及其右孩子 35:* 向右分支。是不是左边有 35 个分支，右边有 22 个分支？另外，为什么 22:* 不与 15:4 配对 - 它只是与 20:5 配对以创建一棵新树。

从最初的观察看来，这棵树似乎不需要平衡或具有任何特定的顺序，除了叶子的频率加起来就是父节点的值。两个人用相同的数据创建一棵霍夫曼树最终会得到不同的编码值吗？

Answer 1

到目前为止的帖子都是错误的和误导性的：选择具有相同权重的叶子确实很重要，它们确实改变了它们压缩数据的程度。

这是一个反例，演示了不同的选择如何导致不同的压缩率： ABBBCCCDDDDEEEEEEEE

A：1，B：3，C：3，D：4，E：8。第一步：取A和B组成一个权重为4的节点。 第二步：

如果您在第一步中使用 C 获取新创建的节点，那么您将 (19 (11 (7 (4 (1-A) (3-B)) (3-C)) (4-D)) (8-E))得到 37 位压缩数据。

另一方面，如果您使用权重为 4 的 D，而不是新创建的节点，您将 (19 (11 (4 (1-A) (3-B)) (7 (3-C) (4-D))) (8-E))得到 41 位压缩数据。

Answer 2

霍夫曼树的关键是：

按频率排序这个列表，使两个最低的元素成为叶子

如果您有两个以上频率最低的元素（例如 3,4,4...），则任何两个都可以（3 和 4 中的任何一个 - 而不是两个 4）。此外，这些最低元素中的哪一个被分配 0 和哪个是 1 并不重要。这两个事实允许不同但有效的霍夫曼编码来自相同的数据。

霍夫曼树应该通过频率而不是节点数来平衡。因此以下是平衡的：

(100 (50 (25 (12 (12 1)))))

这不是：

(((100 50) 25) ((12 12) 1)))

特别是在您的问题中，15 与 20 而不是 22 配对，因为 15 和 20 是两个最低的剩余值（均低于 22）。任何一个分支（左或右）都可以，只要它是一致的（在同一算法中总是更小的左，或者总是更小的右，以便可以在另一端重建编码）。

Answer 3

一切都在页面上进行了解释。22:* 没有与 15:4 配对，因为在每一步中，两个具有最低元素的节点被组合在一起。这将创建一个独特的订单。

霍夫曼代码可以不同（如果您有多个具有相同频率的值或交换左/右的 0 和 1 表示），但霍夫曼长度不能。

左/右分支只是如何绘制树或用图形表示它的问题，所以这无关紧要。