huffman-code - 霍夫曼编码码字的变化

Question

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

下面是一个例子:

字符频率码字我的解决方案
一个 22 00 10
乙 12 100 010
24 01 11
D 6 1010 0110
E 27 11 00
传真 9 1011 0111

两种解决方案的码字长度相同，并且不存在作为另一个码字前缀的码字。

这是否使我的解决方案有效？或者它必须只有 2 个解决方案，最佳的一个并翻转最佳的位？

Answer 1

有 96 种可能的方法可以将 0 和 1 分配给该组长度，并且所有方法都是完全有效的、最佳的前缀代码。你已经展示了其中的两个。

存在定义解决歧义的“规范”霍夫曼代码的约定。定义规范代码的值(value)在于将代码从压缩器传输到解压缩器。只要双方都知道并同意如何明确分配 0 和 1，那么只需要传输每个符号的代码长度——而不是代码本身。

deflate format最短代码从零开始，然后递增。在每个代码长度内，代码按符号值排序，即按符号排序。因此，对于您的代码，规范的霍夫曼代码将是:

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 位来表示这些符号多次。