6.14. 哈夫曼编码树¶
6.14.1. 哈夫曼编码树¶
人们常常可以用空间需求的改善来换取运行时间上的代价。在许多情形下，这种取舍是值得的。一个典型的例子是把文件存储在磁盘上。如果文件不经常使用，所有者可能希望压缩它们以节省空间。以后使用时可以解压，这会花费一些时间，但只需一次。
在计算机程序中，我们常常通过给每个项分配一个唯一的编码来表示一组项。例如，标准的 ASCII 编码 方案给每个字符分配一个唯一的八位值。要提供足够的唯一编码、使每个字符都有不同的编码，需要至少一定数量的二进制位。例如，要表示 ASCII 字符集的 128 个符号，需要 \(\left\lceil log\ 128\right\rceil\) 即七位，才能提供所需的 128 个唯一编码。 [1]
表示 \(n\) 个唯一编码值需要 \(\left \lceil log\ n \right\rceil\) 位，这一要求假定所有编码长度相同，ASCII 编码就是如此。这类编码称为 定长编码 。如果所有字符的使用频率都相同，那么定长编码方案是最节省空间的方法。然而，你可能已经注意到，在许多应用中并非所有字符的使用频率都相同。例如，英文文档中各个字母的使用频率差别很大。
表 6.14.1 给出了字母表中各字母的相对频率。从该表可以看出，字母 'E' 出现的频率约为字母 'Z' 的 60 倍。在普通 ASCII 中，单词 "DEED" 和 "MUCK" 占用相同的空间（四个字节）。像 "DEED" 这样由相对常见的字母组成的单词，似乎应当比 "MUCK" 这样由相对不常见的字母组成的单词占用更少的空间。
如果某些字符比其他字符使用得更频繁，是否有可能利用这一事实，给它们分配较短的编码呢？代价可能是其他字符需要更长的编码，但如果这些字符出现得足够少，这也许是值得的。这一概念正是当今常用文件压缩技术的核心。下一节介绍一种分配 变长编码 的方法，称为 哈夫曼编码 。虽然它最简单的形式并不常用于文件压缩（有更好的方法），但哈夫曼编码体现了这类编码方案的精髓。研究哈夫曼编码的一个动机是，它让我们第一次有机会看到一种称为 搜索 trie 的树结构。
6.14.1.1. 构建哈夫曼编码树¶
哈夫曼编码为字符分配编码，使得编码的长度取决于对应字符的相对频率或 权值 。因此，它是一种变长编码。如果字母的估算频率与编码消息中实际出现的频率相符，那么该消息的长度通常会小于使用定长编码时的长度。每个字母的哈夫曼编码由一棵满二叉树导出，这棵树称为 哈夫曼编码树 ，或简称为 哈夫曼树 。哈夫曼树的每个叶结点对应一个字母，我们把叶结点的权值定义为其对应字母的权值（频率）。目标是构建一棵具有 最小外部路径权值 的树。把一个叶结点的 加权路径长度 定义为其权值乘以其深度。对于给定的叶结点集合，具有最小外部路径权值的二叉树，就是加权路径长度之和最小的那棵。权值高的字母深度应当小，这样它对总路径长度的贡献最小。因此，如果另一个字母的权值较小，它就可能被推到树中更深的位置。
为 \(n\) 个字母构建哈夫曼树的过程相当简单。首先，创建 \(n\) 棵初始哈夫曼树组成的集合，其中每棵都是包含一个字母的单个叶结点。把这 \(n\) 棵部分树放入一个按权值（频率）组织的优先队列。接着，从优先队列中取出前两棵树（即权值最小的两棵）。把这两棵树合并成一棵新树，其根以这两棵树为子结点，其权值等于这两棵树权值之和。把这棵新树放回优先队列。重复这一过程，直到所有部分哈夫曼树都合并为一棵。
下面的幻灯片演示了表 6.14.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; }
}
这个实现类似于
类层次结构（class hierarchy）
实现满二叉树的典型方式。
有一个名为 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' 分配给连接结点与其右子结点的边。下面的幻灯片演示了这一过程。
现在我们看到了边如何与编码中的位相关联，为每个字母生成编码就很简单了（因为每个字母都对应树中的一个叶结点）。
现在我们有了每个字母的编码，对文本消息进行编码，就是用其二进制编码替换消息中的每个字母。为此可以使用一张查找表。
6.14.1.2. 解码¶
如果一组编码中没有任何一个是另一个的前缀，就称这组编码满足 前缀性质 。前缀性质保证解码一个位串时不会产生歧义。换句话说，在解码过程中，一旦到达某个编码的最后一位，我们就知道它对应的是哪个字母。哈夫曼编码当然具有前缀性质，因为某个编码的任何前缀都对应一个内部结点，而所有编码都对应叶结点。
当我们使用哈夫曼编码树解码一个字符时，我们沿着由编码字符串中的位所决定的路径在树中行进。每个 '0' 位表示向左分支，每个 '1' 位表示向右分支。下面的幻灯片展示了如何通过适当地遍历树来解码一条消息的示例。
6.14.1.3. 哈夫曼编码的效率如何？¶
理论上，只要真实频率已知，并且字母的频率与该字母在消息中的上下文无关，哈夫曼编码就是最优的编码方法。在实践中，英文文本文档中字母的频率会随上下文而变化。例如，虽然在英文文档中 E 是字母表中最常用的字母，但作为单词的首字母，T 更为常见。这就是为什么大多数商业压缩工具不把哈夫曼编码作为其主要编码方法，而是使用能够利用字母上下文的技巧。
影响哈夫曼编码压缩效率的另一个因素是字母的相对频率。有些频率模式相比定长编码节省不了空间；另一些则可以实现很大的压缩。一般来说，当字母频率变化较大时，哈夫曼编码效果更好。
对所有 ASCII 符号进行哈夫曼编码，效果应当比这个例子更好。表 6.14.1 中的字母并不典型，因为常见字母相对于罕见字母而言太多了。对所有 26 个字母进行哈夫曼编码，期望成本为每个字母 4.29 位。等价的定长编码约需五位。这对定长编码有些不太公平，因为五位实际上可以容纳 32 个编码，而字母只有 26 个。更一般地说，如果把 ASCII 编码按每个字符八位计算，对典型文本文件进行哈夫曼编码大约能比 ASCII 编码节省 40%。对二进制文件（例如编译后的可执行文件）进行哈夫曼编码，其分布频率会截然不同，因此空间节省量也不同。大多数商业压缩程序会使用两到三种编码方案，以适应不同类型的文件。
在解码示例中，"DEED" 用 8 位编码，比定长编码所需的十二位节省了 33%。然而，"MUCK" 需要 18 位，比相应的定长编码占用更多空间。问题在于 "MUCK" 由那些预计不常出现的字母组成。如果消息与字母的期望频率不符，那么编码的长度也不会如预期那样。
你可以使用下面的可视化工具，为你自己的一组字母和频率创建哈夫曼树。
