18. 哈夫曼编码树¶
18.1. 哈夫曼编码树¶
人们常常可以用空间需求的改善来换取运行时间上的代价。 在许多情形下，这种取舍是值得的。 一个典型的例子是把文件存储在磁盘上。 如果文件不经常使用，所有者可能希望压缩它们以节省空间。 以后使用时可以解压，这会花费一些时间，但只需一次。
在计算机程序中，我们常常通过给每个项分配一个唯一的编码 来表示一组项。 例如，标准的 ASCII 编码 方案给每个字符分配一个唯一的八位值。 要提供足够的唯一编码、使每个字符都有不同的编码， 需要至少一定数量的二进制位。 例如，要表示 ASCII 字符集的 128 个符号， 需要 \(\left\lceil log\ 128\right\rceil\) 即七位， 才能提供所需的 128 个唯一编码。 [1]
表示 \(n\) 个唯一编码值需要 \(\left \lceil log\ n \right\rceil\) 位， 这一要求假定所有编码长度相同，ASCII 编码就是如此。 这类编码称为 定长编码 。 如果所有字符的使用频率都相同， 那么定长编码方案是最节省空间的方法。 然而，你可能已经注意到，在许多应用中并非所有字符的使用频率都相同。 例如，英文文档中各个字母的使用频率差别很大。
表 11.18.1 给出了字母表中各字母的相对频率。 从该表可以看出，字母 'E' 出现的频率约为字母 'Z' 的 60 倍。 在普通 ASCII 中，单词 "DEED" 和 "MUCK" 占用相同的空间（四个字节）。 像 "DEED" 这样由相对常见的字母组成的单词， 似乎应当比 "MUCK" 这样由相对不常见的字母组成的单词 占用更少的空间。
如果某些字符比其他字符使用得更频繁， 是否有可能利用这一事实，给它们分配较短的编码呢？ 代价可能是其他字符需要更长的编码， 但如果这些字符出现得足够少，这也许是值得的。 这一概念正是当今常用文件压缩技术的核心。 下一节介绍一种分配 变长编码 的方法， 称为 哈夫曼编码 。 虽然它最简单的形式并不常用于文件压缩（有更好的方法）， 但哈夫曼编码体现了这类编码方案的精髓。 研究哈夫曼编码的一个动机是， 它让我们第一次有机会看到一种称为 搜索 trie 的树结构。
18.1.1. 构建哈夫曼编码树¶
哈夫曼编码为字符分配编码，使得编码的长度 取决于对应字符的相对频率或 权值 。 因此，它是一种变长编码。 如果字母的估计频率与编码消息中实际出现的频率相符， 那么该消息的长度通常会小于使用定长编码时的长度。 每个字母的哈夫曼编码由一棵满二叉树导出， 这棵树称为 哈夫曼编码树 ， 或简称为 哈夫曼树 。 哈夫曼树的每个叶结点对应一个字母， 我们把叶结点的权值定义为其对应字母的权值（频率）。 目标是构建一棵具有 最小外部路径权值 的树。 把一个叶结点的 加权路径长度 定义为其权值 乘以其深度。 对于给定的叶结点集合，具有最小外部路径权值的二叉树， 就是加权路径长度之和最小的那棵。 权值高的字母深度应当小，这样它对总路径长度的贡献最小。 因此，如果另一个字母的权值较小，它就可能被推到树中更深的位置。
为 \(n\) 个字母构建哈夫曼树的过程相当简单。 首先，创建 \(n\) 棵初始哈夫曼树组成的集合， 其中每棵都是包含一个字母的单个叶结点。 把这 \(n\) 棵部分树放入一个按权值（频率）组织的优先队列。 接着，从优先队列中取出前两棵树（即权值最小的两棵）。 把这两棵树合并成一棵新树，其根以这两棵树为子结点， 其权值等于这两棵树权值之和。 把这棵新树放回优先队列。 重复这一过程，直到所有部分哈夫曼树都合并为一棵。
下面的幻灯片演示了 表 11.18.2 中八个字母的哈夫曼树构建过程。 [2]
下面是哈夫曼树结点的实现。
/** Huffman tree node implementation: Base class */
interface HuffBaseNode {
public boolean isLeaf();
public int weight();
}
/** Huffman tree node: Leaf class */
class HuffLeafNode implements HuffBaseNode {
private char element; // Element for this node
private int weight; // Weight for this node
/** Constructor */
HuffLeafNode(char el, int wt)
{ element = el; weight = wt; }
/** @return The element value */
public char value() { return element; }
/** @return The weight */
public int weight() { return weight; }
/** Return true */
public boolean isLeaf() { return true; }
}
/** Huffman tree node: Internal class */
class HuffInternalNode implements HuffBaseNode {
private int weight;
private HuffBaseNode left;
private HuffBaseNode right;
/** Constructor */
HuffInternalNode(HuffBaseNode l,
HuffBaseNode r, int wt)
{ left = l; right = r; weight = wt; }
/** @return The left child */
public HuffBaseNode left() { return left; }
/** @return The right child */
public HuffBaseNode right() { return right; }
/** @return The weight */
public int weight() { return weight; }
/** Return false */
public boolean isLeaf() { return false; }
}
这个实现类似于
类层次结构
实现满二叉树的典型方式。
有一个名为 HuffNode 的抽象 基类 ，
以及两个名为 LeafNode 和 IntlNode 的
子类 。
这个实现反映了叶结点和内部结点所包含的信息截然不同这一事实。
下面是哈夫曼树类的实现。
/** A Huffman coding tree */
class HuffTree implements Comparable<HuffTree> {
private HuffBaseNode root;
/** Constructors */
HuffTree(char el, int wt)
{ root = new HuffLeafNode(el, wt); }
HuffTree(HuffBaseNode l, HuffBaseNode r, int wt)
{ root = new HuffInternalNode(l, r, wt); }
public HuffBaseNode root() { return root; }
public int weight() // Weight of tree is weight of root
{ return root.weight(); }
public int compareTo(HuffTree t) {
if (root.weight() < t.weight()) { return -1; }
else if (root.weight() == t.weight()) { return 0; }
else { return 1; }
}
}
下面是建树过程的实现。
public static HuffTree buildTree(MinHeap<HuffTree> hheap) {
HuffTree tmp1, tmp2, tmp3 = null;
while (hheap.heapSize() > 1) { // While two items left
tmp1 = hheap.removemin();
tmp2 = hheap.removemin();
tmp3 = new HuffTree(tmp1.root(), tmp2.root(),
tmp1.weight() + tmp2.weight());
hheap.insert(tmp3); // Return new tree to heap
}
return tmp3; // Return the tree
}
buildHuff 接受 fl 作为输入，它是部分哈夫曼树的最小堆，
最初是上面幻灯片第 1 步中所示的单个叶结点。
函数 buildTree 的主体主要是一个 for 循环。
在 for 循环的每次迭代中，取出堆中最前面的两棵部分树，
分别放入变量 temp1 和 temp2 。
创建一棵树（ temp3 ），使其左、右子树分别为
temp1 和 temp2 。
最后，把 temp3 放回 fl 。
分配和使用哈夫曼编码
一旦哈夫曼树构建完成，给各个字母分配编码就很容易了。 从根开始，我们为树中的每条边分配 '0' 或 '1'。 '0' 分配给连接结点与其左子结点的边， '1' 分配给连接结点与其右子结点的边。 下面的幻灯片演示了这一过程。
现在我们看到了边如何与编码中的位相关联， 为每个字母生成编码就很简单了 （因为每个字母都对应树中的一个叶结点）。
现在我们有了每个字母的编码， 对文本消息进行编码，就是用其二进制编码替换消息中的每个字母。 为此可以使用一张查找表。
18.1.2. 解码¶
如果一组编码中没有任何一个是另一个的前缀， 就称这组编码满足 前缀性质 。 前缀性质保证解码一个位串时不会产生歧义。 换句话说，在解码过程中，一旦到达某个编码的最后一位， 我们就知道它对应的是哪个字母。 哈夫曼编码当然具有前缀性质， 因为某个编码的任何前缀都对应一个内部结点， 而所有编码都对应叶结点。
当我们使用哈夫曼编码树解码一个字符时， 我们沿着由编码串中的位所决定的路径在树中行进。 每个 '0' 位表示向左分支，每个 '1' 位表示向右分支。 下面的幻灯片展示了如何通过适当地遍历树来解码一条消息的示例。
18.1.3. 哈夫曼编码的效率如何？¶
理论上，只要真实频率已知， 并且字母的频率与该字母在消息中的上下文无关， 哈夫曼编码就是最优的编码方法。 在实践中，英文文本文档中字母的频率会随上下文而变化。 例如，虽然在英文文档中 E 是字母表中最常用的字母， 但作为单词的首字母，T 更为常见。 这就是为什么大多数商业压缩工具 不把哈夫曼编码作为其主要编码方法， 而是使用能够利用字母上下文的技巧。
影响哈夫曼编码压缩效率的另一个因素 是字母的相对频率。 有些频率模式相比定长编码节省不了空间； 另一些则可以实现很大的压缩。 一般来说，当字母频率变化较大时，哈夫曼编码效果更好。
对所有 ASCII 符号进行哈夫曼编码，效果应当比这个例子更好。 表 11.18.1 中的字母并不典型， 因为常见字母相对于罕见字母而言太多了。 对所有 26 个字母进行哈夫曼编码， 期望代价为每个字母 4.29 位。 等价的定长编码约需五位。 这对定长编码有些不太公平， 因为五位实际上可以容纳 32 个编码，而字母只有 26 个。 更一般地说，如果把 ASCII 编码按每个字符八位计算， 对典型文本文件进行哈夫曼编码大约能比 ASCII 编码节省 40%。 对二进制文件（例如编译后的可执行文件）进行哈夫曼编码， 其分布频率会截然不同，因此空间节省量也不同。 大多数商业压缩程序会使用两到三种编码方案， 以适应不同类型的文件。
在解码示例中，"DEED" 用 8 位编码， 比定长编码所需的十二位节省了 33%。 然而，"MUCK" 需要 18 位，比相应的定长编码占用更多空间。 问题在于 "MUCK" 由那些预计不常出现的字母组成。 如果消息与字母的期望频率不符， 那么编码的长度也不会如预期那样。
你可以使用下面的可视化工具， 为你自己的一组字母和频率创建哈夫曼树。
