algorithm - 具有相同权重树的霍夫曼编码合并顺序

Question

在霍夫曼编码中，我真的很纠结于合并具有相同“权重”的树的顺序。我查看了很多资源，但它们似乎都涵盖了“简单情况”，即不超过两个具有相同权重的元素，或者根本没有涵盖整个主题。

---

假设我有以下要编码的字符串: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

以及下表:

    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...

我认为这里一定有一条我遗漏的基本规则，因为霍夫曼编码必须是确定性的(才能正确解码)，不是吗!？

Answer 1

当您对两个最低权重有多个选择时，您选择哪一对并不重要。对于所有选择，霍夫曼算法将返回一组代码，该代码集可最大限度地减少对提供的集合进行编码的总位数。

因此，霍夫曼算法不是确定性的，除非对选择施加其他约束。尽管该算法可以提供不同的结果，但这不会阻止编码器/解码器组合的确定性。所需要的只是将生成的霍夫曼代码与编码数据一起正确传输，以便解码器可以对其进行解码。非确定性唯一表明的是符号的频率集不足以描述霍夫曼码。

如另一个答案所述，通过要求 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。同一组频率的两个不同规范代码!

您可能会问，哪一个是“正确的”？答案是他们都是。原因是如果将频率乘以长度，您将获得相同的总位数来对集合进行编码。 2x2 + 2x2 + 1x2 + 1x2 = 2x1 + 2x2 + 1x3 + 1x3 = 12。

因此，即使您将代码限制为规范，您也可以从霍夫曼算法中得到不止一个答案，请不要感到惊讶。