奇妙的二叉树：Huffman的贡献
关键字 Huffman
提起 Huffman 这个名字，程序员们至少会联想到二叉树和二进制编码。的确，我们总以 Huffman 编码来概括 D.A.Huffman 个人对计算机领域特别是数据压缩领域的杰出贡献。我们知道，压缩 = 模型 + 编码，作为一种压缩方法，我们必须全面考虑其模型和编码两个模块的功效；但同时，模型和编码两个模块又相互具有独立性。举例来说，一个使用 Huffman 编码方法的程序，完全可以采用不同的模型来统计字符在信息中出现的概率。因此，我们这一章将首先围绕 Huffman 先生最为重要的贡献 —— Huffman 编码展开讨论，随后，我们再具体介绍可以和 Huffman 联合使用的概率模型。
为什么是二叉树
为什么压缩领域中的编码方法总和二叉树联系在一起呢？原因非常简单，回忆一下我们介绍过的“前缀编码”：为了使用不固定的码长表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较长编码的前缀。要构造符合这一要求的二进制编码体系，二叉树是最理想的选择。考察下面这棵二叉树：
根(root)
0 | 1
+------+------+
0 | 1 0 | 1
+-----+-----+ +---+----+
| | | |
a | d e
0 | 1
+-----+-----+
| |
b c
要编码的字符总是出现在树叶上，假定从根向树叶行走的过程中，左转为0，右转为1，则一个字符的编码就是从根走到该字符所在树叶的路径。正因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，符合要求的前缀编码也就构造成功了：
a - 00 b - 010 c - 011 d - 10 e - 11
Shannon-Fano 编码
进入 Huffman 先生构造的神奇二叉树之前，我们先来看一下它的前身，由 Claude Shannon 和 R.M.Fano 两人提出的 Shannon-Fano 编码。
讨论之前，我们假定要编码字符的出现概率已经由某一模型统计出来，例如，对下面这串出现了五种字符的信息( 40 个字符长 ):
cabcedeacacdeddaaabaababaaabbacdebaceada
五种字符的出现次数分别：a - 16，b - 7，c - 6，d - 6，e - 5。
Shannon-Fano 编码的核心仍然是构造二叉树，构造的方式非常简单：
1) 将给定符号按照其频率从大到小排序。对上面的例子，应该得到：
a - 16
b - 7
c - 6
d - 6
e - 5
2) 将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和。我们有：
a - 16
b - 7
-----------------
c - 6
d - 6
e - 5
3) 我们把第二步中划分出的上部作为二叉树的左子树，记 0，下部作为二叉树的右子树，记 1。
4) 分别对左右子树重复 2 3 两步，直到所有的符号都成为二叉树的树叶为止。现在我们有如下的二叉树：
根(root)
0 | 1
+------+------+
0 | 1 0 | 1
+-----+-----+ +---+----+
| | | |
a b c |
0 | 1
+-----+-----+
| |
d e
于是我们得到了此信息的编码表：
a - 00 b - 01 c - 10 d - 110 e - 111
可以将例子中的信息编码为：
cabcedeacacdeddaaabaababaaabbacdebaceada
10 00 01 10 111 110 111 00 10 00 10 ......
码长共 91 位。考虑用 ASCII 码表示上述信息需要 8 * 40 = 240 位，我们确实实现了数据压缩。
Huffman 编码
Huffman 编码构造二叉树的方法和 Shannon-Fano 正好相反，不是自上而下，而是从树叶到树根生成二叉树。现在，我们仍然使用上面的例子来学习 Huffman 编码方法。
1) 将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点）。
a(16) b(7) c(6) d(6) e(5)
2) 在 1 中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值为两棵子树频率值之和。对上面的例子，我们得到一个新的树林：
| (11)
a(16) b(7) c(6) +---+---+
| |
d e
3) 对上面得到的树林重复 2 的做法，直到所有符号都连入树中为止。这一步完成后，我们有这样的二叉树：
根(root)
0 | 1
+------+----------------+
| 0 | 1
| +---------+-----------+
| 0 | 1 0 | 1
a +-------+------+ +-------+-------+
| | | |
b c d e
由此，我们可以建立和 Shannon-Fano 编码略微不同的编码表：
a - 0 b - 100 c - 101 d - 110 e - 111
对例子中信息的编码为：
cabcedeacacdeddaaabaababaaabbacdebaceada
101 0 100 101 111 110 111 0 101 0 101 ......
码长共 88 位。这比使用 Shannon-Fano 编码要更短一点。
让我们回顾一下熵的知识，使用我们在第二章学到的计算方法，上面的例子中，每个字符的熵为：
Ea = - log2(16 / 40) = 1.322
Eb = - log2( 7 / 40) = 2.515
Ec = - log2( 6 / 40) = 2.737
Ed = - log2( 6 / 40) = 2.737
Ee = - log2( 5 / 40) = 3.000
信息的熵为：
E = Ea * 16 + Eb * 7 + Ec * 6 + Ed * 6 + Ee * 5 = 86.601
也就是说，表示该条信息最少需要 86.601 位。我们看到，Shannon-Fano 编码和 Huffman 编码都已经比较接近该信息的熵值了。同时，我们也看出，无论是 Shannon-Fano 还是 Huffman，都只能用近似的整数位来表示单个符号，而不是理想的小数位。我们可以将它们做一个对比：
符号 理想位数 S-F 编码 Huffman 编码
( 熵 ) 需要位数 需要位数
----------------------------------------------------
a 1.322 2 1
b 2.515 2 3
c 2.737 2 3
d 2.737 3 3
e 3.000 3 3
----------------------------------------------------
总 计 86。601 91 88
这就是象 Huffman 这样的整数位编码方式无法达到最理想的压缩效果的原因。
为 Huffman 编码选择模型（附范式 Huffman 编码）
最简单，最容易被 Huffman 编码利用的模型是“静态统计模型”，也就是说在编码前统计要编码的信息中所有字符的出现频率，让后根据统计出的信息建立编码树，进行编码。这种模型的缺点是显而易见的：首先，对数据量较大的信息，静态统计要消耗大量的时间；其次，必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）；再次，事实上，即使不将编码树计算在内，对通常含有 0 - 255 字符集的计算机文件来说，静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文件有时甚至在压缩后反而增大了。所以，“静态统计模型”一般仅作为复杂算法的某一部分出现，在信息的某一局部完成压缩功能。我们很难将其用于独立的压缩系统。
有一种有效的“静态统计模型”的替代方案，如果我们要压缩的所有信息具有某些共同的特性，也即在分布上存在着共同的特征，比如我们要压缩的是普通的英文文本，那么，字母 a 或者字母 e 的出现频率应当是大致稳定的。使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩，不但不用保存多份统计信息，而且一般说来对该类文件有着较好的压缩效果。这种方案除了适应性不太强以外，偶尔还会有一些尴尬的时候。读一遍下面这段话：
If Youth，throughout all history， had had a champion to stand up for it； to show a doubting world that a child can think；and， possibly， do it practically； you wouldn't constantly run across folks today who claim that "a child don't know anything." - Gadsby by E.V.Wright, 1939.
发现什么问题了吗？哦，整段话中竟没有出现一次英文中出现频率最高的字母 e ！真让人惊讶，但没有办法，事先拟定的频率分布总有意外的时候。
对英文或中文文本，有一种比较实用的静态模型：不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩。也就是说，每次编码的不再是 a b c 这样的单个符号，而是 the look flower 这样的单词。这种压缩方式可以达到相当不错的压缩效果，并被广泛地用于全文检索系统。
对基于词的编码方式，需要解决几个技术难点。首先是分词的问题，英文单词可以由词间空格分隔，但中文怎么办呢？其实，有很多中文分词算法可以解决这个问题，本书就不再详细介绍了。王笨笨就曾开发过一个不错的分词模块，但希望通过收取一定报酬的方式提供该模块，如有需要，请和王笨笨 E-Mail 联系。一旦我们将词语分离出来，我们就可以对每个词进行频率统计，然后建立 Huffman 编码树，输出编码时，一个编码将代替一个词语。但要注意，英文和汉语的单词数量都在几万到十几万左右，也就是说，我们的 Huffman 编码树将拥有十几万个叶子节点，这对于一棵树来说太大太大了，系统将无力承担所需要的资源，这怎么办呢？我们可以暂时抛开树结构，采用另一种构造 Huffman 编码的方式——范式 Huffman 编码。
范式 Huffman 编码(Canonical Huffman Code)的基本思路是：并非只有使用二叉树建立的前缀编码才是 Huffman 编码，只要符合(1)是前缀编码(2)某一字符编码长度和使用二叉树建立的该字符的编码长度相同这两个条件的编码都可以叫做 Huffman 编码。考虑对下面六个单词的编码：
符号 出现次数 传统 Huffman 编码 范式 Huffman 编码
------------------------------------------------------------
单词1 10 000 000
单词2 11 001 001
单词3 12 100 010
单词4 13 101 011
单词5 22 01 10
单词6 23 11 11
注意到范式 Huffman 编码的独特之处了吗？你无法使用二叉树来建立这组编码，但这组编码确实能起到和 Huffman 编码相同的作用。而且，范式 Huffman 编码具有一个明显的特点：当我们把要编码的符号按照其频率从小到大排列时，如果把范式 Huffman 编码本身作为单词的话，也呈现出从小到大的字典顺序。
构造范式 Huffman 编码的方法大致是：
1) 统计每个要编码符号的频率。
2) 根据这些频率信息求出该符号在传统 Huffman 编码树中的深度（也就是表示该符号所需要的位数 - 编码长度）。因为我们关心的仅仅是该符号在树中的深度，我们完全没有必要构造二叉树，仅用一个数组就可以模拟二叉树的创建过程并得到符号的深度，具体方法这里就不详述了。
3) 分别统计从最大编码长度 maxlength 到 1 的每个长度对应了多少个符号。根据这一信息从 maxlength 个 0 开始以递增顺序为每个符号分配编码。例如，编码长度为 5 的符号有 4 个，长度为 3 的有 1 个，长度为 2 的有 3 个，则分配的编码依次为： 00000 00001 00010 00011 001 01 10 11
4) 编码输出压缩信息，并保存按照频率顺序排列的符号表，然后保存每组同样长度编码中的最前一个编码以及该组中的编码个数。
现在完全可以不依赖任何树结构进行高速解压缩了。而且在整个压缩、解压缩过程中需要的空间比传统 Huffman 编码少得多。
最后要提到的是，Huffman 编码可以采用自适应模型，根据已经编码的符号频率决定下一个符号的编码。这时，我们无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。但是，采用自适应模型必须考虑编码表的动态特性，即编码表必须可以随时更新以适应符号频率的变化。对于 Huffman 编码来说，我们很难建立能够随时更新的二叉树，使用范式 Huffman 编码是个不错的选择，但依然存在不少技术上的难题。幸好，如果愿意的话，我们可以暂时不考虑自适应模型的 Huffman 编码，因为对于自适应模型我们还有许多更好的选择，下面几章将要谈到的算术编码、字典编码等更为适合采用自适应模型，我们将在其中深入探讨自适应模型的各种实现方法。