霍夫曼编码码字的变化

Question

我正在尝试解决一些哈夫曼编码问题，但是我总是得到不同的编码值（而不是长度）。 例如，如果字符 'c' 的编码是100，在我的解决方案中它是101。

以下是一个例子：

字符 频率 编码 我的解决方案 A 22 00 10 B 12 100 010 C 24 01 11 D 6 1010 0110 E 27 11 00 F 9 1011 0111

两个解决方案的编码长度相同，并且没有一个编码是另一个编码的前缀。

这是否使我的解决方案有效？还是只能有2种解决方案，最优的和翻转最优的位？

- a.u.r

Answer 1

有96种方式可以将0和1分配给该长度集合，所有这些方式都是完全有效的、最优的前缀编码。你已经展示了其中两种。

存在一些约定来定义“规范”的哈夫曼编码，以解决歧义。定义规范编码的价值在于从压缩机到解压机传输代码。只要双方知道并同意如何明确地分配0和1，就只需要传输每个符号的代码长度——而不是代码本身。 deflate format 从最短的代码0开始递增。在每个代码长度内，按符号值排序，即按符号排序。因此，对于您的代码，规范的哈夫曼编码将是：

A - 00
C - 01
E - 10
B - 110
D - 1110
F - 1111

所以，这两个二进制码按符号顺序A、C、E分配，同样地，四位二进制码按D、F的顺序分配。较短的代码在较长的代码之前分配。

在找到编码长度时，存在一个不同且有趣的歧义。根据等频节点的组合顺序，即当您有多个最低频率节点选择时，您实际上可能会得到完全相同的一组代码长度。即使代码长度不同，当您将长度乘以频率并将它们加起来时，您将获得完全相同的位数。

同样地，不同的代码都是最优且有效的。在选择要组合的节点时，有方法来解决这种歧义，其中好处可以是最小化树的深度。这可以减少表驱动哈夫曼解码的表大小。

例如，考虑频率为A:2、B:2、C:1、D:1的情况。您首先将C和D组合以得到2。然后，您有A、B和C+D都具有频率2。现在，您可以选择将A和B组合，或者将C+D与A或B组合。这给出了两个不同的比特长度集。如果您组合A和B，则得到长度：A-2、B-2、C-2和D-2。如果您将C+D与B组合，则得到A-1、B-2、C-3、D-3。这两种都是最优代码，因为2x2 + 2x2 + 1x2 + 1x2 = 2x1 + 2x2 + 1x3 + 1x3 = 12，因此这两个代码使用12位来表示那些多次出现的符号。

- Mark Adler

---

后一种歧义似乎很少被提及，所以看到它被讨论是很好的。 - JasonD

Answer 2

问题是，其实并没有问题。

您的哈夫曼树是有效的，编码和解码后结果完全相同。只需想象一下，如果您手动构建哈夫曼树，总有更多的方法将具有相等（或最小差异）值的项目组合在一起。例如，如果您有A B C（每个频率为1），可以先将A和B组合，再与C组合，或者先将B和C组合，再与A组合。

您看，有更多的正确方式。 编辑：即使按频率仅有一种可能的组合方式，您也可以获得不同的结果，因为您可以将1分配给左侧或右侧分支，因此您将获得不同（但正确）的结果。

- bpoiss

---

实际上，你不需要等频率才能得到上述的歧义。所有符号的频率和所有构造节点的频率总和可以不同。这将无歧义地生成一棵可能的哈夫曼树。然而，在这个单一树的每个分支处，你仍然可以任意独立地将0分配给左分支和1分配给右分支，或者将1分配给左分支和0分配给右分支。然后你会得到不同的二进制编码。 - Mark Adler

你所提到的歧义更有趣，并且在某些情况下可能会导致不同的哈夫曼树，具有不同的编码长度。请参见我的答案。 - Mark Adler

你说得对，我已经将这个加入到我的答案中了。是的，但在使用生成的哈夫曼树进行编码-解码后，结果必须与之前相同，否则生成树时会出现错误。 - bpoiss

这就是为什么规范哈夫曼编码在两端以相同的方式解决歧义非常有用。 - Mark Adler