大话数据结构-6.12 赫夫曼树及其应用 200- 高飞网

6.12 赫夫曼树及其应用 200

2016-12-27 00:04:53.0

6.12.1 赫夫曼树

    以上学时通过100分制得分,划分成绩等级的算法为例:

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

    上面的算法看似没有什么问题,但一张好的考卷,应该让成绩大部分处理中等或良好的的范围,优秀和不及格都应该较少才对,而这面的算法,使得所有的成绩都要先判断是否及格,再逐级而上得到结果。输入量很大时,其实算法是有效率问题的。

    如果在实际的学习生活中,学生的成绩在5个等级上的分布规律如下表

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

    把上图中的二叉树重新进行分配如下:

    这样似乎更为高效一些。

6.12.2 赫夫曼树定义与原理

    先把以上两棵二叉树简化为叶子结点带权的二叉树,如下图。其中A为不及格、B表示及格、C表示中等、D表示良好、E表示优秀。每个叶子的分支线上的数字表示成绩所占比例。


    从树中一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称为路径长度。树的路径长度就是从树根到每一结点的路径长度之和。二叉树a的路径长度为1+1+2+2+3+3+4+4=20,二叉树b的树路径长度为1+2+3+3+2+1+2+2=16。

    如果考虑到带权的结点,结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。带权路径长度WPL最小的二叉树称做赫夫曼树(最优二叉树)。这两棵树的带权路径长度分别为:

    二叉树a:5*1+15*2+40*3+30*4+10*4=315

    二叉树b:5*3+15*3+40*2+30*2+10*2=220

    把路径长度理解为条件语句到达某个判断点的步数,权重理解为相关数据出现的比重,则如果有10000个学生的百分制成绩需要计算机,用二叉树a和b,分别需要31500和22000次比较,差不多少了三分之一步数。

    那么如何将二叉树a转为赫夫曼树呢?

    步骤:

  1. 先把有权值的叶子结点按照从小到大的顺序,排列成一个有序序列,即:A5、E10、B15、D30、C40。
  2. 取头两个最小权值的结点作为一个新节点N1的两个子结点,注意相对较小的是左孩子,这里就是A为N1的左孩子,E为N1的右孩子,如下图,新结点的权值为两个叶子权值的和,即5+10=15。
  3. 将N1替换A与E,插入有序序列中,保持从小到大排列。即。N115,B15,D30,C40
  4. 重复步骤2。将N1与B作为一个新结点N2的两个子结点,N2的权值为:15+15=30
  5. 将N2替换N1与B,插入有序序列中,保持从小到大排列。即:N230,D30,C40。
  6. 重复步骤2。将N2与D作为一个新结点N3的两个子结点。N3的权值为:30+30=60。
  7. 将N3替换N2与D,插入有序序列中,保持从小到大排列,即:C40,N360。
  8. 重复步骤2。将C与N3作为一个新结点T的两个子结点,由于T即是根结点,完成赫夫曼树的构造。

    虽然6-12-8是赫夫曼树,但由于每次判断都要两次比较(如根结点就是a<80 && a>79。两次比较才能得到y或n的结果),所以总体性能上,反而不如图6-12-3的二叉树性能高。

    构造赫夫曼树算法描述:

  1. 根据续写的n个权值{w1,w2,w3,...wn}构成n棵二叉树的集合F={T1,T2,...,Tn},其中每棵二叉树Ti中只有一个带权为wi根结点,其左右子树均为空。
  2. 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左右子树的权值之和。
  3. 在F中删除这两棵树,同时将新得到的二叉树加入F中
  4. 重复2和3步骤,直到F只含一棵树为止,这棵树便是赫夫曼树。

6.12.3 赫夫曼编码

    假如有一段文字内容为“BADCADFEED”要通过网络传输给别人,显示机器是用0和1的位表示这些内容,如下是ABCDFE这六个字母的编码:

    这样真正传输的数据就是编码后的“001000011010000011101100100011”,对方接收时按3位一分来译码。如果内容很长,这个二进制串也将非常长。而事实上,这些字母的出现频率是不相同的,比如英文中“a、e、i、o、u”出现的比较高。

    假设六个字母的频率为A 27、B 8、C 15、D 15、E 30、F 5,合起来正好是100%,则意味着可以用赫夫曼树来规划它们。

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

    此时,对这六个字母用其从根到叶子所经过的路径的0或1来编码,可以得到如下表:

    将原文字内容“BADCADFEED”再次编码,可见:

原编码二进制串001000011010000011101100100011
30个字符
新编码二进制串100101001010100100011110025个字符

    由上可知数据被压缩了。

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

    当收到 1001010010101001000111100 时,由约定好的赫夫曼树可知,1001为B,01为A,如下图:

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