0

我试图通过 Huffman 算法手动解决两种不同的压缩场景，在每一个场景中，我们从一个包含元组(symbol, frequency)作为其项目的有序队列开始，我们将尝试形成一个字典：

step 0:
[c:3] [b:4] [a:5]

step 1:
[a:5]    [7]
     [c:3] [b:4]

step 2:
     [12]
[a:5]    [7]
     [c:3] [b:4]

如果我们认为左边是 0，右边是 1，那么我们有一个字典：

a -> 0
b -> 11
c -> 10

直到现在，一切看起来都是正确的。但是让我们假设我们的初始队列如下所示：

step 0:
[c:1] [b:2] [a:4]

step 1:
    [3]      [a:4]
[c:1] [b:2]

step 2:
         [7]
    [3]      [a:4]
[c:1] [b:2]

产生以下字典：

a -> 1
b -> 01
c -> 00

这似乎不对（两者a都b相等）。

我究竟做错了什么？我可以if在树的根部查看其中一个分支实际上是叶子，选择该方向作为 1 的方向，但这对我来说似乎并不干净。我想我一定是错过了什么？

4

2 回答 2

2

位序列不相等。如果你有一个像这样的字符串：

01100

那么就只能解压为“bac”了。您必须以在序列中保留前导零的方式存储压缩结果，因此例如可以将上面的内容填充到 01100000 或 00001100 以填充输出字节，然后与长度 5 一起存储。当然问题是仅使用输出的第一个或最后一个字节，具体取决于您选择填充的哪一侧。

于 2012-06-19T04:58:34.100 回答
1

关键是字典中的位序列在解码时不应引起歧义。序列的值无关紧要。

在霍夫曼编码中，歧义是通过只有编码树中的叶子才能容纳要编码的字符的条件来解决的。上面的树遵循这个规则，所以生成的编码没有问题。

于 2012-06-19T04:56:51.387 回答