java - 对哈夫曼树感到困惑

Question

A quick tutorial on generating a huffman tree

对哈夫曼树感到困惑。在上面那个链接的末尾附近，它显示了剩下 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 位压缩数据。