哈夫曼编码教材课件

路径：路径长度：树的路径长度：带权路径长度：树的带权路径长度：霍夫曼树：Huffman树及其应用一、最优二叉树（霍夫曼树）由一结点到另一结点间的分支所构成路径上的分支数目从树根到每一结点的路径长度之和。结点到根的路径长度与结点上权的乘积预备知识：若干术语debacfg树中所有叶子结点的带权路径长度之和带权路径长度最小的树。a→e的路径长度＝树长度＝2101路径：Huffman树及其应用一、最优二叉树（霍Huffman树简介：树的带权路径长度如何计算？WPL=wklkk=1nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：WPL=36WPL=46WPL=35哈夫曼树则是：WPL最小的树。Huffman树WeightedPathLength2Huffman树简介：树的带权路径长度如何计算？WPL=(1)由给定的n个权值{w0,w1,w2,…,wn-1}，构造具有n棵扩充二叉树的森林F={T0,T1,T2,…,Tn-1}，其中每一棵扩充二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。

(2)

重复以下步骤,直到F中仅剩下一棵树为止：

①在F中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。②在F中删去这两棵二叉树。③把新的二叉树加入F。构造霍夫曼树的基本思想：构造Huffman树的步骤（即Huffman算法）：权值大的结点用短路径，权值小的结点用长路径。先举例！3(1)由给定的n个权值{w0,w1,w2,…,例1：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4，怎样编码才能使它们组成的报文在网络中传得最快？法1：等长编码。例如用二进制编码来实现。取d=00，i=01，a=10，n=11怎样实现Huffman编码？法2：不等长编码，例如用哈夫曼编码来实现。取d=0;i=10,a=110,n=111最快的编码是哪个？是非等长的Huffman码！先要构造Huffman树！4例1：设有4个字符d,i,a,n，出现的频度分别为7,5,2操作要点1：对权值的合并、删除与替换——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权构造Huffman树的步骤：注：方框表示外结点（叶子，字符对应的权值），圆框表示内结点（合并后的权值）。5操作要点1：对权值的合并、删除与替换构造Huffman树的步操作要点2：按左0右1对Huffman树的所有分支编号！dain111000Huffman编码结果：d=0,i=10,a=110,n=111WPL=1bit×7＋2bit×5+3bit(2+4)=35特点：每一码都不是另一码的前缀，绝不会错译!称为前缀码——将Huffman树与Huffman编码挂钩6操作要点2：按左0右1对Huffman树的所有分支编号！da例2：假设用于通信的电文仅由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的二进制编码方案又如何？霍夫曼编码的基本思想是：概率大的字符用短码，概率小的用长码。由于霍夫曼树的WPL最小，说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。解：先将概率放大100倍，以方便构造哈夫曼树。

权值集合w={7,19,2,6,32,3,21,10}，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。7例2：假设用于通信的电文仅由8个字母{a,b,c,dw4={19,21,28,32}为清晰起见，重新排序为:

w={2,3,6,7,10,19,21,32}2356w1={5,6,7,10,19,21,32}w2={7,10,11,19,21,32}w3={11,17,19,21,32}111071728211940w5={28,32,40}3260w6={40,60}w7={100}100bcadegfh哈夫曼树××××××××××××××8w4={19,21,28,32}为清晰起见，重新排序为对应的哈夫曼编码（左0右1）：23561110732172821194060100bcadegfh00000111111100符编码频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符编码频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman码的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.61

WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=31100001111011101011111011101000001010011100101110111二进制码9对应的哈夫曼编码（左0右1）：235611107321728另一种结果表示：10另一种结果表示：10例3：设字符集为26个英文字母，其出现频度如下表所示。51481156357203251频度zyxwvut字符11611882380频度p21fq15gr47hsonmlkj字符5710332221364186频度iedcba空格字符先建哈夫曼树，再利用此树对报文“Thisprogramismyfavorite”进行编码和译码。要求编程实现：11例3：设字符集为26个英文字母，其出现频度如下表所示。514提示1：霍夫曼树中各结点的结构可以定义为如下5个分量：charweightparentlchildRchild将整个霍夫曼树的结点存储在一个数组中：HT[1..n];

将结点的编码存储在HC[1..n]中。提示3：霍夫曼树如何构造？构造好之后又如何求得各结点对应的霍夫曼编码？提示2：霍夫曼树的存储结构可采用顺序存储结构：12提示1：霍夫曼树中各结点的结构可以定义为如下5个分量：cha需求分析1.写一个对txt文件压缩和解压的程序，使用动态编码。2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树；3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。应用：压缩程序

——哈弗曼编码算法13需求分析1.写一个对txt文件压缩和解压的程序，使用动态编码概要分析采用顺序表实现对Huffman树的存储//---------------Huffman树存储结构------------------typedefstruct{intweight;intlchild,rchild,parent;}HuffmanTree;typedefHuffmanTreeHTree[m];weight域存有该节点字符的权值，lchild、rchild、parent分别存放该节点的左孩子、右孩子和双亲节点在顺序表中的位置。

14概要分析采用顺序表实现对Huffman树的存储14采用顺序表实现对Huffman编码的存储//---------------Huffman编码存储结构------------------typedefstruct{charch;intstart;charbits[n+1];}HuffmanCode;typedefHuffmanCodeHCode[n];ch存放对应的字符，start存放Huffman编码在字符数组bits[]中开始的位置。15采用顺序表实现对Huffman编码的存储15抽象数据抽象数据类型定义：ADT{数据对象：txt文档基本操作：FileRead(intcount[],chars[],charfilename[])初始条件：压缩文档存在。操作结果：对该文档进行读取，求其所有出现的字符和字符的权值。CreateHuffmanTree(HTreeT,intN,intcount[],chars[])初始条件：以求得该文档的字符和权值。操作结果：建立Huffman树。HuffmanCoding(HTreeT,HCodeH,intN,chars[])初始条件：Huffman树。操作结果：求各个字符的Huffman编码。16抽象数据抽象数据类型定义：16FilePrint(HTreeT,HCodeH,intN)初始条件：求得Huffman编码以及各节点的权值。操作结果：将求得的数据分别存放在HuffmanCode.txt、Char.txt、Weight.txt中。FileWrite(HCodeH,intN,charfilename[])初始条件：求得Huffman编码以及各节点的权值。操作结果：将文档翻译成Huffman编码以字符形式存放在File.txt中。FileConvert(void)初始条件：File.txt存在。操作结果：将字符形式的Huffman编码翻译成二进制形式，每首季8比特就通过位操作合并成一个字节写入文件code.txt中，最后不足8位时将最后的几位存放在Tail.txt中。FileRead(HTreeT,HCodeH)初始条件：压缩生成的HuffmanCode.txt、Char.txt、Weight.txt存在。操作结果：读取字符及其权值和其Huffman编码。17FilePrint(HTreeT,HCodeH,intFileExtract(void)初始条件：压缩结果文件Code.txt和tail.txt存在。操作结果：将code.txt和tail.txt中的字符写成编码的二进制字符形式，写进file00.txt。FileTrans(HTreeT,HCodeH,intN)初始条件：已生成File00,txt并已求得各个字符的Huffman编码，Huffman树已建立。操作结果：将Huffman编码翻译成原文件，写入translated.txt。}ADT还需要包含调用若干库文件：stdio.h,malloc.h,string.h。18FileExtract(void)18主函数

统计字符，得出统计出的字符的权值n编码解码退出根据权值进行建立哈夫曼树输出哈夫曼树输出编码压缩编码生成二进制文件解压生成新的文本文档19主函数统计字符，采用C语言的编程方法在VC++6.0环境下实现本题目的要求。

主程序流程图

建立哈夫曼树输出哈夫曼树

输出编码根据哈夫曼树编码对编码进行压缩根据哈夫曼树解码生成二进制文件对二进制文件进行解压生成文本文档20采用C语言的编程方法在VC++6.0环境下实现本题目的要求。#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAX_SIZE1000000#definen150#definem2*n-1

typedefstruct{charch;intweight;intlchild,rchild,parent;}HuffmanTree;typedefHuffmanTreeHTree[m];

typedefstruct{charch;charbits[n+1];}HuffmanCode;typedefHuffmanCodeHCode[n];一.宏定义及节点定义压缩部分21一.宏定义及节点定义压缩部分21

由于文档限于英文文章，所以字符的ASCII码限于0~150。依次读取文档的各个字符，计算每个字符出现的次数为权值，再将数组压缩：没有出现的字符从数组中删去。返回文档出现不同字符的个数算法如下：1、统计字符出现的频率，即权值的函数intapprate(char*s,intcnt[],charstr[]);方法具体实现如下：定义两个数组，分别存放大写和小写英文字母。a.将两个数组初始化都为0.b.如果取出的字符是小写字母，则将小写字母转换为数字，每一个字符对应一个数字，同一个字符出现一次频率就加1，直到全部统计出为止，如果取出的是大写字母，方法如小写字母的实现方法。c.再将转换都的数字再转换为相应的字符，以便为下面的建树方便调用。具体代码如下：二读取原文档函数22由于文档限于英文文章，所以字符的ASCII码intFileRead(intcount[],chars[],charfilename[]){inti=0,N=0,k=0,temp[n];charc;FILE*rf;rf=fopen(filename,"r");if(rf==NULL){printf("cannotopenfile\n");exit(0);}for(i=0;i<n;i++){temp[i]=0;count[i]=0;}while(!feof(rf)){c=fgetc(rf);k=c;temp[k]++;i++;}fclose(rf);for(i=0;i<n;i++){if(temp[i]!=0){s[N]=i;count[N]=temp[i];N++;}}returnN;}//FileRead23intFileRead(intcount[],char三生成Huffman树函数

选取字符中权值最小的两个节点建树，将权值相加放在根节点中，将原节点删除，新节点放入数组。递归进行上述操作直到数组中只有一个节点为止。算法如下：2、建立哈夫曼树构造哈夫曼数时，首先将n个权值的叶子结点存放到数组huffTree[2*num]的前n个分量中，然后不断的将两棵子树合并为一棵子树，并将新子树的根结点顺序存放到数组huffTree[2*num]的前n个分量的后面。设n个叶子的权值保存在数组cnt[n]中，哈夫曼树的存储主要是利用数组存储，例如将已知字符窜s为abcdeacedaeadcedabadadaead统计出的字符频率分别为a:9,b:2,c:3,d:7,e:5则构造哈夫曼树的存储空间的初始状态最后状态如图：24三生成Huffman树函数选取字符序号字符名称weightparentlchildrchild1a90002b20003c30004d70005e50006000700080009000初始状态25序号字符名称weightparentlchildrchild序号字符名称weightparentlchildrchild1A98002B26003C36004D78005E570065723710956816941926078最后状态26序号字符名称weightparentlchildrchild

伪代码描述为:1.数组哈夫曼树HuffmanTree初始化，所有元素结点的双亲、左右孩子都置为0；2.数组哈夫曼树HuffmanTree的前n个元素的权值给定权值cnt[n]；3.进行n-1次合并c.1、在二叉树集合中选取两个权值最小的根结点，其下标分别为i1和i2；c.2、将二叉树i1和i2合并为一棵新的二叉树k27伪代码描述为:27voidCreateHuffmanTree(HTreeT,intN,intcount[],chars[]){

inti,j,p1=0,p2=0,l1,l2;for(i=0;i<2*N-1;i++){T[i].lchild=0;T[i].rchild=0;T[i].parent=0;}for(i=0;i<N;i++)

T[i].weight=count[i];for(i=N;i<2*N-1;i++){l1=l2=1000000;for(j=0;j<i;j++){if(T[j].parent==0){if(T[j].weight<l1){l1=T[j].weight,p1=j;}}}for(j=0;j<i;j++){if(T[j].parent==0){if((T[j].weight<l2)&&(j!=p1)){l2=T[j].weight,p2=j;}}}T[p1].parent=i;T[p2].parent=i;T[i].lchild=p1;T[i].rchild=p2;T[i].weight=T[p1].weight+T[p2].weight;}T[2*N-2].parent=0;}//CreateHuffmanTree28voidCreateHuffmanTree(HTreeT四求Huffman编码函数：

从叶子节点找到根节点，若该节点是双亲节点的左孩子为1，反之为0，直到根节点为止求得该节点Huffman编码的逆序列;1.、对哈夫曼树进行编码函数void Huffmancoding(element huffTree[],CodeCodeNode[],charstr[],intn) ;主要思想：规定哈夫曼编码树的左分支代表0，右分支代表1，则从根结点对应的字符的编码，称为哈夫曼编码。例如上面所举例子的哈夫曼编码构造树及哈夫曼编码29四求Huffman编码函数：292610165579233026101655792330字符频率编码a911b2010c3011d710E50031字符频率编码a911b2010c3011d710E50031

对每个叶子结点进行编码：a.1初始化编码深度为0，将孩子结点的双亲结点付给一个变量，双亲结点不为空时，深度加1，继续向上查找，这时该双亲结点已变成孩子结点，循环知道双亲结点为空，求出每一个叶子结点的深度。a.2将编码初始结点初始化为深度+1，将孩子结点的双亲结点付给一个变量，双亲结点不为空时，初始结点-1，如果此孩子为双亲的左孩子，则置为0，否则置为1，循环知道双亲结点为空。编码完毕！32对每个叶子结点进行编码：32函数C代码：voidHuffmanCoding(HTreeT,HCodeH,intN,chars[]){intc,p,i,start;charcd[n+1];cd[N+1]='\0';for(i=0;i<N;i++){H[i].ch=s[i];start=N;c=i;p=T[c].parent;while(p){if(T[p].lchild==c)cd[--start]='0';elsecd[--start]='1';c=p;p=T[p].parent;H[i].start=start;}strcpy(H[i].bits,cd);}}//HuffmanCoding33函数C代码：33五.输出解压信息函数：将求得的数据分别存放在HuffmanCode.txt、Char.txt、Weight.txt中函数C代码：voidFilePrint(HTreeT,HCodeH,intN){inti,j=0;FILE*rf,*fp,*rp;rf=fopen("HuffmanCode.txt","w");fp=fopen("Char.txt","w");rp=fopen("Weight.txt","w");while(j<N){for(i=H[j].start;i<N;i++)fprintf(rf,"%c",H[j].bits[i]);fprintf(rf,"\n");j++;}for(i=0;i<N;i++)fputc(H[i].ch,fp);for(i=0;i<N;i++)fprintf(rp,"%d\n",T[i].weight);fclose(rf);fclose(fp);fclose(rp);}//FilePrint34五.输出解压信息函数：将求得的数据分别存放在HuffmanC六.翻译成Huffman编码函数：读取原文件，将每个字符翻译成Huffman编码，以字符形式输导File.txt中。读取原文件，将每个字符翻译成Huffman编码，以字符形式输导File.txt中。函数C代码：35六.翻译成Huffman编码函数：读取原文件，将每个字符翻译voidFileWrite(HCodeH,intN,charfilename[]){inti,k,p=0;charc;FILE*rf,*fp;rf=fopen(filename,"r");fp=fopen("File.txt","w");if(rf==NULL){printf("cannotopenfile\n\n");exit(0);}while(!feof(rf)){c=fgetc(rf);for(i=0;i<N;i++){if(H[i].ch==c){for(k=H[i].start;k<N;k++){fputc(H[i].bits[k],fp)，p++;if(p==8){fprintf(fp,"");p=0;}}}

}}fclose(rf);fclose(fp);}//FileWrite36voidFileWrite(HCodeH,intN,c七.压缩函数函数读取File.txt文档，每8位子符翻译成二进制，在转化成十进制在翻译成字符，输出到Code.txt中，最后不足8位的部分不翻译，直接写入Tail.txt中，最后将中间文档File.txt删除。主要思想：主要采用二进制转换为十进制的方法进行解压处理。代码如下：37七.压缩函数函数37voidFileConvert(void){inti=0,k=0,temp=0,l;charst[10];FILE*rf,*fp,*rp;rf=fopen("File.txt","r");fp=fopen("Code.txt","wb");rp=fopen("Tail.txt","w");if(rf==NULL){printf("cannotopenfile\n\n");exit(0);}while(!feof(rf)){st[i]=fgetc(rf);switch(st[i]){case'0':k=2*k+0;i++;break;case'1':k=2*k+1;i++;break;case'':fwrite(&k,1,1,fp);temp++;k=0;i=0;break;default:fprintf(rp,"%d",temp);for(k=0;k<i;k++)fprintf(rp,"%c",st[k]);break;}}fclose(rf);fclose(fp);fclose(rp);l=remove("File.txt");}//FileConvert38voidFileConvert(void){38八压缩程序main函数部分代码如下：voidmain(){HTreeT;HCodeH;ntN;intcount[n];chars[n],filename[10];;printf("\n");printf("InputFilename\n");scanf("%s",filename);printf("\n");printf("Encoding..........\n");N=FileRead(count,s,filename);printf("CharacterIn'Char.txt'\n");printf("CharacterWeightIn'Weight.txt'\n");CreateHuffmanTree(T,N,count,s);HuffmanCoding(T,H,N,s);FilePrint(T,H,N);printf("HuffmanCodeIn'HuffmanCode.txt'\n");FileWrite(H,N,filename);FileConvert();printf("CodeFileIn'Code.txt'\n");printf("TailFileIn'Tail.txt'\n");}39八压缩程序main函数部分代码如下：39压缩部分：主要思想为：对字符窜编码的解码是将编码窜从左到右逐为判别，直到确定一个字符。这可以用生成哈夫曼的逆过程实现。从根结点开始，根据每一位的值是0还是1确定选择左分支还是右分支，直到到达一个叶子结点，然后再从根结点出发，开始下一个字符的翻译。如根据上面的（a）哈夫曼编码树对生成的(b)字符编码表进行解码，从根结点开始，由于第一位是1，所以选择右分支，下一位又是1，又选择右分支，到达叶子结点对应的字符a。再从根结点出发，下一位是0，选择左分支，再下一位是1，则选择右分支，再下一结点为0，选择左分支，到达叶子结点对应的字符c，同理，知道所有的字符都被解出伪代码如下：创建新的文本文档b、读取压缩的二进制文件：

