哈夫曼编码压缩解压缩.pdf

《哈夫曼编码压缩解压缩.pdf》由会员分享，可在线阅读，更多相关《哈夫曼编码压缩解压缩.pdf（33页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、哈夫曼编码压缩解压缩哈夫曼编码压缩解压缩xx 学院课程设计题目 哈夫曼编码压缩解压缩院系名称计算机科学与技术系专 业 （班 级）姓 名 （学 号）指 导 教 师完 成 时 间1哈夫曼编码实现文本文件的压缩和解压缩 一、 任务分析和定义在了解哈夫曼编码压缩解压缩原理之前，首先让我们来认识哈夫曼树和哈夫曼编码。1 在了解哈夫曼编码压缩解压缩原理之前，首先让我们来认识哈夫曼树。哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。2 在文本文件中多采用二进制编码。为了使文件尽可能的缩短, 可以对文件中每个字符出现的次数进行统计。设法让出现次数多的字符二进制码短些, 而让那些很少出现的字符二进制码长一些

2、。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。哈夫曼树中的左右分支各代表0和1，则从根节点到叶子节点所经历的路径分支上的0或1组成的字符串，为该节点对应字符的哈夫曼编码。3 统计字符集中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的结点，路径越短。哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。 4

3、哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行解压缩。 总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其中字符出现的频率，以其为权值构建哈夫曼树。其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，此外还要存储相应的哈夫曼编码，为解压缩做准备。二、概要设计和数据结构的选择以下是在任务分析及对题意的理解做出的概要设计和对数据结构的选择。 1数据结构定义：struct headunsigned char b; /记录字符在数组中的位置long count; /字符

4、出现频率（权值）long parent,lch,rch; /定义哈夫曼树指针变量char bits256; /定义存储哈夫曼编码的数组 header512,tmp;2定义所需要的子函数：void compress() /用于实现文件的压缩功能void uncompress() /用于实现文件的解压缩功能 3主程序的流程及程序模块间的关系：主函数实现菜单工具栏，并且能够对用户的输入进行容错处理，通过 if 语句实现该工具的两个子功能：即：a. 调用压缩子函数压缩同文件夹下的字符型文本文件b. 调用解压缩子函数解压缩同文件夹下的字符型文本文件 并可在完成相应功能后安全退出2压缩或解压缩的文件在同文

5、件夹下生成4. 流程图：主函数压缩函数 compress 解压缩函数菜 单 uncompress退出图 1. 程序模块打开文本文件，统计文件长度初始化结点根据权值大小结点排序选择最小权值两个结点Parent=-1Parent!=-1 构建哈夫曼树计算左右分支权值大小，进行无重复前缀编码哈夫曼编码位操作压缩存储NO 压缩文件成功!YES 压缩文件失败!压缩率为 %图 2. 压缩函数3打开压缩文件读取原文件长度进行文件定位根据哈夫曼编码的长短，对结点进行排序通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储在单字节内对相应位置补 0YESNOYES解压缩文件成功!解压缩文件失败!对解压缩

6、后文件和原文件相同性比较进行判断图 3. 解压缩函数二、 详细设计和编码以下是主函数和子函数的详细设计和附部分源代码。1 压缩（compress）子函数设计该函数主要是为了实现对同文件夹下文本文件的压缩。 11 算法中先是统计文件中字符重复出现的频率和文件的长度。字符出现的频率用作结点的权值，而原文件长度用作求压缩率的分母。12 然后对结点进行初始化，根据频率（权值）大小，对结点进行排序，依次选择权值较小且 parent 域不等于-1 的结点建哈夫曼树。计算左右孩子权值大小，与后续进入树的结点权值进行比较，从而确定后续结点在树中的位置。13 进行哈夫曼无重复前缀编码，再对哈夫曼编码进行位操作从

