哈夫曼编码

Huffman树及其应用一、Huffman树二、Huffman编码最优二叉树Huffman树Huffman编码带权路径长度最短的树不等长编码是通信中最经典的压缩编码1树的带权路径长度如何计算？WPL=wklkk=1nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：WPL=WPL=WPL=Huffman树是WPL最小的树树中所有叶子结点的带权路径长度之和3646352一、Huffman树（最优二叉树）路径：路径长度：树的路径长度：带权路径长度：树的带权路径长度：Huffman树：由一结点到另一结点间的分支所构成。路径上的分支数目。从树根到每一结点的路径长度之和。结点到根的路径长度与结点上权的乘积（WPL）若干术语：debacfg即树中所有叶子结点的带权路径长度之和带权路径长度最小的树。例如：a→e的路径长度＝树长度＝210Huffman常译为赫夫曼、霍夫曼、哈夫曼、胡夫曼等WeightedPathLength31.构造Huffman树的基本思想：例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4，怎样编码才能使它们组成的报文在网络中传得最快？法1：等长编码（如二进制编码）令d=00，i=01，a=10，n=11，则：WPL1＝2bit×(7＋5＋2＋4）＝36法2：不等长编码（如Huffman编码）令d=0;i=10,a=110,n=111，则：明确：要实现Huffman编码，就要先构造Huffman树讨论：Huffman树有什么用？权值大的结点用短路径，权值小的结点用长路径。WPL最小的树频度高的信息用短码，低的用长码，传输效率肯定高！WPL2=1bit×7＋2bit×5+3bit×(2+4)=35最小冗余编码、信息高效传输42.构造Huffman树的步骤（即Huffman算法）：(1)由给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}（即森林），其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。(2)在F中选取两棵根结点权值最小的树做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。(3)在F中删去这两棵树，同时将新得到的二叉树加入F中。(4)重复(2)和(3),直到F只含一棵树为止。这棵树便是Huffman树。怎样证明它就是WPL最小的最优二叉树？参考《信源编码》总之，每次合并当前值最小的两个权。(此树特征：没有度为1的结点)5step1：对权值进行合并、删除与替换——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权具体操作步骤：a.初始方框表示外结点（叶子，字符）圆框表示内结点（合并后的权值）b.合并{2}{4}c.合并{5}{6}d.合并{7}{11}谁左谁右？不规定就不会惟一6step2：按左“0”右“1”对Huffman树的所有分支编号dain111000Huffman编码结果：d=0,i=10,a=110,n=111WPL=1bit×7＋2bit×5+3bit(2+4)=35（小于等长码的WPL=36）特征：每一码不会是另一码的前缀，译码时可惟一复原Huffman编码也称为前缀码——将Huffman树与Huffman编码挂钩7二、Huffman编码哈夫曼编码的基本思想是——出现概率大的信息用短码，概率小的用长码,最小冗余Huffman编码不等长编码是通信中最经典的压缩编码按左“0”右“1”对Huffman树的所有分支编号如何将Huffman树与Huffman编码挂钩?8本节重点：如何编程实现Huffman编码？建议1：Huffman树中结点的结构可设计成4或5分量形式：charweightparentlchildrchild将整个Huffman树的结点存储在一个数组HT[1..n..m]中;（Huffman树内外结点总数m=2n-1）各叶子结点的编码存储在另一“复合”数组HC[1..n]中。(n个权值就是n个叶子,将对应n个不同码串)建议2：Huffman树的存储结构可采用顺序存储结构：即：先构造Huffman树HT再求出n个权值/字符的Huffman编码HC9m=n0+n2=n+(n-1)=2n-1Huffman编码举例解：先将概率放大100倍，以方便构造哈夫曼树。放大后的权值集合w={7,19,2,6,32,3,21,10}，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。例1【严题集6.26③】：假设用于通信的电文仅由8个字母{a,b,c,d,e,f,g,h}构成，它们在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，试为这8个字母设计哈夫曼编码。如果用0～7的二进制编码方案又如何？【类同P148例2】1010717000—000—000—000—000—-00000000r0010002100300320060020019007lpw13121011987654321w={7,19,2,6,32,3,21,10}在机内存储形式为:23528211940100bca116d6032egfh请注意：哈夫曼树样式不惟一，编程时应该有约定√√599√√111010491728√√√√√√40√√60100双亲parent左右孩子lchild,rchild36111811111011121227对应的哈夫曼编码：符编码频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符编码频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.101110001101011001011011011111000001010011100101110111Huffman码的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.613(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3二进制等长码的WPL＝按左0右1标注000000111111101071723528211940100bca116d6032egfh12另一种表示：13自己上机练习说明：设字符集为26个英文字母，其出现频度如下表所示。51481156357203251频度zyxwvut字符11611882380频度p21fq15gr47hsonmlkj字符5710332221364186频度iedcba空格字符要求：先建Huffman树，再利用此树对任一字符串文件进行编码和译码——即设计一个Huffman编/译码器14typedefstruct{unsignedintweight；//权值分量（可放大取整）unsignedintparent，lchild，rchild；//双亲和孩子分量}HTNode，*HuffmanTree；//用动态数组存储Huffman树typedefchar**HuffmanCode；//动态数组存储Huffman编码表Huffman树和Huffman树编码的存储表示：000r0920019007lpw321双亲*HuffmanTree或HT向量样式：HT[3].parent=9指针型指针……15Huffman编码的实现：先构造Huffman树HT，再求出N个字符的Huffman编码HC。voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){if(n=1)return;m=2*n-1;//n个叶子的HuffmanTree共有2n-1个结点；HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0单元未用for(p=HT+1,i=1;i=n;++i,++p,++w)*p={*w,0,0,0};//给前n个单元初始化for(；i=m;++i,++p)*p={0,0,0,0};//对叶子之后的存储单元清零for(i=n+1;i=m;++i){//建Huffman树(从n个叶子后开始存内结点)Select(HT,i-1,s1,s2);//在HT[1…i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2（教材未列此函数源码）HT[s1].parent=i;HT[s2].parent=i;//给双亲分量赋值HT[i].lchild=s1;HT[i].rchild=s2;//给合并后的内结点赋孩子值HT[i].weight=HT[s1].weight+HT[s2].weight;}*w存放n个字符的权值int*w是表明w是一个指向int数组的指针,*w即取一个int,w++后*w取下一个元素……w这里和数组名(即指向该int数组的指针)等价。s200rs1090i20i7lpwis2s116sizeof()可以对变量或变量类型运算,sizeof(char*)是一个char型指针的空间大小,如定义char*p,那么sizeof(p)就是结果,和sizeof(char*)等价。(续前)再求出n个字符的Huffman编码HCHC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符//编码的头指针向量（一维数组）见P149图17cd=(char*)malloc(n*sizeof(char));//分配求编码的临时最长空间cd[n-1]=“\0”;//编码结束符（从cd[0]~cd[n-1]为合法空间）for(i=1;i=n;++i)//逐个字符求Huffman编码{start=n-1;//编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码{if(HT[f].lchild==c)cd[--start]=“0”;elsecd[--start]=“1”;}HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间，并以数组形式存放各码串指针strcpy(HC[i],&cd[start]);//从cd复制编码串到HC所指空间}free(cd);//释放临时空间}//HuffmanCoding