按照编码的先后顺序进行读取编码，当文件没结束时，读取编码，从根结点开始，如果此结点有子结点，如果读取的编码为0并且是根结点的左孩子，则将此左孩子置为根结点，如果读取的编码为1并且是根结点的右孩子，则将此右孩子置为根结点，否则的话说明已经有一个字符和编码对应了,输出，再从根结点开始，重复上述过程，知道读取的文件为空，解码完毕。

c、关闭文件40压缩部分：主要思想为：40#include<stdio.h>//预处理及相关结构变量声明部分#include<string.h>#include<stdlib.h>#defineMAX_SIZE1000000#definen150#definem2*n-1typedefstruct{charch;intweight;intlchild,rchild,parent;}HuffmanTree;typedefHuffmanTreeHTree[m];typedefstruct{charch;charbits[n+1];}HuffmanCode;typedefHuffmanCodeHCode[n];41#include<stdio.h>//预处理及相关结构变量声一.读取解压信息函数：读取字符及其权值和其Huffman编码。函数C代码：{inti=0,j=0,N=0;charc,*p;charstr[MAX_SIZE];FILE*rf,*fp,*rp;rf=fopen("Char.txt","r");fp=fopen("HuffmanCode.txt","r");rp=fopen("Weight.txt","r");if(rf==NULL){printf("cannotopenfile\n");exit(0);}if(fp==NULL){printf("cannotopenfile\n");exit(0);}if(rp==NULL){printf("cannotopenfile\n");exit(0);}42一.读取解压信息函数：读取字符及其权值和其Huffman编码while(!feof(rf)){H[N].ch=fgetc(rf);T[N].ch=H[N].ch;N++;}while(!feof(fp)){c=fgetc(fp);switch(c){case'\n':i++;j=0;break;default:H[i].bits[j]=c;j++;H[i].bits[j]='\0';break;}}for(i=0;i<N;i++)T[i].weight=0;i=0;j=0;while(!feof(rp)){c=fgetc(rp);switch(c){case'\n':for(p=str;*p!='\0';p++)T[i].weight=T[i].weight*10+*p-48;i++;j=0;break;default:str[j]=c;j++;str[j]='\0';break;}}fclose(rf);fclose(fp);fclose(rp);returnN-1;}//FileRead43while(!feof(rf))43二翻译为Huffman编译文档函数：将Code.txt重新翻译成二进制，在以字符形式输入到File00.txt中，再将Tail.txt中的最后编码复制到File.txt的最后。函数C代码：intFileExtract(void){inti,j=0,k=0,t,temp=0;unsignedcharc;chars[8];FILE*rf,*fp,*rp;rf=fopen("Tail.txt","r");fp=fopen("File00.txt","w");rp=fopen("File00.txt","a");if(rf==NULL){printf("cannotopenfile\n");exit(0);}fscanf(rf,"%d%s",&temp,s);fclose(rf);rf=fopen("Code.txt","rb");if(rf==NULL){printf("cannotopenfile\n");exit(0);}44二翻译为Huffman编译文档函数：将Code.txt重新翻while(j<temp){j++;c=fgetc(rf);for(i=7;i>=0;i--){t=c;t>>=i;t&=1;if(k==0&&t==1)k=1;if(k==1)fprintf(fp,"%d",t);}fprintf