7、原先的按字节存储到现在的按位存储实现字符存储空间的压缩。假设原文件第一个字符是“A”，8 位 2进制为 01000001，编码后为 0110 识别编码第一个0，那么我们就可以将其左移一位，看起来没什么变化。下一个是1，应该|1，结果 00000001， 同理 4 位都做完，应该是00000110，由于字节中的 8 位并没有全部用完，我们应该继续读下一个字符，根据编码表继续拼完剩下的 4 位，如果字符的编码不足 4 位，还要继续读一个字符，如果字符编码超过 4 位，那么我们将把剩下4的位信息拼接到一个新的字节里。其中编码后压缩字符存储空间从字节到位代码实现如下：for(i=0;in;i+)fwr

8、ite(&(headeri.b),1,1,ofp);c=strlen(headeri.bits);fwrite(&c,1,1,ofp);j=strlen(headeri.bits);if(j%8!=0) /若存储的位数不是 8 的倍数，则补 0for(f=j%8;f8;f+)strcat(headeri.bits,0);while(headeri.bits0!=0)c=0;for(j=0;j8;j+) /字符的有效存储不超过 8 位，则对有效位数左移实现两字符编码的连接if(headeri.bitsj=1) c=(c1)|1; /|1 不改变原位置上的“0”“1”值else c=c1;strc

9、py(headeri.bits,headeri.bits+8); /把字符的编码按原先存储顺序连接fwrite(&c,1,1,ofp);14 统计压缩了的文件长度与原文件长度作比，计算压缩率。 2 解压缩（uncompress）子函数设计该函数主要是为了实现对同文件夹下压缩文件的解压缩。 21 压缩执行程序，完成后输出压缩的结果，并且保留压缩后的二进制代码和哈夫曼编码为解压缩做准备；在执行解压缩时，首先调用压缩所产生的二进制代码和哈夫曼编码，以出现的字符为叶子节点，以字符出现的频率为权值构建新的哈夫曼树，它的输出结果就是解压缩后的文件。其中解码过程如下：while(1) /通过哈夫曼编码的长短

10、，依次解码，从原来的位存储还原到字节存储while(strlen(bx)f;l-) /在单字节内对相应位置补 05strcat(bx,0);strcat(bx,buf);for(i=0;i=8)for(i=0;i8;i+)if(bufi=1) c=(c1)|1;else c=c1;fwrite(&c,1,1,ofp);pt1+; /统计压缩后文件的长度strcpy(buf,buf+8);j=strlen(buf);2文件压缩存储的实现，在建好哈夫曼树对文件字符编过码以后，我们要做的就是如何存储这些编码，从而实现文件的压缩存储。我们知道原文件中的字符是以 ASCII码形式二进制“0”“1”按字节

11、存储，例如：英文字母大 A 的 ASCII 码值是 65，小 b 是98，它们在计算机中存储为 01000001 和 01100010，存储两个字符需要两个字节，如果按哈夫曼编码存储，由于小 b 可能在原字符型文本文件中出现频率较高，它的哈夫曼编码是 110，大A 是 11101，小 b 占 3 位，大 A 占 5 位，这时，两个字符就可以存储在一个字节中，在字符存储位置不变7的情况下，节省了存储空间，实现了文件的压缩。在上机调试的过程中，这一块出现的问题最多，实现的过程也最难理解，后在查阅相关资料以及老师的指教下，最终达到了预期的目的。3解压缩文件和原文件相似性功能的比较，这里开始我有两个思

12、路，一是逐字符比较解压缩文件和原文件的相似性，二是统计解压缩文件长度和原文件长度进行比较，若大小完全相等，则解压缩文件和原文件相同，否则不同。 while(1)while(strlen(bx)f;l-)strcat(bx,0);strcat(bx,buf);for(i=0;in;i+)if(memcmp(headeri.bits,bx,headeri.count)=0) break;strcpy(bx,bx+headeri.count);c=headeri.b;fwrite(&c,1,1,ofp);m+; /统计解压缩后文件的长度if(m=flength) break; /flength 是原

