需要有关如何使用霍夫曼代码对单词进行编码的帮助

如何使用哈夫曼代码对单词进行编码，例如 NEED

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

通常有两个特殊的标记，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 位。这个速度接近 1:8 的压缩比 (97.5%)。

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