哈夫曼压缩解压.docx

《哈夫曼压缩解压.docx》由会员分享，可在线阅读，更多相关《哈夫曼压缩解压.docx（29页珍藏版）》请在三一办公上搜索。

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

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

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

4、,文档中内容为字符型数据。概要设计和数据结构的选择 以下是在任务分析对题意的理解做出的概要设计和对数据结构的选择:1、数据结构定义/huffman树的结点结构体 typedef struct HTnode long weight; 记录结点的权值int parent;/记录结点的双亲结点位置int Ichild;/结点的左孩子int rchild;/结点的右孩子int *code;记录该结点的huffman编码int codelen; 记录该结点huffman编码的长度初始化结点,令其权值为无穷大，无双亲及左右孩子 HTnode() weight = MAX;parent = -1;lchil

5、d = -1;rchild = -1;codelen = 0;HTnode;2、定义huffman数类及其函数class huffmanTreepublic:huffmanTree();virtual huffmanTree();bool count(char *input);/压缩时统计各字符出现的次数，将其写入对应结点的权值 void create();/压缩时根据各结点的权值构造huffman树void code(); 压缩时利用huffman树计算每个字符的huffman编码void printcode(); /列出每个字符的huffman编码void addbit(int bit);

6、 /压缩时对一未满8个bit的byte中加入一个bitvoid resetbyte(); 将byte清空bool compress(char *input, char *output);/ 压缩函数，成功返回 true 失败 false bool decompress(char *input, char *output); / 恢复函数，成功返回 true 失败falsevoid compare(char *input, char *output);将原文件与压缩后的文件比较void compare2(char *input, char *output); /将原文件与恢复后的文件比较 pri

7、vate:int root; 记录根结点的位置int leafnum;/记录不同字符的个数HTnode HTleaf*2-1; /HTnode结构的数组,用来表示huffman树,树的最大结点个数不会超过leaf*2-1char byte;/压缩文件时用来缓冲bit的变量int bitsnum; /byte中bit的个数int lacknum; /压缩到最后byte中的bit不满8个时填充的0的个数;3、主程序的流程及模块间关系主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用switch语句进行分支执彳亍huffmanTree类中功能函数：1:压缩函数 bool

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

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

10、照上面的算法，则可按照下面图的构造过程生成huffman树。主程序模块:Huffman解码流程、上机调试以下是我在上机过程中遇到的一些问题及解决方案开始考虑问题是，要对文件进行压缩，如何才能达到比较好的效果，那就huffman编码是采用等长编码还是采用不等长问题,采用不登长编码要避免译码的二义性或多义性。假设用0表示字符D用01表示字符C则当接受到编码串.QI.，并译到字符0 时，是立即译出对应的字符D ,还是接着与下一个字符1 一起译为对应的字符C,这就产生 了二义性。因此，若对某一个字符集进行不等长编码，则要求字符集合中任何一个字符的 编码都不能是其他字符编码的前缀。符合此要求的编码叫做前

11、缀编码。显然等长编码是前 缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能 是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字 符编码才会是另一个结点的字符编码的前缀。为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编 码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予 该结点上，求出此树的最小带权路径长度就等于文件的最短长度。因此，对文件进行压 缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的 huffman树的问题。基本思路大致有了后，接下来是对程序的编

12、写工作，程序初步形成后，对其测 试，发现了一些语法错误修正后编译通过。运行程序如下图所示图5程序主菜单压缩：在命令行下输入1对文件进行压缩，根据提示输入刚刚建的文本文件(huffman.txt), 和要生成的压缩文件名称,按回车确认进行压缩。图6压缩文本成功执行完毕后如下图所示。0111111111111 1031111116100 011101101610011111111101 uumuiiiiiii 003611111111001116111 IMkJlllllllU11 侦丽 11111110161101 11110161110 0011011196F太平：17249 Bte 了大小:

13、14330 ByteM； 82.0773mJ1W3 t104 t10513C lk7 13S 1091001111110101 UMllMlliyill 0111111111001001111111111112112?11415 litH: 浜喔会计AHt天景够睡 压化口业寸1 u ffma nDeb u ghuffman .exe壬XT-X、王一i一.R-，-Tn lrT R Kn jTt ,rrr J- rT IFTT ,s L日 jTt nu. R . R- jTt InLnM nH- Ld1.1 LnM - 4.ni.4.zy.4.印Jiuf珈an朱伯: 的Jiuffman指时: ff

