哈夫曼编码教材课件.ppt

1,路 径：路径长度：树的路径长度：带权路径长度：树的带权路径长度：霍 夫 曼 树：,Huffman树及其应用,一、最优二叉树（霍夫曼树）,由一结点到另一结点间的分支所构成,路径上的分支数目,从树根到每一结点的路径长度之和。,结点到根的路径长度与结点上权的乘积,预备知识：若干术语,树中所有叶子结点的带权路径长度之和,带权路径长度最小的树。,ae的路径长度,树长度,2,10,2,Huffman树简介：,树的带权路径长度如何计算？,经典之例：,WPL=36,WPL=46,WPL= 35,哈夫曼树则是：WPL 最小的树。,Huffman树,Weighted Path Length,3,(1) 由给定的 n 个权值w0, w1, w2, , wn-1，构造具有 n 棵扩充二叉树的森林F = T0, T1, T2, , Tn-1 ，其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 F 中删去这两棵二叉树。 把新的二叉树加入 F。,构造霍夫曼树的基本思想：,构造Huffman树的步骤（即Huffman算法）：,权值大的结点用短路径，权值小的结点用长路径。,先举例！,4,例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树！,5,操作要点1：对权值的合并、删除与替换在权值集合7,5,2,4中，总是合并当前值最小的两个权,构造Huffman树的步骤：,注：方框表示外结点（叶子，字符对应的权值）， 圆框表示内结点（合并后的权值）。,6,操作要点2：按左0右1对Huffman树的所有分支编号！,Huffman编码结果：d=0, i=10, a=110, n=111WPL=1bit72bit5+3bit(2+4)=35,特点：每一码都不是另一码的前缀，绝不会错译! 称为前缀码,将 Huffman树 与 Huffman编码 挂钩,7,例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个字母设计哈夫曼编码。如果用07的二进制编码方案又如何？,霍夫曼编码的基本思想是：概率大的字符用短码，概率小的用长码。由于霍夫曼树的WPL最小，说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。,解：先将概率放大100倍，以方便构造哈夫曼树。权值集合 w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。,8,w4=19, 21, 28, 32,为清晰起见，重新排序为:w=2, 3, 6, 7, 10, 19, 21, 32,5,6,w1=5, 6, 7, 10, 19, 21, 32,w2=7, 10, 11, 19, 21, 32,w3=11, 17, 19, 21, 32,11,17,28,w5=28,32,40,w6=40,60,w7=100,哈夫曼树,9,对应的哈夫曼编码（左0右1）：,Huffman码的WPL2(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,WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3,二进制码,10,另一种结果表示：,11,例3：设字符集为26个英文字母，其出现频度如下表所示。,先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。,要求编程实现：,12,提示1：霍夫曼树中各结点的结构可以定义为如下5个分量：,将整个霍夫曼树的结点存储在一个数组中：HT1.n; 将结点的编码存储在HC1.n中。,提示3：霍夫曼树如何构造？构造好之后又如何求得各结点对应的霍夫曼编码？,提示2：霍夫曼树的存储结构可采用顺序存储结构：,13,需求分析,1.写一个对txt文件压缩和解压的程序，使用动态编码。2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树；3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。,应用：压缩程序 哈弗曼编码算法,14,概要分析,采用顺序表实现对Huffman树的存储 /-Huffman树存储结构-typedef struct int weight; int lchild, rchild, parent;HuffmanTree;typedef HuffmanTree HTreem;weight域存有该节点字符的权值，lchild、rchild、parent分别存放该节点的左孩子、右孩子和双亲节点在顺序表中的位置。,15,采用顺序表实现对Huffman编码的存储 /-Huffman编码存储结构-typedef struct char ch; int start; char bitsn+1;HuffmanCode;typedef HuffmanCode HCoden;ch存放对应的字符，start存放Huffman编码在字符数组bits中开始的位置。,16,抽象数据,抽象数据类型定义：ADT 数据对象：txt文档基本操作：FileRead(int count,char s,char filename)初始条件：压缩文档存在。操作结果：对该文档进行读取，求其所有出现的字符和字符的权值。CreateHuffmanTree(HTree T,int N,int count,char s)初始条件：以求得该文档的字符和权值。操作结果：建立Huffman树。HuffmanCoding(HTree T,HCode H,int N,char s)初始条件：Huffman树。操作结果：求各个字符的Huffman编码。,17,FilePrint(HTree T,HCode H,int N)初始条件：求得Huffman编码以及 各节点的权值。操作结果：将求得的数据分别存放在HuffmanCode.txt、Char.txt、Weight.txt中。FileWrite(HCode H,int N,char filename)初始条件：求得Huffman编码以及 各节点的权值。操作结果：将文档翻译成Huffman编码以字符形式存放在File.txt中。FileConvert(void)初始条件：File.txt存在。操作结果：将字符形式的Huffman编码翻译成二进制形式，每首季8比特就通过位操作合并成一个字节写入文件code.txt中，最后不足8 位时将最后的几位存放在Tail.txt中。FileRead(HTree T,HCode H)初始条件：压缩生成的HuffmanCode.txt、Char.txt、Weight.txt存在。操作结果：读取字符及其权值和其Huffman编码。,18,FileExtract(void)初始条件：压缩结果文件Code.txt和tail.txt存在。操作结果： 将code.txt和tail.txt中的字符写成编码的二进制字符形式，写进file00.txt。FileTrans(HTree T,HCode H,int N)初始条件： 已生成File00,txt并已求得各个字符的Huffman编码，Huffman树已建立。操作结果：将Huffman编码翻译成原文件，写入translated.txt。ADT还需要包含调用若干库文件：stdio.h, malloc.h, string.h。,19,20,采用C语言的编程方法在VC+6.0环境下实现本题目的要求。主程序流程图,21,#include#include#include#define MAX_SIZE 1000000#define n 150#define m 2*n-1 typedef struct char ch; int weight; int lchild,rchild,parent;HuffmanTree;typedef HuffmanTree HTreem; typedef struct char ch; char bitsn+1;HuffmanCode;typedef HuffmanCode HCoden;,一.宏定义及节点定义,压缩部分,22,由于文档限于英文文章，所以字符的ASC II码限于0150。依次读取文档的各个字符，计算每个字符出现的次数为权值，再将数组压缩：没有出现的字符从数组中删去。返回文档出现不同字符的个数算法如下：1、统计字符出现的频率，即权值的函数int apprate(char *s,int cnt,char str);方法具体实现如下：定义两个数组，分别存放大写和小写英文字母。a. 将两个数组初始化都为0.b. 如果取出的字符是小写字母，则将小写字母转换为数字，每一个字符对应一个数字，同一个字符出现一次频率就加1，直到全部统计出为止，如果取出的是大写字母，方法如小写字母的实现方法。c. 再将转换都的数字再转换为相应的字符，以便为下面的建树方便调用。 具体代码如下：,二 读取原文档函数,23,int FileRead(int count,char s,char filename) int i=0,N=0,k=0,tempn; char c; FILE *rf; rf=fopen(filename,r); if (rf=NULL) printf(cannot open filen); exit(0); for (i=0;in;i+) tempi=0; counti=0; while (!feof(rf) c=fgetc(rf); k=c; tempk+; i+; fclose(rf); for (i=0;in;i+) if (tempi!=0) sN=i; countN=tempi; N+; return N;/FileRead,24,三 生成Huffman树函数,选取字符中权值最小的两个节点建树，将权值相加放在根节点中，将原节点删除，新节点放入数组。递归进行上述操作直到数组中只有一个节点为止。算法如下：2、建立哈夫曼树构造哈夫曼数时，首先将n个权值的叶子结点存放到数组huffTree2*num的前n个分量中，然后不断的将两棵子树合并为一棵子树，并将新子树的根结点顺序存放到数组huffTree2*num的前n个分量的后面。设n个叶子的权值保存在数组cntn中，哈夫曼树的存储主要是利用数组存储，例如将已知字符窜s为abcdeacedaeadcedabadadaead统计出的字符频率分别为a:9,b:2,c:3,d:7,e:5则构造哈夫曼树的存储空间的初始状态最后状态如图：,25,26,27,伪代码描述为:1. 数组哈夫曼树HuffmanTree初始化，所有元素结点的双亲、左右孩子都置为0；2. 数组哈夫曼树HuffmanTree的前n个元素的权值给定权值cntn；3. 进行n-1次合并c.1、在二叉树集合中选取两个权值最小的根结点，其下标分别为i1和i2；c.2、将二叉树i1和i2合并为一棵新的二叉树k,28,void CreateHuffmanTree(HTree T,int N,int count,char s) int i,j,p1=0,p2=0,l1,l2; for (i=0;i2*N-1;i+) Ti.lchild=0; Ti.rchild=0; Ti.parent=0; for (i=0;iN;i+) Ti.weight=counti; for (i=N;i2*N-1;i+) l1=l2=1000000; for (j=0;ji;j+) if (Tj.parent=0) if (Tj.weightl1) l1=Tj.weight, p1=j; for (j=0;ji;j+) if (Tj.parent=0) if (Tj.weightl2)/ CreateHuffmanTree,29,四 求Huffman编码函数：,从叶子节点找到根节点，若该节点是双亲节点的左孩子为1，反之为0，直到根节点为止求得该节点Huffman编码的逆序列;1.、对哈夫曼树进行编码函数voidHuffmancoding(element huffTree,Code CodeNode,char str,int n);主要思想：规定哈夫曼编码树的左分支代表0，右分支代表1，则从根结点对应的字符的编码，称为哈夫曼编码。例如上面所举例子的哈夫曼编码构造树及哈夫曼编码,30,31,32,对每个叶子结点进行编码：a.1初始化编码深度为0，将孩子结点的双亲结点付给一个变量，双亲结点不为空时，深度加1，继续向上查找，这时该双亲结点已变成孩子结点，循环知道双亲结点为空，求出每一个叶子结点的深度。a.2将编码初始结点初始化为深度+1，将孩子结点的双亲结点付给一个变量，双亲结点不为空时，初始结点-1，如果此孩子为双亲的左孩子，则置为0，否则置为1，循环知道双亲结点为空。编码完毕！,33,函数C代码：void HuffmanCoding(HTree T,HCode H,int N,char s)int c,p,i,start;char cdn+1;cdN+1=0;for (i=0;iN;i+) Hi.ch=si; start=N; c=i; p=Tc.parent; while (p) if (Tp.lchild=c) cd-start=0; else cd-start=1; c=p; p=Tp.parent; Hi.start=start; strcpy(Hi.bits,cd); / HuffmanCoding,34,五.输出解压信息函数：,将求得的数据分别存放在HuffmanCode.txt、Char.txt、Weight.txt中函数C代码：void FilePrint(HTree T,HCode H,int N)int i,j=0;FILE *rf,*fp,*rp;rf=fopen(HuffmanCode.txt,w);fp=fopen(Char.txt,w);rp=fopen(Weight.txt,w);while (jN) for (i=Hj.start;iN;i+) fprintf(rf,%c,Hj.bitsi); fprintf(rf,n); j+; for (i=0;iN;i+) fputc(Hi.ch,fp);for (i=0;iN;i+) fprintf(rp,%dn,Ti.weight);fclose(rf);fclose(fp);fclose(rp);/ FilePrint,35,六.翻译成Huffman编码函数：,读取原文件，将每个字符翻译成Huffman编码，以字符形式输导File.txt中。读取原文件，将每个字符翻译成Huffman编码，以字符形式输导File.txt中。函数C代码：,36,void FileWrite(HCode H,int N,char filename)int i,k,p=0;char c;FILE *rf,*fp;rf=fopen(filename,r);fp=fopen(File.txt,w);if (rf=NULL) printf( cannot open filenn ); exit(0);while (!feof(rf) c=fgetc(rf); for (i=0;iN;i+) if (Hi.ch=c) for (k=Hi.start;kN;k+) fputc(Hi.bitsk,fp)，p+; if (p=8) fprintf(fp, ); p=0; fclose(rf);fclose(fp);/ FileWrite,37,七.压缩函数函数,读取File.txt文档，每8位子符翻译成二进制，在转化成十进制在翻译成字符，输出到Code.txt中，最后不足8位的部分不翻译，直接写入Tail.txt中，最后将中间文档File.txt删除。主要思想：主要采用二进制转换为十进制的方法进行解压处理。代码如下：,38,void FileConvert(void)int i=0,k=0,temp=0,l;char st10;FILE *rf,*fp,*rp;rf=fopen(File.txt,r);fp=fopen(Code.txt,wb);rp=fopen(Tail.txt,w);if (rf=NULL) printf( cannot open filenn ); exit(0); while (!feof(rf) sti=fgetc(rf); switch(sti) case0: k=2*k+0; i+;break; case1: k=2*k+1; i+;break; case : fwrite(/ FileConvert,39,八 压缩程序main函数部分,代码如下：void main()HTree T;HCode H;nt N;int countn;char sn,filename10;printf(n);printf(Input Filenamen);scanf(%s,filename);printf(n);printf(Encoding.n);N=FileRead(count,s,filename);printf(CharacterIn Char.txtn);printf(CharacterWeight In Weight.txtn);CreateHuffmanTree(T,N,count,s);HuffmanCoding(T,H,N,s);FilePrint(T,H,N);printf(Huffman Code In HuffmanCode.txtn);FileWrite(H,N,filename);FileConvert();printf(Code File In Code.txtn);printf(Tail File In Tail.txtn);,40,压缩部分：,主要思想为：对字符窜编码的解码是将编码窜从左到右逐为判别，直到确定一个字符。这可以用生成哈夫曼的逆过程实现。从根结点开始，根据每一位的值是0还是1确定选择左分支还是右分支，直到到达一个叶子结点，然后再从根结点出发，开始下一个字符的翻译。如根据上面的（a）哈夫曼编码树对生成的(b)字符编码表进行解码，从根结点开始，由于第一位是1，所以选择右分支，下一位又是1，又选择右分支，到达叶子结点对应的字符a。再从根结点出发，下一位是0，选择左分支，再下一位是1，则选择右分支，再下一结点为0，选择左分支，到达叶子结点对应的字符c，同理，知道所有的字符都被解出伪代码如下：创建新的文本文档b、 读取压缩的二进制文件： 按照编码的先后顺序进行读取编码，当文件没结束时，读取编码，从根结点开始，如果此结点有子结点，如果读取的编码为0并且是根结点的左孩子，则将此左孩子置为根结点，如果读取的编码为1并且是根结点的右孩子，则将此右孩子置为根结点，否则的话说明已经有一个字符和编码对应了,输出，再从根结点开始，重复上述过程，知道读取的文件为空，解码完毕。 c、 关闭文件,41,#include/预处理及相关结构变量声明部分#include#include#define MAX_SIZE 1000000#define n 150#define m 2*n-1typedef struct char ch; int weight; int lchild,rchild,parent;HuffmanTree;typedef HuffmanTree HTreem;typedef struct char ch; char bitsn+1;HuffmanCode;typedef HuffmanCode HCoden;,42,一.读取解压信息函数：,读取字符及其权值和其Huffman编码。函数C代码： int i=0,j=0,N=0; char c,*p; char strMAX_SIZE; FILE *rf,*fp,*rp; rf=fopen(Char.txt,r); fp=fopen(HuffmanCode.txt,r); rp=fopen(Weight.txt,r); if (rf=NULL) printf(cannot open filen); exit(0); if (fp=NULL) printf(cannot open filen); exit(0); if (rp=NULL) printf(cannot open filen); exit(0); ,43,while (!feof(rf) HN.ch=fgetc(rf); TN.ch=HN.ch; N+; while (!feof(fp) c=fgetc(fp); switch(c) casen: i+; j=0;break; default: Hi.bitsj=c; j+; Hi.bitsj=0;break; for (i=0;iN;i+) Ti.weight=0; i=0; j=0; while (!feof(rp) c=fgetc(rp); switch(c) casen: for (p=str;*p!=0;p+) Ti.weight=Ti.weight*10+*p-48; i+; j=0;break; default: strj=c; j+; strj=0;break; fclose(rf); fclose(fp); fclose(rp); return N-1;/ FileRead,44,二翻译为Huffman编译文档函数：,将Code.txt重新翻译成二进制，在以字符形式输入到File00.txt中，再将Tail.txt中的最后编码复制到File.txt的最后。函数C代码：int FileExtract(void) int i,j=0,k=0,t,temp=0; unsigned char c; char s8; FILE *rf,*fp,*rp; rf=fopen(Tail.txt,r); fp=fopen(File00.txt,w); rp=fopen(File00.txt,a); if (rf=NULL) printf(cannot open filen); exit(0); fscanf(rf,%d %s, ,45,while (j=0;i-) t=c; t=i; t/ FileExtract,46,三.翻译Huffman编译文档函数：,读取二进制文档，从根节点开始找叶子节点，遇到1找左节点，遇到0找右节点，直到为叶子节点为止，输出叶子节点的字符，最后删除中间文件File00.txt。函数C代码：float FileTrans(HTree T,HCode H,int N) int i=2*N-2,l; float temp=0.0; char c; FILE *rf,*fp; rf=fopen(File00.txt,r); fp=fopen(Translated File.txt,w); if (rf=NULL) printf(cannot open filen); exit(0); while(!feof(rf) c=fgetc(rf);,47,if (Ti.lchild|Ti.rchild) if (c=0) i=Ti.lchild; else if (c=1) i=Ti.rchild; else fputc(Ti.ch,fp); temp+; i=2*N-2; if (c=0) i=Ti.lchild; else if (c=1) i=Ti.rchild; fclose(rf); fclose(fp); l=remove(File00.txt); return temp;/ FileTrans,48,四.解压程序main函数部分,void main() HTree T; HCode H; int N,temp01; float temp02; N=FileRead(T,H); printf(decoding.n); CreateHuffmanTree(T,N); temp01=FileExtract(); temp02=FileTrans(T,H,N); printf(Translated File In Translated File.txtn)； printf(percent=%6f%n ,temp01/temp02*100); ,49,五.数据测试,测试用例：sample.txt,50,输入测试文件名,51,运行完毕处理结果如下：该文本文件保存的是测试文件中出现的字符以及相应的权值,52,53,对应字符哈夫曼编码,54,编码压缩以后保存在code文本文件里,55,解压测试,56,根据huffman编码解压后的结果保存在Translated File.txt里面,