Rob*_*ert 3 compression algorithm tree encoding huffman-code
我真的很为合并在霍夫曼编码中具有相同“权重”的树的顺序而苦苦挣扎。我查看了很多来源，但它们似乎都只涵盖“简单情况”，其中不超过两个具有相同权重的元素，或者根本没有涵盖整个主题。
假设我有以下要编码的字符串：ABCDEE. （风格基于本网站）
所以我有：
FREQUENCY VALUE
--------- -----
1 A
1 B
1 C
1 D
2 E
我现在开始用两个最小的元素构建树：
问题 1)我是否必须使用A & B或如何决定我应该使用哪些值？我知道它们必须是最小的，但除此之外呢？例如A & D？
这是重要末（可以说，我做到以下几点：）
2:[A&B] 2:[B&C]
/ \ / \
1:A 1:B 1:B 1:C
以及下表：
FREQUENCY VALUE
--------- -----
2 [A&B]
2 [C&D]
2 E
问题 2）再次...我应该以什么顺序合并树？例如[A&B]&E或[A&B]&[C&D]
因为，如果我[A&B]&E先合并，树将如下所示：
4:[A&B&E]
/ \
2:[A&B] 2:E
/ \
1:A 1:B
（问题3）如何决定2:E应该在左边还是在右边？)
加入后[C&D]最终的树看起来像这样：
6:[A&B&C&D&E]
/ \
2:[C&D] 4:[A&B&E]
/ \ / \
1:C 1:D 2:[A&B] 2:E
/ \
1:A 1:B
但是，如果我从加入开始[A&B]&[C&D]：
4:[A&B&C&D]
/ \
2:[A&B] 2:[C&D]
/ \ / \
1:A 1:B 1:C 1:D
然后 join E，最终的树看起来像这样：
6:[A&B&C&D&E]
/ \
E:2 4:[A&B&C&D]
/ \
2:[A&B] 2:[C&D]
/ \ / \
1:A 1:B 1:C 1:D
所以在第一个变体E中将是11和在第二个变体中0。或者作为另一个例子C，00vs 是110......
我认为这里必须有一个基本规则，因为霍夫曼编码必须是确定性的（才能正确解码），不是吗！？
当您对两个最低权重有多个选择时，选择哪一对并不重要。对于所有选择，霍夫曼算法将返回一组代码，这些代码最小化对提供的集合进行编码的总位数。
因此，霍夫曼算法不是确定性的，除非对选择施加其他约束。尽管算法可以提供不同的结果，但这并不能阻止编码器/解码器组合的确定性。所需要的只是将生成的霍夫曼码与编码数据一起正确传输，以便解码器可以对其进行解码。非确定性显示的唯一一件事是符号的频率集不是霍夫曼码的充分描述符。
正如另一个答案中所指出的，通过要求代码是规范的，可以减少大量可能的代码。这减少了传输霍夫曼代码所需的位数，因为您不再需要区分所有可能的结果代码。对于规范代码，您不必描述哈夫曼树或代码的特定位值。这一切都可以简单地从编码每个符号所需的位数推导出来。因此，霍夫曼码（或实际上任何前缀码）的充分描述符是每个符号的位数。
重要的是要注意，即使您将结果限制为规范代码，霍夫曼算法仍然可以为同一组频率产生一组不同的代码长度，这取决于在选择两个最低权重子树时所做的选择。下面是一个例子：
考虑符号和频率 A: 2, B: 2, C: 1, D: 1。你必须将 C 和 D 组合起来得到 2 的权重。现在你有三个 2 的权重，所以要组合三个选择。A 和 B，A 和 CD，或 B 和 CD。第一个选择与后两个选择根本不同。如果将 A 和 B 组合，则以位为单位的结果代码长度为：A = 2、B = 2、C = 2 和 D = 2。另一方面，如果将 B 和 CD 组合，则最终得到 A = 1、B = 2、C = 3 和 D = 3。同一组频率的两个不同规范代码！
你可能会问，哪一个是“正确的”？答案是他们两个都是。原因是如果您将频率乘以长度，您将获得相同的总位数来对集合进行编码。2x2 + 2x2 + 1x2 + 1x2 = 2x1 + 2x2 + 1x3 + 1x3 = 12。
因此，即使您将代码限制为规范，也不要感到惊讶，您可以从 Huffman 算法中得到不止一个答案。