哈夫曼压缩解压-数据结构设计报告

1、数据结构课程设计数学与应用数学一班胡耕岩2012214147-、问题分析和任务定义1.11.1 设计任务采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。要求(1)(1)运行时的压缩原文件的规模应不小于 5K5K。(2)(2)提供恢复文件与原文件的相同性对比功能。1.21.2 问题分析本课题是利用哈夫曼编码思想，设计对一个文本文件(.txt).txt)中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件(.txt).txt)。在了解哈夫曼压缩解压缩原理之前，首先让我们来认识哈夫曼树。哈夫曼树又称最优二叉树，是带权路径长度最小的二

2、叉树。在文本文件中多采用二进制编码。为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。哈夫曼树中的左右分支各代表0 0和11, ,则从根节点到叶子节点所经历的路径分支的0 0和11组成的字符串，为该节点对应字符的哈夫曼编码。统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）利用哈夫曼树的特点：权越大的叶子离根越

3、近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的节点，路径越短。哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。1.31.3测试用数据本实验的数据是通过读入一个名为

4、huffman.txthuffman.txt 的文本文档，文档中内容为字符型数据。二、概要设计和数据结构的选择以下是在任务分析对题意的理解做出的概要设计和对数据结构的选择：1 1、数据结构定义/huffman树的结点结构体typedefstructHTnode（longweight;记录结点的权值intparent;记录结点的双亲结点位置intlchild;/结点的左孩子intrchild;结点的右孩子int*code;记录该结点的huffman编码intcodelen;记录该结点huffman编码的长度初始化结点，令其权值为无穷大，无双亲及左右孩子HTnode()weight=MAX;par

5、ent=-1;lchild=-1;rchild=-1;codelen=0;HTnode;2 2、定义 huffmanhuffman 数类及其函数classhuffmanTreepublic:huffmanTree();virtualhuffmanTree();boolcount(char*input);值leaf*2-1/压缩文件时用来缓冲bit的变量/byte中bit的个数/压缩到最后byte中的bit不?t8个时填充的0的个数3 3、主程序的流程及模块间关系主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用/压缩时统计各字符出现的次数,将其写入对应结点的权voi

6、dcreate。;voidcode();voidprintcode();/压缩时根据各结点的权值构造huffman/压缩时利用huffman树计算每个字符的/列出每个字符的huffman编码树huffman编码voidaddbit(intbit);/voidresetbyte();压缩时对一个未满/将byte清空8个bit的byte中加入一个bitboolcompress(char*input,char*output);/false压缩函数，成功返回true失败booldecompress(char*input,char*output);/败falsevoidcompare(char*inpu

7、t,char*output);较voidcompare2(char*input,char*output);/private:introot;/记录根结点的位置intleafnum;/记录不同字符的个数HTnodeHTleaf*2-1;/HTnode结构的数组,恢复函数，成功返回true失/将原文件与压缩后的文件比将原文件与恢复后的文件比较用来表示huffman树，树的最大结点个数不会超过charbyte;intbitsnum;intlacknum;switch压缩函数compress对比函数compare2恢复函数decompress语句进行分支执行huffmanTree类中功能函数:1:压缩

8、函数boolcompress(char*input,char*output)2:恢复函数booldecompress(char*input,char*output)3:恢复文件与原文件的对比函数voidcompare2(char*input,char*output)并可在完成相应功能后安全退出，压缩或恢复的文件在同文件夹下生成。三、详细设计和编码核心算法-huffman算法：(1)根据给定的n个权值w1,w2,wnw1,w2,wn构成 n n 棵二叉树的集合 F=F=T1,T2T1,T2；,Tn,Tn, ,其中每棵二叉树 T1T1 中只有一个带权的 w1w1 的根据点，其左右子树均空。(2)在

9、F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右树上根结点的权值之和。(3)(3)在 F F 中删除这两棵树，同时将所得到的二叉树加入 F F 中。(4)重复(2)(3)(2)(3)，直到 F F 中只含一棵树为止。这棵树便是Huffman树。Huffman树可用于构造代码总长度最短的编码方案。为了详细说明这个问题，特以下面例子来说明：有四个叶子结点A,B,C,D,分别带权为9,4,5,2,可以构成许多种不同的带权二叉树，但各个带权二叉树的WPL(树的带权路径长度)不同，要想由n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优

