Question

6.12.1　赫夫曼树

“喂，兄弟，最近无聊透顶了，有没有什么书可看？”“我这有《三国演义》的电子书，你要不要？”“‘既生瑜，何生亮。’《三国演义》好呀，你邮件发给我！”“OK！文件1M多大小，好像大了点。我打个包，稍等……哈哈，少了一半，压缩效果不错呀。”“太棒了，快点传给我吧。”

图6-12-1

这是我们生活中常见的对白。现在我们都是讲究效率的社会，什么都要求速度，在不能出错的情念他的成就，于是就把他在编码中用到的特殊的二叉树称之为赫夫曼树，他的编码方法称为赫夫曼编码。也就是说，我们现在介绍的知识全都来自于近60年前这位伟大科学家的研究成果，而我们平时所用的压缩和解压缩技术也都是基于赫夫曼的研究之上发展而来，我们应该要记住他。

那么压缩而不出错是如何做到的呢？简单说，就是把我们要压缩的文本进行重新编码，以减少不必要的空间。尽管现在最新技术在编码上已经很好很强大，但这一切都来自于曾经的技术积累，我们今天就来介绍一下最基本的压缩编码方法——赫夫曼编码。

在介绍赫夫曼编码前，我们必须得介绍赫夫曼树，而介绍赫夫曼树，我们不得不提这样一个人，美国数学家赫夫曼（David Huffman），也有的翻译为哈夫曼。他在1952年发明了赫夫曼编码，为了纪念他的成就，于是就把他在编码中用到的特殊的二叉树称之为赫夫曼树，他的编码方法称为赫夫曼编码。也就是说，我们现在介绍的知识全都来自于近60年前这位伟大科学家的研究成果，而我们平时所用的压缩和解压缩技术也都是基于赫夫曼的研究之上发展而来，我们应该要记住他。

什么叫做赫夫曼树呢？我们先来看一个例子。

过去我们小学、中学一般考试都是用百分制来表示学科成绩的。这带来了一个弊端，就是很容易让学生、家长，甚至老师自己都以分取人，让分数代表了一切。有时想想也对，90分和95分也许就只是一道题目对错的差距，但却让两个孩子可能受到完全不同的待遇，这并不公平。于是在如今提倡素质教育的背景下，我们很多的学科，特别是小学的学科成绩都改作了优秀、良好、中等、及格和不及格这样模糊的词语，不再通报具体的分数。

不过对于老师来讲，他在对试卷评分的时候，显然不能凭感觉给优良或及格不及格等成绩，因此一般都还是按照百分制算出每个学生的成绩后，再根据统一的标准换算得出五级分制的成绩。比如下面的代码就实现了这样的转换。

if (a < 60)
    b = "不及格";
else if (a < 70)
    b = "及格";
else if (a < 80)
    b = "中等";
else if (a < 90)
    b = "良好";
else
    b = "优秀";

图6-12-2粗略看没什么问题，可是通常都认为，一张好的考卷应该是让学生成绩大部分处于中等或良好的范围，优秀和不及格都应该较少才对。而上面这样的程序，就使得所有的成绩都需要先判断是否及格，再逐级而上得到结果。输入量很大的时候，其实算法是有效率问题的。

图6-12-2

如果在实际的学习生活中，学生的成绩在5个等级上的分布规律如表6-12-1所示。

表6-12-1

那么70分以上大约占总数80%的成绩都需要经过3次以上的判断才可以得到结果，这显然不合理。

有没有好一些的办法，仔细观察发现，中等成绩（70～79分之间）比例最高，其次是良好成绩，不及格的所占比例最少。我们把图6-12-2这棵二叉树重新进行分配。改成如图6-12-3的做法试试看。

图6-12-3

从图中感觉，应该效率要高一些了，到底高多少呢。这样的二叉树又是如何设计出来的呢？我们来看看赫夫曼大叔是如何说的吧。

6.12.2　赫夫曼树定义与原理

我们先把这两棵二叉树简化成叶子结点带权的二叉树（注：树结点间的边相关的数叫做权Weight），如图6-12-4所示。其中A表示不及格、B表示及格、C表示中等、D表示良好、E表示优秀。每个叶子的分支线上的数字就是刚才我们提到的五级分制的成绩所占百分比。

图6-12-4

赫夫曼大叔说，从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。图6-12-4的二叉树a中，根结点到结点D的路径长度就为4，二叉树b中根结点到结点D的路径长度为2。树的路径长度就是从树根到每一结点的路径长度之和。二叉树a的树路径长度就为1+1+2+2+3+3+4+4=20。二叉树b的树路径长度就为1+2+3+3+2+1+2+2=16。

如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。假设有n个权值{w₁,w₂,...,w_n}，构造一棵有n个叶子结点的二叉树，每个叶子结点带权w_k，每个叶子的路径长度为l_k，我们通常记作，则其中带权路径长度WPL最小的二叉树称做赫夫曼树。也有不少书中也称为最优二叉树，我个人觉得为了纪念做出巨大贡献的科学家，既然用他们的名字命名，就应该要坚持用他们的名字称呼，哪怕“最优”更能体现这棵树的品质也应该只作为别名。

有了赫夫曼对带权路径长度的定义，我们来计算一下图6-12-4这两棵树的WPL值。

二叉树a的WPL=5×1+15×2+40×3+30×4+10×4=315

