7

生成霍夫曼树的快速教程

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

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

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

4

3 回答 3

6

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

这是一个反例,演示了不同的选择如何导致不同的压缩率: 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 位压缩数据。

于 2012-12-11T11:17:37.943 回答
5

霍夫曼树的关键是:

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

如果您有两个以上频率最低的元素(例如 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)。任何一个分支(左或右)都可以,只要它是一致的(在同一算法中总是更小的左,或者总是更小的右,以便可以在另一端重建编码)。

于 2010-06-08T01:22:01.793 回答
2

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

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

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

于 2010-06-08T01:26:27.667 回答