14、iliuffnan;的心m皿新马 的加If nan堀裾 的JiufTnan贵码 的血man?|码的加man养码 的侦FFman：；码fman;敢Huffman!柄的huffman编码liiiffmanE:不huffnan：JiufFlian 瑜码:JiufTnan第招:Jiuff nan： huffritiri 编福:图7压缩完毕恢复：在命令行下输入2对本程序压缩的文件进行恢复，根据提示输入待恢复的文件名称和恢复后的文件名称,按回车确定,成功执行后如下图所示。图7文件恢复完毕对比:在命令行下输入3对恢复后的文件和原文件对比，根据提示输入要对比的文件，按 回车确认，成功执行后如下图所示。图8文件

15、恢复完毕五、测试结果程序功能满足设计要求,测试未发现明显bug ,详细可参见五使用说明。程序如下：/ stdafx.h#include /输入输出头文件#include 文件操作的类和方法#include 队列容器using namespace std;const int leaf = 256;/最多可能出现的不同字符数const long MAX = 99999999;表示无穷大/huffman树的结点结构体typedef struct HTnodelong weight;/记录结点的权值int parent;/记录结点的双亲结点位置int lchild;结点的左孩子int rchild;/

16、结点的右孩子int *code;/记录该结点的huffman编码int codelen;/记录该结点huffman编码的长度/初始化结点,令其权值为无穷大,无双亲及左右孩子 HTnode()weight = MAX;parent = -1;lchild = -1;rchild = -1;codelen = 0;HTnode;/#/huffmanTree.h/huffman 树类 class huffmanTreepublic:huffmanTree();virtual huffmanTree();bool count(char *input);权值void create();void code

17、();huffman 编码void printcode();void addbit(int bit);void resetbyte();/压缩时统计各字符出现的次数,将其写入对应结点的压缩时根据各结点的权值构造huffman树/压缩时，利用建好的huffman树计算每个字符的/列出每个字符的huffman编码/压缩时对一个未满8个bit的byte中加入一个bit/Wbyte 清空bool compress(char *input, char *output);true 失败 falsebool decompress(char *input, char *output);true 失败 fals

18、evoid compare(char *input, char *output);比较void compare2(char *input, char *output);比较private:int root;int leafnum;HTnode HTleaf*2-1;大结点个数不会超过leaf*2-1char byte;int bitsnum;int lacknum;压缩函数成功执行返回恢复函数成功执行返回将原文件与压缩后的文件将原文件与恢复后的文件/记录根结点的位置记录不同字符的个数/HTnode结构的数组，用来表示huffman树，树的最/压缩文件时用来缓冲bit的变量/byte中bit的个

19、数/压缩到最后byte中的bit不满8个时填充的0的个数/# #/huffmanTree.cpp#include stdafx.h#include huffmanTree.h/ Construction/Destruction/huffmanTree:huffmanTree()/初始化成员变量root = 0;leafnum = 0;byte = 0;bitsnum = 0;lacknum = 0;huffmanTree:huffmanTree()for(int i=0; ileaf; i+)if(HTi.codelen != 0)delete HTi.code;统计各字符出现的次数bool

