4

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

这是一个例子：

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

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

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

4

2 回答 2

5

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

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

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

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

因此，这两个位代码按符号顺序 A、C、E 分配，类似地，四个位代码按 D、F 顺序分配。较短的代码在较长的代码之前分配。

在查找代码长度时会出现一种不同且有趣的歧义。根据相同频率节点的组合顺序，即当您选择两个以上的最低频率节点时，您实际上可以最终得到完全相同最优的不同代码长度集。即使代码长度不同，当您将长度乘以频率并将它们相加时，您会得到两个不同代码的完全相同的位数。

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

例如，考虑频率 A: 2, B: 2, C: 1, D: 1。你首先将 C 和 D 组合得到 2。然后你有频率 2 的 A、B 和 C+D。现在你可以选择将 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 位来表示这些符号。

于 2013-06-01T16:31:39.130 回答
2

问题是，没有问题。

你的霍夫曼树是有效的，它在编码和解码后也给出了完全相同的结果。试想一下，如果您要手动构建一棵霍夫曼树，那么总会有更多方法可以组合具有相等（或最小差异）值的项目。例如，如果你有A B C（每个人的频率为 1），你可以首先将AandB和结果与C，或首先B与C和结果与 a 结合。

你看，还有更正确的方法。

编辑：即使只有一种可能的方法来按频率组合项目，您也可以获得不同的结果，因为您可以为左侧或右侧分支分配 1，因此您将获得不同（正确）的结果。

于 2013-06-01T14:53:59.107 回答