10、树。权值越大的结点离根越近的二叉树才是最优二叉树(huffman树)。按照上面的算法，则可按照下面图的构造过程生成huffman树。主程序模块：huffmanTree类Huffman编码流程或多义性。假设用0表示字符D,用01表示字符C则当接受到编码串“01”，并译到字符0时，是立即译出对应的字符D,还是接着与下一个字符1一起译为对应的字符C,这就产生了二义性。因此，若对某一个字符集进行不等长编码，则要求字符集合中任何一个字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结

11、点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度， 特将每个字符的出现频率作为字符结点的权值赋予该结点上， 求出此树的最小带权路径长度就等于文件的最短长度。因此，对文件进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的huffman树的问题。基本思路大致有了后，接下来是对程序的编写工作，程序初步形成后，对其测试，发现了一些语法错误，修正后编译通过。运行程序如下图所示图5程序主菜单压缩：在命令行下输入1

12、对文件进行压缩，根据提示输入刚刚建的文本文件(huffman.txt),和要生成的压缩文件名称，按回车确认进行压缩。成功执行完毕后如下图所示。O00Q1111111UlliUlllllllOBllleillItMlllllllU111AAH11011llllQlQllQtl11110101110U011011100URIlRUiHllfl10B11111O00Q1111111UlliUlllllllOBllleillItMlllllllU111AAH11011llllQlQllQtl11110101110U011011100URIlRUiHllfl10B111111010110101图6压缩文

13、本nrp3rfF-r=TrJT-JTT:frr:rrniTnfT-rJrrrr-riTrjprjp-电力不力受石石外毛石石毛右币石力心石石辰麻庙坛后扁扁吊扁后届忘扁寸.寸-寸寸,y寸目目寸m寸-IT?01111111111111001111011111111111110011111101081101081001111111116110011111111161U1111111110010011111U11111111100100111111111101001111111111111111010011111111111H:荒亨发丁咋玉信.而MWCDGShLffTnanL：?buhuffmn.=ne

14、n na am mFrffFfFrffFfffffffffffffnnnnnnclcl一曰ammlllammlllnnnnnnnnnnnnnnnnnnnnnnnnaaaaaaadaaaaaaaaaaadaaaammmmmmmmmmmmmmmmmmmmtfffmmmmtfff f f f f fFffFfifffffffffffifffffffffffhlllululiululu1hlllululiululu1M MlulubuluhlllluhlllluhllhllhulMdvlulubuluhlllluhlllluhllhllhulMdvN N的的的的的的的用的的的的的的的的的的的也4343

15、也色匕.1:1:忖口EmrklTr-lrKKEmrklTr-lrKK另色世色1111- -ccI1I1，6666jTrTjnrTjn-rJrrjTtJTrTTJTTJTrJrrjTrTjnrTjn-rJrrjTtJTrTTJTTJTrJrr- -TTJTITTJTI. .JTrJXJTrJX- -TTITTI- -lrnlrn- -rTTrTT3 34E64E6T Tg9g9口1 12 2456?9U1456?9U112125 5E EM-00011111111222M-000111111112222UT2UT11-II11i1111A11i111ij11-II11i1111A11i111ij

16、j jE Es s- -终为身济功为谓阴为甘的阴滴以为为为防京缩直：gttgg,B.值盾.值.值；但良清.录氏玉图7压缩完毕恢复：在命令行下输入2对本程序压缩的文件进行恢复，根据提示输入待恢复的文件名称和恢复后的文件名称，按回车确定，成功执行后如下图所示。对比：在命令行下输入3对恢复后的文件和原文件对比，根据提示输入要对比的文件，按回车确认，成功执行后如下图所示。H：t果亨哈LffnanDebughuffm后nexi图7文件恢复完毕图8文件恢复完毕五、测试结果程序功能满足设计要求，测试未发现明显bug，详细可参见五使用说明。1 1H H：t t果喔重计V V岩夫号.小娥近匹ocfeWLffma

