algorithm - 对于霍夫曼代码，完整二叉树的优势是什么？

Question

我正在研究用于对字符流进行位编码的 Huffman 代码，并读到最佳代码将由一个完整的二叉树表示，其中每个不同的字符由一个叶子表示，并且所有内部节点都包含两个子节点。

我想知道为什么全二叉树是这里的最佳选择？换句话说，全二叉树的优势是什么？

Answer 1

这不是选择，而是等价。

最优霍夫曼码由有限状态机解码，其中

• 每个状态正好有两个出口（下一位是0或1）
• 每个状态只有一个条目
• 所有包含输出符号的状态都是停止状态，并且
• 所有停止状态都包含输出符号

这相当于一个搜索树，其中

• 所有内部节点正好有两个孩子
• 所有节点都只有一个父节点
• 所有包含输出符号的节点都是叶节点，并且
• 所有叶节点都包含输出符号

也有非最优霍夫曼码，它们具有不包含输出符号的停止状态/叶节点。这样的二叉树不会是满的。

Answer 2

反证法：

假设树 T 不是为给定字符及其频率提供最佳霍夫曼码的完整二叉树。由于 T 不是一棵完全二叉树，因此存在一个节点 N，它只有一个子节点 C。

让我们用C替换N来构造一个新的二叉树T'。与树T相比，C的叶子节点的深度在T'中减少了1。因此T'提供了比T更好的解决方案，这证明T不是最优的.

  T                T'

  /\              /\
 .  N            .  C
.  /            .
. C             .

Answer 3

您问为什么要使用完整的二叉树。这实际上是三个问题。

如果您询问“完整”，那么对于任何正确生成的霍夫曼代码，它必须是完整的。

如果您要询问“二进制”，则霍夫曼代码中遇到的每个位都有两种可能性，0 或 1，因此每个节点必须有两个分支。

但是，如果您要询问“树”，则根本不需要将代码表示为树。有许多表示不仅可以完整地表示代码，而且还可以比树更短的表示压缩流和更快的解码。

示例是使用规范的霍夫曼代码，并将其简单地表示为每个位长度的符号计数，以及相应符号的列表。这在puff.c 代码中使用。或者您可以生成一组表，分阶段一次解码多个位，用于zlib 的 inflate。还有其他的。