算法快学笔记（七）：赫夫曼，赫夫曼树，赫夫曼编码

1. 赫夫曼

鼎鼎大名赫夫曼树以及赫夫曼编码都是出自赫夫曼这位大牛之手，为表致敬先简单的介绍赫夫曼大神。

赫夫曼，全名David Albert Huffman，1925年8月9日－1999年10月7日，生于美国俄亥俄州，计算机科学家，为霍夫曼编码的发明者。

1951年，赫夫曼在麻省理工学院（MIT）攻读博士学位，他为了完成一篇题为<<查找最有效的二进制编码>>的报告，研究出了赫夫曼树。

1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）中发表了赫夫曼编码。

2. 赫夫曼树

哈夫曼树也叫最优二叉树（哈夫曼树），是赫夫曼编码的理论基础，目前经常使用到的压缩和解压缩技术都是基于赫夫曼的研究基础上发展而来。通过一个例子来展开对赫夫曼树的说明

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

如上代码是百分制考试的评分标准。粗略看上面的代码，貌似没有什么问题。但是通常情况来说一个班级的学生成绩分布在及格、中等、良好的相对较多，分布在优秀和不及格的相对较少。但是上面的代码，最开始的逻辑是先判断是否及格，再逐渐向上得到结果。当输入量很大的时候，算法在效率方面是存在一定问题的。

假设实际中学生在5个等级上成绩分布的概率如下表所示。如果按照上述的代码逻辑执行，70分以上的成绩占总概率的80%，但是想判断出一个70分以上的成绩至少需要执行3次以上的判断才能得到结果，显然是十分不合理的。成绩等级的分布如下：

如果能依照成绩概率分布的规律,如下图，更改成绩等级判断逻辑，那么程序判断的次数将大大较少。

2.1 赫夫曼树原理

按照上面的两种逻辑，可以把上述的逻辑分别简化成下图的二叉树结构。其中A表示不及格、B及格、C中等、D良好、E优秀。分支线上的数字表示成绩所占比例数。

2.1.1 相关概念

1. 路径长度: 从树中的一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称作路径长度。
2. 树的路径长度 : 树的路径长度就是从树根到每一个结点的路径长度之和。
3. 赫夫曼树的定义。若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径WPL长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径WPL长度达到最小，称这样的 二叉树为最优二叉树 ，也称为哈夫曼树(Huffman Tree)。

关于赫夫曼树的定义出现了权。如果考虑到带权的节点，节点的带权路径长度为从该节点到树根之间的路径长度与节点上权的乘积。

按照上述所讲，则上图中:

1. 二叉树a的WPL = 5 * 1 + 15 * 2 + 40 * 3 + 30 * 4 + 10 * 4 = 315。
2. 二叉树b的WPL = 5 * 3 + 15 * 3 + 40 * 2 + 30 * 2 + 10 * 2 = 220。

315和220这两个结果分别意味着，如果用二叉树 a 的判断方法，10000个学生的成绩需要做31500次比较，而二叉树 b 的判断方法只要做22000次比较。很显然，二叉树b的效率比a高了很多。

2.2 赫夫曼构造步骤

看了上述两个二叉树的对比，但是想二叉树 b 这样的高效的二叉树又是如何得到的？

步骤如下。

• 第一步,先把有权值得叶子结点按照从小到大的顺序排列成一个有序序列,即为A5,E10,D10,B15,C70。
• 第二步,取头两个最小权值的结点作为一个新结点N1的两个子结点,注意相对较小的的孩子是左孩子,这里A就是N1的左孩子,D为N1的右孩子,新结点的权值为两个叶子结点的权值之和 5 + 10 = 15;
• 第三步,将N1替换A与E,插入有序序列中,保持从小到大的排序,即 N1 15,B15,C70;
• 第四步,重复步骤2,将N1与B作为一个新结点N2的两个子结点, N2的权值 = 15 + 15 = 30;

• 第五步,将N2替换N1与B,插入有序序列中,保持从小到大的排序,即 N2 ，D30,C40;

• 第六步,重复步骤2,将N2和D作为一个新结点N3的两个子结点。N3的权值为30+30 = 60

• 第七步，将N3替换N2和D，排序得到C40，N3为40。

• 第八步，重复步骤二，将C于N3作为一个新节点T的两个子节点。即完成赫夫曼树的构造。

赫夫曼树构造完成

最终结果的WPL=40 * 1+30 * 2+15 * 3+10 * 4 * 5=205,比之前的220还少了15.此时的二叉树才是最优二叉树（最优赫夫曼树）

3. 赫夫曼树应用之赫夫曼编码

赫夫曼树最大的成绩是在当前远距离通讯过程中，解决了数据传输最优化问题。比如有ABCDEF六个字母，通过0和1编码用二进制字符发送。编码后的数据为000001010011100101，解码的时候可以按照3位一份来解码。不过不管是任何文字语言，字母或汉字在某一话题或其他方面出现的频率是不一样的。如汉字中的“的”、“了”、“你”等等，都是频率极高的汉字。所以因为频频的不同，可以按照赫夫曼树的规律来规划。

假设ABCDEF出现的概率分别为27%、8%、15%、15%、30%、5%。则形成的赫夫曼树如下图。此外我们可以将左右分支分别改为0和1，然后用0和1来编码字母。则编码结果为A=01、B=1001、C=101、D=00、E=11、F=1000。

按照赫夫曼树编码：

• 原本的编码结果为：000001010011100101
• 现在的编码结果为:0110011010011100

现在的编码结果明显要比之前的少了一些，短短是几个字母编码后，少的量不是很大，如果是通篇的文章或更多，那么编码量将会节省很多，这就是文件压缩的原理。并且随着字符的增多，按照权重优先级编码，这种压缩会进一步提升很多。

既然有编码，就必然有解码。简单说说解码，按照赫夫曼树这种编码方法，非0即1，且每个字符编码长短不等很容易混淆。 所以若要设计出长短不等的编码，则必须是任意字符的编码都不是另一个字符编码的前缀 （这种编码通常称为前缀编码）。

自己观察A=01、B=1001、C=101、D=00、E=11、F=1000根本就不存在容易和 1001 、1000混淆的10和100编码，这一点从上面的0和1的左右分支图也能轻易的总结出，因为ABCDEF这几个字符都在输的最末端，所以不会出现这种容易混淆的问题。

最后需要注意的是，是编码和解码需要规定好同样的赫夫曼编码规则。本例的规则如下：