17、nDebughuftmn.exeocfeWLffmanDebughuftmn.exe哈夫曼编碣压缩帧复算法1压缩n恢复力恢复文件与原文件的对比4清屏5退出说日后请您输入相应用墀作序号迸行操任#文抒V V的2-12-1的件17174ufl垢.女，名tctc:件恢复成 5,件文：小信liAWM?_sliAWM?_sJAJJAJA A件又件程序如下:/stda仅.h#include/#include/#include/usingnamespacestd;输入输出头文件文件操作的类和方法队列容器constintleaf=256;constlongMAX=99999999;/最多可能出现的不同字符数/表

18、示无穷大/huffman树的结点结构体typedefstructHTnodelongweight;intparent;intlchild;intrchild;int*code;intcodelen;/记录结点的权值/记录结点的双亲结点位置/结点的左孩子/结点的右孩子/记录该结点的huffman编码/记录该结点huffman编码的长度初始化结点，令其权值为无穷大，无双亲及左右孩子HTnode()weight=MAX;parent=-1;lchild=-1;rchild=-1;codelen=0;HTnode;/，L，L，L，L，L，L，L， ，L，L，L，L，L，/，kk，kk，kkn-nkkn

19、-nkknnkkn-nkkn-nkk，kk，”，”IT，二/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/huffmanTree.h/huffman树类classhuffmanTreepublic:Word资料private:introot;intleafnum;HTnodeHTleaf*2-1;/HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1charbyte;/压缩文件时用来缓冲bit的变量intbitsnum;/byte中bit的个数intlacknum;/压缩到最后byte中的bit不?8个

20、时填充的0的个数;/， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ，/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa#/huffmanTree.cpp#includestdafX.h#includehuffmanTree.h/Construction/Destruction/huffmanTree:huffmanTree()/初始化成员变量root=0;leafnum=0;byte=0;bitsnum=0;lacknum=0;huffmanTree();virtualhuffmanTree();boolc

