1

当我使用霍夫曼贪心算法构造二叉树时，如果所有四个字母的概率相同，我会得到以下结果：

  • 00
  • 01
  • 10
  • 11

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

4

1 回答 1

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了。你从下一点开始。

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

于 2013-02-06T16:29:45.357 回答