3

您如何使用霍夫曼代码（例如 NEED）对单词进行编码

4

4 回答 4

5

霍夫曼编码基本上使用可变长度的位串来表示标记（通常是字符，但有几个例外）。令牌越常见，它的位长就越短，这（通常）在处理流时是动态的。

通常有两种特殊标记，ESCAPE 和 END-STREAM。

编码维护一个字典，它基本上是查找位序列以获取令牌。最初它只包含两个特殊标记。

ESCAPE 和 END_STREAM 的初始位序列可以是 0 和 1（这在开始时并不重要）。当编码器接收到一个不在字典中的字符时，它会输出 ESCAPE 和全长标记，然后根据所有标记的频率添加它并分配新的位序列。

所以你的'N'可能会导致输出流：

0 xxxxxxxx
| +- token code for N
+--- ESCAPE

和新字典：

ESCAPE:00
END-STREAM:01
N:1

那么你的'E'可能会导致输出流：

0 xxxxxxxx 0 yyyyyyyy
             +- token code for E

和新字典：

ESCAPE:00
END-STREAM:01
N:10
E:11

您的下一个 E 不会导致 ESCAPE 输出，因为它已经在字典中，因此您只需输出其代码 (11)。它将改变字典，因为 E 现在有更高的计数。这在我们的情况下无关紧要，因为所有字符都是两个二进制数字，但是在更复杂的示例中，“E”标记的位长度会缩短。

当 D 到达时，输出流变为：

0 xxxxxxxx 0 yyyyyyyy 11 0 zzzzzzzz
                      |    +- token code for D
                      +------ second E

和新字典：

ESCAPE:00
END-STREAM:011
N:010
E:11
D:10

因此，您可以看到，随着更多字符的输入，常见字符的位长度会减少，而不常见字符的位长度会增加，从而为您提供压缩。在这种情况下，N（或 D）得到一个 3 位数的代码，而 E 坚持使用 2 位数的代码，因为它们的数量更多。

美妙之处在于您不需要将字典与文件一起存储，因为 ESCAPE 部分也动态构建它以进行解压缩。

此外，因为直到最后都没有 END-STREAM 令牌，所以它的位长越来越大。ESCAPE 与此类似，虽然仍有许多新字符进入，但它的位长保持较短，但当没有新字符到来时，它会遭受与 END-STREAM 相同的命运。

（8 位 ASCII）输入流的最佳情况是一个只包含数百万个相同字符的文件。第一个字符需要 9 位，然后每个附加字符需要 1 位，然后流结束需要 2 位。该速度接近 8 比 1 的压缩率 (97.5%)。

最坏的情况是每个字符中的一个，每个字符花费 9 位加上流的结尾——这实际上将流扩展了 12.5%。

于 2008-12-07T07:06:09.923 回答
1

我想你的意思是霍夫曼编码。这是一种无损压缩数据的算法。简而言之，您将最长和最重复的连续数据位替换为尽可能小的表示形式（这是大多数压缩的工作方式）。例如，一个 HTML 页面可能会将非常常见<DIV的二进制数分配给二进制数01，将每一个的 32 位减少<DIV到仅 2 位。

这是基本的想法。另一个技巧是如何选择数字，这样您就不需要使用固定大小或分隔符。这是使用Huffman Tree完成的。阅读维基百科文章了解更多信息。

于 2008-12-07T06:33:58.443 回答
1

看看Huffman Coding with F#，这是一篇介绍用 F# 编写的 Huffman 编码器/解码器的博客文章。它简短而清晰。

于 2008-12-07T06:56:34.200 回答
0

看看我的 Huffman in C# 项目：https ://github.com/kad0xf/HuffmanSharp

于 2015-07-22T19:38:07.143 回答