21、ount(char*input);/权值voidcreate();voidcode();huffman编码voidprintcode();voidaddbit(intbit);voidresetbyte();boolcompress(char*input,返回true失败false压缩时统计各字符出现的次数，将其写入对应结点的/压缩时根据各结点的权值构造huffman树/压缩时，利用建好的huffman树计算每个字符的/列出每个字符的huffman编码8个bit的byte中加入一个bit/压缩时对一个未满/将byte清空char*output);booldecompress(char*inpu

22、t,char*output);返回true失败falsevoidcompare(char*input,char*output);比较voidcompare2(char*input,char*output);文件比较/压缩函数成功执行恢复函数成功执行/将原文件与压缩后的文件/将原文件与恢复后的/记录根结点的位置/记录不同字符的个数)huffmanTree二huffmanTree()(for(inti=0;ileaf;i+)(if(HTi.codelen!=0)deleteHTi.code;)/统计各字符出现的次数boolhuffmanTree:count(char*input)(ifstream

23、ifs;charc;ifs.open(input,ios:binary);if(!ifs)cout无法打开文件input!endl;returnfalse;)while(ifs.get(c)if(HTc+128.weight=MAX)若该字符是第一次出现，先初始化权值HTc+128.weight=0;leafnum+;)HTc+128.weight+;/权值+1)ifs.close();returntrue;)/选权值最小的两棵树组成新的数voidhuffmanTree二create()for(inti=leaf;i2*leaf-1;i+)intloc1=-1,loc2=-1;for(intj

24、=0;ji;j+)if(HTj.parent!=-1)continue;if(loc1=-1|HTj.weightHTloc1.weight)(loc2=loc1;loc1=j;elseif(loc2=-1|HTj.weightloc2?loc2:loc1;HTi.rchild=loc1loc2?loc1:loc2;HTloc1.parent=i;HTloc2.parent=i;root=i;/列出每个字符的huffman编码voidhuffmanTree:printcode()(for(inti=0;ileaf;i+)(if(HTi.codelen!=0)cout值为i-128的字符的huf

25、fman编码：;for(intj=0;jHTi.codelen;j+)coutHTi.codej;coutendl;/压缩时，利用建好的huffman树计算每个字符的huffman编码voidhuffmanTree:code()for(inti=0;i=0;j-)/从后往前找，记录结点的huffman编码if(loc=HTHTloc.parent.lchild)HTi.codej=0;elseHTi.codej=1;loc=HTloc.parent;/压缩时对一个未满8个bit的byte中加入一个bitvoidhuffmanTree:addbit(intbit)if(bit=0)byte=by

26、te1;/若新增的bit为0,则直接将byte按位左移elsebyte=(byte1)|1);/若新增的bit为1,先将byte按位左移，再与1按位或运算bitsnum+;将byte清空voidhuffmanTree:resetbyte()byte=0;bitsnum=0;/压缩函数成功执行返回true失败falseboolhuffmanTree:compress(char*input,char*output)if(!count(input)returnfalse;create();code();ifstreamifs;ofstreamofs;ifs.open(input,ios:binary

27、);ofs.open(output,ios:binary);charc;if(!ifs)cout无法打开文件input!endl;returnfalse;if(!ofs)cout无法打开文件output!endl;returnfalse;ofs.put(0);预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数ofs.put(root-384);将根节点的位置-384写入(为使该值不超过char的最大表示范围)for(inti=0;ileaf*2-1;i+)/写入每个结点的双亲结点位置if(HTi.parent=-1)若该节点没有双亲结点，则写入127(一个字节所能表示的最大值)o

28、fs.put(127);else否则将双亲结点的位置-384再写入(为使该值不超过char的最大表示范围)ofs.put(HTi.parent-384);while(ifs.get(c)/将字符的huffman编码并加入byte中inttmp=c+128;for(inti=0;iHTtmp.codelen;i+)addbit(HTtmp.codei);if(bitsnum=8)若byte已满8位，则输出该byte并将byte清空ofs.put(byte);resetbyte();)if(bitsnum!=0)/处理最后未满8个字符的byte,用0填充并记录填充的个数for(inti=bitsn

29、um;i8;i+)addbit(0);lacknum+;)ofs.put(byte);resetbyte();)ofs.seekp(0,ios:beg);/将写指针移动到文件开头ofs.put(lacknum);/写入最后一个字节缺失的bit个数ifs.close();0fs.close();returntrue;)恢复函数成功执行返回true失败falseboolhuffmanTree:decompress(char*input,char*output)queueq;charc;ifstreamifs;ofstreamofs;ifs.open(input,ios:binary);ofs.op

30、en(output,ios:binary);if(!ifs)cout无法打开文件input!endl;returntrue;)if(!ofs)cout无法打开文件output!endl;returnfalse;)ifs.get(c);lacknum=c;/读出最后一个字节缺失的bit个数ifs.get(c);root=c+384;/读出根结点的位置for(inti=0;i1)/还未到最后一个字节c=q.front();for(inti=0;i8;i+)if(int(c&128)=0)point=HTpoint.lchild;if(HTpoint.lchild=-1&HTpoin

31、t.rchild=-1)ofs.put(char(point-128);point=root;c=c1;elsepoint=HTpoint.rchild;if(HTpoint.lchild=-1&HTpoint.rchild=-1)ofs.put(char(point-128);point=root;c=c1;q.pop();)c=q.front();/最后一个字节for(i=0;i8-lacknum;i+)(if(int(c&128)=0)(point=HTpoint.lchild;if(HTpoint.lchild=-1&HTpoint.rchild=-1)(ofs

32、.put(char(point-128);point=root;)c=c1;)elsepoint=HTpoint.rchild;if(HTpoint.lchild=-1&HTpoint.rchild=-1)ofs.put(char(point-128);point=root;)c=c1;)q.pop();ifs.close();0fs.close();returntrue;)/将原文件与压缩后的文件比较voidhuffmanTree:compare(char*input,char*output)ifstreamorigin,compress;origin.open(input,ios:

33、binary);compress.open(output,ios:binary);if(!origin)cout无法打开文件input!endl;return;)if(!compress)(cout无法打开文件output!endl;return;)doubletotal1=0,total2=0;charc;while(origin.get(c)total1+;while(compress.get(c)total2+;cout原文件大小：total1Byteendl;cout压缩后大小：total2Byteendl;cout压缩率：total2/total1*100%endl;origin.c

34、lose();compress.close();)/将原文件与恢复后的文件比较voidhuffmanTree:compare2(char*input,char*output)(ifstreamorigin,decompress;origin.open(input,ios:binary);decompress.open(output,ios:binary);doubletotal1=0,total2=0;charc1,c2;booldif=false;while(origin.get(c1)&decompress.get(c2)(if(c1!=c2)/依次比较每个字节，不同则将dif标志设为truedif=true;total1+;total2+;)while(origin.