浅谈赫夫曼树及其应用(文件压缩)
日常生活中经常会使用到文件压缩，但是基本很少有人会问到压缩是如何实现的。所谓的，就是把文本重新进行编码，减少不必要的空间。目前最新技术在编码上已经很强大，但是笔者不打算说那些很高深的压缩技术（其实那些高深的压缩技术，其实笔者也不懂）。虽然有很多高深的压缩技术，但是目前经常使用到的压缩和解压缩技术都是基于赫夫曼的研究基础上发展而来。所以今天就简单介绍一个最基本的压缩编码方法-----赫夫曼编码。
一、实例开篇
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次以上的判断才能得到结果，显然是十分不合理的。
成绩分布规律
如果能依照成绩概率分布的规律,如下图，更改成绩等级判断逻辑，那么程序判断的次数将大大较少。
更改后的逻辑判断
二、赫夫曼定义
按照上面的两种逻辑，可以把上述的逻辑分别简化成下图的二叉树结构。其中A表示不及格、B及格、C中等、D良好、E优秀。分支线上的数字表示成绩所占比例数。
屏幕快照 2017-09-11 下午11.37.15.png
在说赫夫曼之前先说明另个概念：
-
路径长度: 从树中的一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称作路径长度。
-
树的路径长度 : 树的路径长度就是从树根到每一个结点的路径长度之和。
说完了上述的两个概念，看一下赫夫曼树的定义。
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径WPL长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径WPL长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
关于赫夫曼树的定义出现了权。如果考虑到带权的节点，节点的带权路径长度为从该节点到树根之间的路径长度与节点上权的乘积。
按照上述所讲，则上图中二叉树a的WPL = 5 * 1 + 15 * 2 + 40 * 3 + 30 * 4 + 10 * 4 = 315。二叉树b的WPL = 5 * 3 + 15 * 3 + 40 * 2 + 30 * 2 + 10 * 2 = 220。315和220这两个结果分别意味着，如果用二叉树 a 的判断方法，10000个学生的成绩需要做31500次比较，而二叉树 b 的判断方法只要做22000次比较。很显然，二叉树b的效率比a高了很多。
三、赫夫曼构造原理
看了上述两个二叉树的对比，但是想二叉树 b 这样的高效的二叉树又是如何得到的？
总共分为四个步骤。
-
1、构成初始集合
对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）
-
2、选取左右子树
在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
-
3、删除左右子树
从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
-
4、重复二和三两步，
重复二和三两步，直到集合F中只有一棵二叉树为止。
结合上述的步骤，看看如何将二叉树 a 转为二叉树 b。
-
第一步,先把有权值得叶子结点按照从小到大的顺序排列成一个有序序列,即为A5,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
屏幕快照 2017-09-12 下午10.17.20.png
- 第七步，将N3替换N2和D，排序得到C40，N3为40。
-
第八步，重复步骤二，将C于N3作为一个新节点T的两个子节点。即完成赫夫曼树的构造。
赫夫曼树构造完成
四、赫夫曼编码
赫夫曼树最大的成绩是在当前远距离通讯过程中，解决了数据传输最优化问题。比如有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这几个字符都在输的最末端，所以不会出现这种容易混淆的问题。另外一点，当然是编码和解码都要规定好同样的赫夫曼编码规则。
