algorithm - 对于霍夫曼代码，我应该避免以 0(零)开头的多位代码吗？

Question

当我使用霍夫曼贪婪算法构造二叉树时，如果所有四个字母的概率均等，我将得到以下结果:

• 00
• 01
• 10
• 11

问题是，我的程序将 00 和 01 视为仅 0 和 1。我是否应该限制以 0(零)到 1(一)开头的代码长度？应该使用什么数据类型来存储霍夫曼代码或其各个位？

Answer 1

如果您的“程序将 00 和 01 视为仅 0 和 1”，那么您的程序有错误。

对于四个等概率符号，代码确实是 00、01、10 和 11。这意味着您需要在解码时查找所有这些位。解码时先拉左边的位。所以你得到一个 0。这意味着代码是 00 或 01。然后你拉下一位。它是一个 1。所以现在你有了完整的代码 01。你发出相应的符号，然后重新开始。

更容易看出概率不相等且代码长度不同的更典型情况。考虑这段代码:

a - 0
b - 10
c - 110
d - 111

要解码，您需要从流中提取位。第一位是 1。现在您知道它必须是 a、b、c 或 d。现在你再拉一个 1。你把它降到 c 或 d。你拉一个 0，所以现在你知道它的 d。您从下一位开始。

在您开始提取位并缩小选择范围之前，您不知道代码的长度。解码后您将知道代码的长度。