数据结构之赫夫曼编码PPT课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,OS,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,1,数据结构,深圳大学,计算机与软件学院,白鉴聪,上节复习,二叉树的存储结构,顺序存储，把普通二叉树补全为完全二叉树，再按层次遍历顺序保存,链式存储，二叉链表、三叉链表,掌握存储结构的画图方法,二叉树的四种遍历：,前序、中序、后序，采用递归嵌套方式,层次遍历，从上往下，从左到右，把二叉树的链式存储转化为数组存储,3,已知二叉树结构如图所示，求,求先、中、后序遍历结果,画出顺序存储和链式存储结果,练习,a,d,e,b,f,g,c,h,i,j,k,4,6.6,赫夫曼树,最优二叉树,赫夫曼树又称为最优树，是一类带权路径长度最短的树,树的路径和路径长度,路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径长度：路径上的分支数目,树的路径长度：从树根到每个结点的路径长度之和,树路径长度为：,2*1+3*2+1*3=11,A,D,B,F,C,G,E,5,6.6,赫夫曼树,最优二叉树,带权路径长度：从结点到树根之间的路径长度与结点上权的乘积,树的带权路径长度,(WPL),：树中所有叶子结点的带权路径长度之和,WPL=2*5+3*3+2*4=27,A,D,B,F,C,G,E,5,6,6.6,赫夫曼树,最优二叉树,具有,n,个叶子结点,(,每个结点的权值为,w,i,),的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵,WPL,值最小,的树,，称这棵树为,Huffman,树,(,或称最优树,),如图,是权值分别为,2,、,3,、,6,、,7,，具有,4,个叶子结点的二叉树,2,3,6,7,3,6,7,2,6,7,2,3,(a),(b),(c),具有相同叶子结点，不同带权路径长度的二叉树,7,6.6,赫夫曼树,最优二叉树,它们的带权路径长度分别为,：,(a)WPL=2,2+3,2+6,2+7,2=36,(b)WPL=2,1+3,2+6,3+7,3=47,(c)WPL=7,1+6,2+2,3+3,3=34,其中,(c),的,WPL,值最小，称这棵树为最优二叉树或,Huffman,树,8,6.6,赫夫曼树,最优二叉树,赫夫曼树的简单应用,百分制转五级制,将,0,100,分转变为不及格、及格、中等、良好、优良五个级别,普通方法用四次判断语句,不同成绩的分布规律构造赫夫曼树，通过赫夫曼树进行判定，大大减少判断次数,构造二叉树的思路：把分布比例数作为叶子权值，每个结点包含一个判断，把高权值结点放在路径短的地方，低权值放在路径长的地方,9,6.6,赫夫曼树,最优二叉树,赫夫曼树的简单应用,百分制转五级制,将,0,100,分转变为不及格、及格、中等、良好、优良五个级别,分数的分布比例为：,10,6.6,赫夫曼树,最优二叉树,赫夫曼树的简单应用,百分制转五级制,采用普通方法用四次判断语句,若有,10000,个输入数据，根据分数分布比例需要,31500,次,80%,以上数据需要经过,3,次以上的比较才能得到结果,11,6.6,赫夫曼树,最优二叉树,赫夫曼树的简单应用,百分制转五级制,把高比例数据先做比较，程序调整如下，,12,6.6,赫夫曼树,最优二叉树,赫夫曼树的简单应用,百分制转五级制,改进方法中每个比较有包含两次判断，再做细化，得到如下的判定树,10000,个输入数据需要,22000,次判断,13,6.6,赫夫曼树,最优二叉树,赫夫曼树的简单应用,百分制转五级制,以,5,、,15,、,40,、,30,和,10,为权值，构造一颗有,5,个叶子的赫夫曼树，也就得到同样的这颗二叉树,14,6.6,赫夫曼树,赫夫曼树的构造,在,Huffman,树中，权值最大的结点离根最近，权值最小的结点离根最远,构造算法,根据给定的,n,个权值,(w,1,w,2,w,n,),构成,n,棵二叉树的集合,F=T,1,T,2,T,n,，其中每棵二叉树,T,i,中只有一个带树为,T,i,的根结点,在,F,中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和,在,F,中删除这两棵树，同时将新得到的二叉树加入,F,中,重复,2,3,，直到,F,只含一棵树为止,15,6.6,赫夫曼树,赫夫曼树的构造,举例,F:7 5 2 4,F:7 5 6,F:7 11,7,5,2,4,初始,合并,2 4,7,5,2,4,6,F:18,11,7,5,2,4,6,合并,5 6,5,合并,7 11,2,7,4,6,11,18,16,6.6,赫夫曼树,赫夫曼编码,通过赫夫曼树把电文缩短，减少传送时间,编码前,GOOD_G,设给出一段报文：,GOOD_GOOD_GOOD_GOOOOOOOO_OFF,字符集合是,O,G,_,D,F,，各个字符出现的频度,(,次数,),是,W,15,4,4,3,2,。,若给每个字符以等长编码,O:000 G:001 _:010 D:011 F:100,则总编码长度为,(15+4+4+3+2)*3=84.,17,6.6,赫夫曼树,赫夫曼编码,编码后,若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。,各字符,O,G,_,D,F,出现概率为,15/28,4/28,4/28,3/28,2/28,化整为,15,4,4,3,2,各字符出现概率,取整数,为,15,4,4,3,2,如果规定，,Huffman,树的左子树小于右子树，则可构成右图所示,Huffman,树,4,15,4,2,3,G,_,F,D,O,18,6.6,赫夫曼树,赫夫曼编码,编码后,令左孩子分支为编码,0,，右孩子分支为编码,1,将根结点到叶子结点路径上的分支编码，组合起来，作为该字符的,Huffman,码，则可得到：,O:1,_:011,G:010,D:001,F:000,4,15,4,2,3,0,0,0,0,1,1,1,1,G,_,F,D,O,19,6.6,赫夫曼树,赫夫曼编码,则总编码长度为,15*1+(2+3+4+4)*3=54,84,Huffman,是一种前缀编码，解码时不会混淆，如,GOOD,编码为：,01011001,4,15,4,2,3,0,0,0,0,1,1,1,1,G,_,F,D,O,20,已知字符,A,、,B,、,C,、,D,、,E,、,F,，对应权值为,13,、,4,、,22,、,38,、,6,、,17,，若进行赫夫曼编码，请完成以下要求：,构建赫夫曼树，要求左孩子权值不大于右孩子权值,写出每个字符对应的编码，分支编码对应,0,或,1,对以下三个编码串进行解码，若解码异常则直接输出,error,01010011101,，,110101,，,010011011,练习,21,6.6,赫夫曼树,赫夫曼编码,赫夫曼树的实现,typedef struct,unsigned int weight;,unsigned int parent,lchild,rchild;,HTNode,*HuffmanTree;,typedef char*HuffmanCode;,22,6.6,赫夫曼树,赫夫曼编码,赫夫曼树的实现,void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n),if(n=1)return;,m=2*n-1;,HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0,号单元未用,for(i=1;i=n;i+)/,初始化,HTi.weight=wi-1;HTi.parent=0;,HTi.lchild=0;HTi.rchild=0;,/end for,for(i=n+1;i=m;i+)/,初始化,HTi.weight=0;HTi.parent=0;,HTi.lchild=0;HTi.rchild=0;,/end for,23,6.6,赫夫曼树,赫夫曼编码,赫夫曼树的实现,for(i=n+1;i=m;i+)/,建哈夫曼树,/,在,HT1.i-1,中选择,parent,为,0,且,weight,最小的两个结点，,/,其序号分别为,s1,和,s2,。,Select(HT,i-1,s1,s2);,HTs1.parent=i;HTs2.parent=i;,HTi.lchild=s1;HTi.rchild=s2;,HTi.weight=HTs1.weight+HTs2.weight;,/end for,24,6.6,赫夫曼树,赫夫曼编码,赫夫曼树的实现,/-从叶子到根逆向求每个字符的哈夫曼编码-,cd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间,cdn-1=0;/编码结束符。,for(i=1;i=n;+i)/逐个字符求哈夫曼编码,start=n-1;/编码结束符位置,for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent),/从叶子到根逆向求编码,if(HTf.lchild=c)cd-start=0;,else cd-start=1;,HCi=(char*)malloc(n-start)*sizeof(char);,/为第i个字符编码分配空间,strcpy(HCi,/从cd复制编码(串)到HC,free(cd);/释放工作空间,/end function,25,6.6,赫夫曼树,赫夫曼解码,算法流程,定义指针,p,指向赫夫曼树结点，实际是记录结点数组的下标,定义指针,i,指向编码串，定义,ch,逐个取编码串的字符,初始化：读入编码串，设置,p,指向根结点，,i,为,0,执行以下循环：,取编码串的第,i,个字符放入,ch,如果,ch,是字符,0,，表示往左孩子移动，则,p,跳转到右孩子,如果,ch,是字符,1,，表示往右孩子移动，则,p,跳转到右孩子,如果,ch,非,0,非,1,，表示编码串有错误，输出,error,表示解码失败,检查,p,指向的结点是否为叶子,如果是叶子，输出解码，,p,跳回根节点,如果不是叶子，设置,ch,为,3,继续循环，一直到编码串末尾,循环执行完后，如果,ch,值为,3,，输出解码失败，否则成功结束,