20、huffmanTree:count(char *input)ifstream ifs;char c;ifs.open(input,ios:binary);if(!ifs)(cout ”无法打开文件 input ! endl;return false;while(ifs.get(c)if(HTc+128.weight二二MAX)若该字符是第一次出现，先初始化权值HTc + 128.weight = 0;leafnum+;HTc+128.weight+;/权值+1ifs.close();return true;选权值最小的两棵树组成新的数void huffmanTree:create()for(i

21、nt i=leaf; i2*leaf-1; i+)int loc1 = -1, loc2 = -1;for(int j=0; ji; j + +)if(HTj.parent != -1)continue;if(loc1 = = -1 | HTj.weight HTloc1.weight)loc2 = loc1;loc1 = j;else if(loc2 = = -1 | HTj.weight loc2 ? loc2 : loci;HTi.rchild = loc1loc2 ? loci : loc2;HTloc1.parent = i; HTloc2.parent = i;root = i;列

22、出每个字符的huffman编码void huffmanTree:printcode()for(int i=0; ileaf; i+)if(HTi.codelen!=0)cout 值为 i-128 ”的字符的huffman编码：”；for(int j=0; jHTi.codelen; j + +)cout HTi.codej;cout endl;压缩时，利用建好的huffman树计算每个字符的huffman编码void huffmanTree:code()for(int i=0; i=0; j-)从后往前找,记录结点的huffman编码if(loc=二HTHTloc.parent.lchild)

23、HTi.codej = 0;elseHTi.codej = 1;loc = HTloc.parent;压缩时对一个未满8个bit的byte中加入一个bitvoid huffmanTree:addbit(int bit)if(bit = 0)byte = byte 1;若新增的bit为0，则直接将byte按位左移elsebyte = (byte 1) | 1);/若新增的bit为1,先将byte按位左移,再与 1按位或运算bitsnum + +;将byte清空void huffmanTree:resetbyte()byte = 0;bitsnum = 0;压缩函数成功执行返回true失败fals

24、ebool huffmanTree:compress(char *input, char *output)if( !count(input) return false;create();code();ifstream ifs;ofstream ofs;ifs.open(input,ios:binary);ofs.open(output,ios:binary);char c;if(!ifs)cout ”无法打开文件 input ! endl;return false;if(!ofs)cout ”无法打开文件 output ! endl;return false;ofs.put(0);/预留一个字

25、符，等压缩完后在该位置写入不足一个byte的bit个数 ofs.put(root-384);/将根节点的位置-384写入(为使该值不超过char的最大表示范 围)for(int i=0; ileaf*2-1; i+)写入每个结点的双亲结点位置if(HTi.parent= = -1)若该节点没有双亲结点，则写入127(一个字节所能表示的最大值)ofs.put(127);else /否则将双亲结点的位置-384再写入(为使该值不超过char的最大表示范 围)ofs.put(HTi.parent-384);while(ifs.get(c)将字符的huffman编码并加入13典中int tmp = c

26、+128;for(int i=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(int i = bitsnum; i8; i + +) addbit(0);lacknum + +;ofs.put(byte);resetbyte();ofs.seekp(0,ios:beg); /将写指针移动到文件开头ofs.put(lacknum)

27、;/写入最后一个字节缺失的bit个数ifs.close();ofs.close();return true;恢复函数成功执行返回true失败falsebool huffmanTree:decompress(char *input, char *output)queue q;char c;ifstream ifs;ofstream ofs;ifs.open(input,ios:binary);ofs.open(output,ios:binary);if(!ifs)cout ”无法打开文件 input ! endl;return true;if(!ofs)cout ”无法打开文件 output !

28、 endl;return false;ifs.get(c);lacknum = c;/读出最后一个字节缺失的bit个数ifs.get(c);root=c + 384;/读出根结点的位置for(int i=0; i1)还未到最后一个字节c = q.front();for(int i=0; i8; i + +)if(int(c&128) =0)point = HTpoint.lchild;if(HTpoint.lchild = = -1 & HTpoint.rchild = = -1) ofs.put(char(point-128);point = root;c = c 1;elsepoint =

29、 HTpoint.rchild;if(HTpoint.lchild = = -1 & HTpoint.rchild = = -1) ofs.put(char(point-128);point = root;c = c 1;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.put(char(point-128);point = root;c =

30、 c 1;elsepoint = HTpoint.rchild;if(HTpoint.lchild = = -1 & HTpoint.rchild = = -1) ofs.put(char(point-128);point = root;c = c 1;q.pop();ifs.close();ofs.close();return true;将原文件与压缩后的文件比较void huffmanTree:compare(char *input, char *output)ifstream origin, compress;origin.open(input,ios:binary);compress.

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

32、igin.close();compress.close();将原文件与恢复后的文件比较void huffmanTree:compare2(char *input, char *output)ifstream origin, decompress;origin.open(input,ios:binary);decompress.open(output,ios:binary);double total1=0, total2=0;char c1, c2;bool dif = false;while(origin.get(c1) & decompress.get(c2)if(c1!=c2)依次比较每个

33、字节，不同则将dif标志设为truedif = true;total1+;total2+;while(origin.get(c1)/若原文件还有剩余的数据,将di股为truedif = true;total1+;while(decompress.get(c2)/若恢复文件还有剩余的数据，将di股为truedif = true;total2 + +;cout ”原文件大小: total1 Byte endl;cout ”恢复文件大小: total2 Byte endl;if(dif二二true)cout ”原文件与恢复文件不同!” endl;elsecout ”原文件与恢复文件相同!” endl

34、;origin.close();decompress.close();/#/huffman.cpp #include stdafx.h#include huffmanTree.h void main() int choice = 1;char input255, output255;huffmanTree h;while(choice)cout*endl;cout *哈夫曼编码压缩恢复算法*endl;cout*endl;cout*1）压缩*endl;cout*endl;cout*2）恢复*endl;cout*endl;cout*3）恢复文件与原文件的对比*endl;cout*endl;cout

35、*4）清屏*endl;cout*endl;cout*5）退出*endl;cout*endl;cout*说明：请您输入相应的操作序号进行操作*endl;cout*endl;cout;cin choice;switch(choice)case 1:cout input;cout output;if( press(input,output)h.printcode();pare(input,output);coutendl文件压缩成功!”endl;elsecoutendl文件压缩失败!endl;break;case 2:cout input;cout output;if (h.decompress(input,output)coutendl文件恢复成功!”endl;elsecoutendl文件恢复失败!endl;break;case 3:cout input;cout output;pare2(input,output);break;case 4:执行清屏命令system(cls);break;case 5:break;default:cout ”参数错误！请重新输入” endl;cout endl;