13、文件长度fclose(ifp);fclose(ofp);printf(nt 解压缩文件成功!n);if(m=flength) /对解压缩后文件和原文件相同性比较进行判断（根据文件大小）printf(t 解压缩文件与原文件相同!nn); else printf(t 解压缩文件与原文件不同!nn); 五、用户使用说明尊敬的用户：感谢您使用 *压缩、解压缩 小工具* ，本工具为您提供了一个快捷易用的压缩解压缩文本文件的工具，在使用前请仔细阅读以下说明文档，以快速了解本工具的使用方法。如果您发现工具存在 BUG 或者您有任何改进意见请与作者联系，欢迎指教。进入可执行文件 *压缩、解压缩 小工具* 菜单

14、栏，有三个选项：81.压缩2.解压缩0.退出表 1. 菜单栏选项 在“*请选择相应功能(0-2):”光标处输入相应数字选择功能，如果超出数字范围，会提示用户继续输入，直到用户输入功能对应的数字为止。 a. 输入数字“1”，选择“压缩”功能，在“请您输入需要压缩的文件：”光标处输入您要压缩的文件包括其扩展名（以字符型文本文件为宜），此时注意需要压缩的文件应和该可执行文件在同一文件夹下，否则提示“文件打开失败!”。单击回车，提示用户“请您输入压缩后的文件名：”，不需要输入其扩展名。等待一段时间以后（适文件大小而定），屏幕提示“压缩文件成功!”和文件的压缩率或者提示“文件压缩失败!”。b. 输入数字

15、“2”，选择“解压缩”功能，在“请您输入需要解压缩的文件：”光标处输入您要解压缩的文件，不需要输入其扩展名，单击回车，提示用户“请您输入解压缩后的文件名：”，需要输入其扩展名。等待一段时间以后（适文件大小而定），屏幕提示“解压缩文件成功!”或者提示“文件解压缩失败!”。 c. 输入数字“0”，选择“退出”，安全推出该工具六、测试结果压缩：图 5. 压缩文件界面 图中 bb.hub 是压缩 aa.txt 生成的文件9图 6. 压缩文件生成原文件 aa.txt 大小是 6.38KB（6538 字节）图 7. 原文件大小压缩文件 bb.hub 大小是 3.89KB（3991 字节）10图 8. 压缩

16、文件大小解压缩：图 9. 解压缩文件界面11图 10. 解压缩文件生成aa.txt 文件内容图 11. 原文件内容cc.txt 文件内容（进行相似性比较可知解压缩文件 cc.txt 与原文件 aa.txt 完全相同）12图 12. 解压缩文件内容七、附录/哈夫曼编码压缩解压缩程序.cpp 2007.6.19#include #include #include #include struct headunsigned char b; /记录字符在数组中的位置long count; /字符出现频率（权值）long parent,lch,rch; /定义哈夫曼树指针变量char bits256; /