注意：这里5是A结点的权，1是A结点的路径长度，其他同理。

二叉树b的WPL=5×3+15×3+40×2+30×2+10×2=220

这样的结果意味着什么呢？如果我们现在有10000个学生的百分制成绩需要计算五级分制成绩，用二叉树a的判断方法，需要做31500次比较，而二叉树b的判断方法，只需要22000次比较，差不多少了三分之一量，在性能上提高不是一点点。

那么现在的问题就是，图6-12-4的二叉树b这样的树是如何构造出来的，这样的二叉树是不是就是最优的赫夫曼树呢？别急，赫夫曼大叔给了我们解决的办法。

1．先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即：A5，E10，B15，D30，C40。

2．取头两个最小权值的结点作为一个新节点N₁的两个子结点，注意相对较小的是左孩子，这里就是A为N₁的左孩子，E为N₁的右孩子，如图6-12-5所示。新结点的权值为两个叶子权值的和5+10=15。

图6-12-5

3．将N₁替换A与E，插入有序序列中，保持从小到大排列。即：N₁15，B15，D30，C40。

4．重复步骤2。将N₁与B作为一个新节点N₂的两个子结点。如图6-12-6所示。N₂的权值=15+15=30。

图6-12-6

5．将N₂替换N₁与B，插入有序序列中，保持从小到大排列。即：N₂30，D30，C40。

6．重复步骤2。将N₂与D作为一个新节点N₃的两个子结点。如图6-12-7所示。N₃的权值=30+30=60。

图6-12-7

7．将N₃替换N₂与D，插入有序序列中，保持从小到大排列。即：C40，N₃60。

8．重复步骤2。将C与N₃作为一个新节点T的两个子结点，如图6-12-8所示。由于T即是根结点，完成赫夫曼树的构造。

图6-12-8

此时的图6-12-8二叉树的带权路径长度WPL=40×1+30×2+15×3+10×4+5×4=205。与图6-12-4的二叉树b的WPL值220相比，还少了15。显然此时构造出来的二叉树才是最优的赫夫曼树。

不过现实总是比理想要复杂得多，图6-12-8虽然是赫夫曼树，但由于每次判断都要两次比较（如根结点就是a<80&&a>=70，两次比较才能得到y或n的结果），所以总体性能上，反而不如图6-12-3的二叉树性能高。当然这并不是我们要讨论的重点了。

通过刚才的步骤，我们可以得出构造赫夫曼树的赫夫曼算法描述。

1.根据给定的n个权值{w₁,w₂,...,w_n}构成n棵二叉树的集合F={T₁,T₂,...,T_n}，其中每棵二叉树T_i中只有一个带权为w_i根结点，其左右子树均为空。
2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3.在F中删除这两棵树，同时将新得到的二叉树加入F中。
4.重复2和3步骤，直到F只含一棵树为止。这棵树便是赫夫曼树。

6.12.3　赫夫曼编码

当然，赫夫曼研究这种最优树的目的不是为了我们可以转化一下成绩。他的更大目的是为了解决当年远距离通信（主要是电报）的数据传输的最优化问题。

比如我们有一段文字内容为“BADCADFEED”要网络传输给别人，显然用二进制的数字（0和1）来表示是很自然的想法。我们现在这段文字只有六个字母ABCDEF，那么我们可以用相应的二进制数据表示，如表6-12-2所示。

表6-12-2

这样真正传输的数据就是编码后的“001000011010000011101100100011”，对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制串也将非常的可怕。而且事实上，不管是英文、中文或是其他语言，字母或汉字的出现频率是不相同的，比如英语中的几个元音字母“ae i o u”，中文中的“的 了 有 在”等汉字都是频率极高。

假设六个字母的频率为A 27，B 8，C 15，D15，E 30，F 5，合起来正好是100%。那就意味着，我们完全可以重新按照赫夫曼树来规划它们。

图6-12-9左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0，右分支改为1后的赫夫曼树。

图6-12-9

此时，我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，可以得到如表6-12-3所示这样的定义。

表6-12-3

我们将文字内容为“BADCADFEED”再次编码，对比可以看到结果串变小了。

• 原编码二进制串：001000011010000011101100100011（共30个字符）
• 新编码二进制串：1001010010101001000111100（共25个字符）

也就是说，我们的数据被压缩了，节约了大约17%的存储或传输成本。随着字符的增加和多字符权重的不同，这种压缩会更加显出其优势。

当我们接收到1001010010101001000111100这样压缩过的新编码时，我们应该如何把它解码出来呢？

编码中非0即1，长短不等的话其实是很容易混淆的，所以若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。

你仔细观察就会发现，表6-12-3中的编码就不存在容易与1001、1000混淆的“10”和“100”编码。

可仅仅是这样不足以让我们去方便地解码的，因此在解码时，还是要用到赫夫曼树，即发送方和接收方必须要约定好同样的赫夫曼编码规则。

当我们接收到1001010010101001000111100时，由约定好的赫夫曼树可知，1001得到第一个字母是B，接下来01意味着第二个字符是A，如图6-12-10所示，其余的也相应的可以得到，从而成功解码。

图6-12-10

一般地，设需要编码的字符集为{d₁,d₂,...,d_n}，各个字符在电文中出现的次数或频率集合为{w₁,w₂,...,w_n}，以d₁,d₂,...,d_n作为叶子结点，以w₁,w₂,...,w_n作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码。