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

Question

你如何使用诸如 NEED 之类的霍夫曼编码对单词进行编码

Answer 1

霍夫曼编码基本上使用可变长度的位串来表示标记(通常是字符，有几个异常(exception))。 token 越常见，它的位长就越短，并且这(通常)在处理流时是动态的。

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

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

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%。