具有相同权重树的霍夫曼编码合并顺序
Merge Order in Huffman Coding with same weight trees
我真的很纠结在霍夫曼编码中合并具有相同 "weight" 的树的顺序。我查看了很多资源，但它们似乎都只涵盖了 "simple cases"，其中具有相同权重的元素不超过两个，或者根本没有涵盖整个主题。
假设我有以下要编码的字符串：ABCDEE。 （样式基于 this website）
所以我有：
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
以及以下 table:
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
然后加入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 将是 00 与 110...
我认为这里一定有一个我遗漏的基本规则，因为霍夫曼编码必须是确定性的（才能正确解码），不是吗！？
合并顺序真的不重要。该算法中重要的是每次都选择最小的子树。因为贪婪地这样做，最终，你总是会以最短的方式到达那棵树中出现频率最高的字母。
当您对两个最低权重有多个选择时，选择哪一对并不重要。对于所有选择，霍夫曼算法将 return 一组代码，该代码集最小化所提供集合的编码位数。
因此，霍夫曼算法 不是 确定性的，除非对选择施加其他限制。尽管该算法可以提供不同的结果，但这 不会 阻止编码器/解码器组合的确定性。所需要的只是将生成的霍夫曼代码与编码数据一起正确传输，以便解码器可以对其进行解码。非确定性唯一表明的是符号的频率集不足以描述霍夫曼码。
如另一个答案中所述，通过要求 code be canonical 减少了可能的代码数量。这减少了传输霍夫曼代码所需的位数，因为您不再需要区分所有可能的结果代码。对于规范代码，您不必描述霍夫曼树或代码的特定位值。这一切都可以简单地从对每个符号进行编码所需的位数中推导出来。因此，霍夫曼代码（或实际上任何前缀代码）的充分描述符是每个符号的位数。
重要的是要注意，即使您将结果限制为规范代码，霍夫曼算法仍然可以为同一组代码生成不同的代码长度集频率，取决于选择两个最低权重子树时所做的选择。这是一个例子：
考虑符号和频率 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。同一组频率的两个不同规范代码！
你可能会问，"right"是哪一个？答案是他们都是。原因是如果将频率乘以长度，您将获得相同的总位数来对集合进行编码。 2x2 + 2x2 + 1x2 + 1x2 = 2x1 + 2x2 + 1x3 + 1x3 = 12.
因此，即使您将代码限制为规范，您也可以从霍夫曼算法中得到不止一个答案，请不要感到惊讶。
我真的很纠结在霍夫曼编码中合并具有相同 "weight" 的树的顺序。我查看了很多资源，但它们似乎都只涵盖了 "simple cases"，其中具有相同权重的元素不超过两个，或者根本没有涵盖整个主题。
假设我有以下要编码的字符串：ABCDEE。 （样式基于 this website）
所以我有：
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
以及以下 table:
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
然后加入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 将是 00 与 110...
我认为这里一定有一个我遗漏的基本规则，因为霍夫曼编码必须是确定性的（才能正确解码），不是吗！？
合并顺序真的不重要。该算法中重要的是每次都选择最小的子树。因为贪婪地这样做，最终，你总是会以最短的方式到达那棵树中出现频率最高的字母。
当您对两个最低权重有多个选择时，选择哪一对并不重要。对于所有选择，霍夫曼算法将 return 一组代码，该代码集最小化所提供集合的编码位数。
因此，霍夫曼算法 不是 确定性的，除非对选择施加其他限制。尽管该算法可以提供不同的结果，但这 不会 阻止编码器/解码器组合的确定性。所需要的只是将生成的霍夫曼代码与编码数据一起正确传输，以便解码器可以对其进行解码。非确定性唯一表明的是符号的频率集不足以描述霍夫曼码。
如另一个答案中所述，通过要求 code be canonical 减少了可能的代码数量。这减少了传输霍夫曼代码所需的位数，因为您不再需要区分所有可能的结果代码。对于规范代码，您不必描述霍夫曼树或代码的特定位值。这一切都可以简单地从对每个符号进行编码所需的位数中推导出来。因此，霍夫曼代码（或实际上任何前缀代码）的充分描述符是每个符号的位数。
重要的是要注意，即使您将结果限制为规范代码，霍夫曼算法仍然可以为同一组代码生成不同的代码长度集频率，取决于选择两个最低权重子树时所做的选择。这是一个例子：
考虑符号和频率 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。同一组频率的两个不同规范代码！
你可能会问，"right"是哪一个？答案是他们都是。原因是如果将频率乘以长度，您将获得相同的总位数来对集合进行编码。 2x2 + 2x2 + 1x2 + 1x2 = 2x1 + 2x2 + 1x3 + 1x3 = 12.
因此，即使您将代码限制为规范，您也可以从霍夫曼算法中得到不止一个答案，请不要感到惊讶。