17、定义存储哈夫曼编码的数组 header512,tmp;/*压缩*/void compress()char filename255,outputfile255,buf512;unsigned char c;long i,j,m,n,f;long min1,pt1,flength,length1,length2;double div;13FILE *ifp,*ofp;printf(t 请您输入需要压缩的文件：);gets(filename);ifp=fopen(filename,rb);if(ifp=NULL)printf(nt 文件打开失败!nn);return;printf(t 请您输入压缩后

18、的文件名：);gets(outputfile);ofp=fopen(strcat(outputfile,.hub),wb);if(ofp=NULL)printf(nt 压缩文件失败!nn);return;flength=0;while(!feof(ifp)fread(&c,1,1,ifp);headerc.count+; /字符重复出现频率+1flength+; /字符出现原文件长度+1flength-;length1=flength; /原文件长度用作求压缩率的分母headerc.count-;for(i=0;i512;i+)if(headeri.count!=0) headeri.b=(u

19、nsigned char)i;/*将每个哈夫曼码值及其对应的 ASCII 码存放在一维数组 headeri中，且编码表中的下标和 ASCII 码满足顺序存放关系*/else headeri.b=0;headeri.parent=-1;headeri.lch=headeri.rch=-1; /对结点进行初始化for(i=0;i256;i+) /根据频率（权值）大小，对结点进行排序，选择较小的结点进树for(j=i+1;j256;j+)if(headeri.countheaderj.count)tmp=headeri;headeri=headerj;headerj=tmp;14for(i=0;i2

20、56;i+) if(headeri.count=0) break;n=i; /外部叶子结点数为 n 个时，内部结点数为 n-1，整个哈夫曼树的需要的结点数为 2*n-1.m=2*n-1;for(i=n;im;i+) /构建哈夫曼树min1=999999999; /预设的最大权值，即结点出现的最大次数for(j=0;jheaderj.count)pt1=j;min1=headerj.count;continue;headeri.count=headerpt1.count;headerpt1.parent=i; /依据 parent 域值（结点层数）确定树中结点之间的关系headeri.lch=p

21、t1; /计算左分支权值大小min1=999999999;for(j=0;jheaderj.count)pt1=j;min1=headerj.count;continue;headeri.count+=headerpt1.count;headeri.rch=pt1; /计算右分支权值大小headerpt1.parent=i;for(i=0;in;i+) /哈夫曼无重复前缀编码f=i;headeri.bits0=0; /根结点编码 0while(headerf.parent!=-1)15j=f;f=headerf.parent;if(headerf.lch=j) /置左分支编码 0j=strle

22、n(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);/依次存储连接“0”“1”编码headeri.bits0=0;else /置右分支编码 1j=strlen(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);headeri.bits0=1;fseek(ifp,0,SEEK_SET); /从文件开始位置向前移动 0 字节，即定位到文件开始位置fwrite(&flength,sizeof(int),1,ofp);/*用来将数据写入文件流中，参数 flength 指向欲写入的数

23、据地址，总共写入的字符数以参数 size*int 来决定，返回实际写入的 int 数目 1*/fseek(ofp,8,SEEK_SET);buf0=0; /定义缓冲区,它的二进制表示 00000000f=0;pt1=8;/*假设原文件第一个字符是A，8 位 2 进制为 01000001，编码后为 0110 识别编码第一个0，那么我们就可以将其左移一位，看起来没什么变化。下一个是1，应该|1，结果 00000001同理 4 位都做完，应该是 00000110，由于字节中的 8 位并没有全部用完，我们应该继续读下一个字符，根据编码表继续拼完剩下的 4 位，如果字符的编码不足 4 位，还要继续读一个

24、字符，如果字符编码超过 4 位，那么我们将把剩下的位信息拼接到一个新的字节里*/while(!feof(ifp)c=fgetc(ifp);f+;for(i=0;i=8) /对哈夫曼编码位操作进行压缩存储for(i=0;i8;i+)if(bufi=1) c=(c1)|1;else c=c0) /对哈夫曼编码位操作进行压缩存储strcat(buf,00000000);for(i=0;i8;i+)if(bufi=1) c=(c1)|1;else c=c1;fwrite(&c,1,1,ofp);pt1+;fseek(ofp,4,SEEK_SET);fwrite(&pt1,sizeof(long),1,

25、ofp);fseek(ofp,pt1,SEEK_SET);fwrite(&n,sizeof(long),1,ofp);for(i=0;in;i+)fwrite(&(headeri.b),1,1,ofp);c=strlen(headeri.bits);fwrite(&c,1,1,ofp);j=strlen(headeri.bits);if(j%8!=0) /若存储的位数不是 8 的倍数，则补 0for(f=j%8;f8;f+)strcat(headeri.bits,0);while(headeri.bits0!=0)c=0;for(j=0;j8;j+) /字符的有效存储不超过 8 位，则对有效位

26、数左移实现两字17符编码的连接if(headeri.bitsj=1) c=(c1)|1; /|1 不改变原位置上的“0”“1”值else c=c1;strcpy(headeri.bits,headeri.bits+8); /把字符的编码按原先存储顺序连接fwrite(&c,1,1,ofp);length2=pt1-;div=(double)length1-(double)length2)/(double)length1; /计算文件的压缩率fclose(ifp);fclose(ofp);printf(nt 压缩文件成功!n);printf(t 压缩率为 %f%nn,div*100);retur

27、n;/*解压缩*/void uncompress()char filename255,outputfile255,buf255,bx255;unsigned char c;long i,j,m,n,f,p,l;long flength;FILE *ifp,*ofp;printf(t 请您输入需要解压缩的文件：);gets(filename);ifp=fopen(strcat(filename,.hub),rb);if(ifp=NULL)printf(nt 文件打开失败!n);return;printf(t 请您输入解压缩后的文件名：);gets(outputfile);ofp=fopen(ou

28、tputfile,wb);if(ofp=NULL)printf(nt 解压缩文件失败!n);return;fread(&flength,sizeof(long),1,ifp); /读取原文件长度，对文件进行定位fread(&f,sizeof(long),1,ifp);fseek(ifp,f,SEEK_SET);18fread(&n,sizeof(long),1,ifp);for(i=0;i0) m=p/8+1;else m=p/8;for(j=0;jf;l-)strcat(headeri.bits,0);strcat(headeri.bits,buf);headeri.bitsp=0;for(

29、i=0;in;i+) /根据哈夫曼编码的长短，对结点进行排序for(j=i+1;jstrlen(headerj.bits)tmp=headeri;headeri=headerj;headerj=tmp;p=strlen(headern-1.bits);fseek(ifp,8,SEEK_SET);m=0;bx0=0;while(1) /通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储while(strlen(bx)f;l-) /在单字节内对相应位置补 0strcat(bx,0);strcat(bx,buf);for(i=0;in;i+)if(memcmp(headeri.bits,b

30、x,headeri.count)=0) break;strcpy(bx,bx+headeri.count); /*从压缩文件中的按位存储还原到按字节存储字符，字符位置不改变*/c=headeri.b;fwrite(&c,1,1,ofp);m+; /统计解压缩后文件的长度if(m=flength) break; /flength 是原文件长度fclose(ifp);fclose(ofp);printf(nt 解压缩文件成功!n);if(m=flength) /对解压缩后文件和原文件相同性比较进行判断（根据文件大小）printf(t 解压缩文件与原文件相同!nn);else printf(t 解压

31、缩文件与原文件不同!nn);return;/*主函数*/int main()int c;while(1) /菜单工具栏printf(t _n);printf(n);printf(t * 压缩、解压缩 小工具 * n);printf(t _n);printf(t _n);printf(t| |n);printf(t| 1.压缩 |n);20printf(t| 2.解压缩 |n);printf(t| 0.退出 |n);printf(t|_|n);printf(n);printf(t 说明：（1）采用哈夫曼编码n);printf(t （2）适用于字符型文本文件n);printf(n);do /对用户

32、输入进行容错处理printf(nt*请选择相应功能(0-2):);c=getch();printf(%cn,c);if(c!=0 & c!=1 & c!=2)printf(t_请检查您输入的数字在 02 之间！n);printf(t 请再输入一遍！n);while(c!=0 & c!=1 & c!=2);if(c=1) compress(); /调用压缩子函数else if(c=2) uncompress(); /调用解压缩子函数elseprintf(t 欢迎您再次使用该工具_n);exit(0); /退出该工具system(pause); /任意键继续system(cls); /清屏return 0;八、参考文献1. 严蔚敏，吴伟民，数据结构（C 语言版），北京：清华大学出版社，1997年版 2徐孝凯，数据结构实用教程，北京：清华大学出版社，1999 年 12 月第 1版 3. 李春葆，数据结构习题与解析，北京：清华大学出版社，2004 年 2 月第 2版 4. 谭浩强，C 语言程序设计教程，北京：高等教育出版社，1998 年 7 月第 2 版九、教师评语21