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

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 lchild; / 结点的左孩子int rchild; 结点的右孩子int *code;记录该结点的huffman编码int codelen;记录该结点huffman编码的长度/初始化结点，令其权值为无穷大，无双亲及左右孩子HTnode() weight = MAX;parent = -1;lc

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

6、/void printcode();void addbit(int bit); / void resetbyte();压缩函数，成功返回true 失败恢复函数，成功返回true 失/将原文件与压缩后的文件比将原文件与恢复后的文件比较bool compress(char *input, char *output);/ falsebool decompress(char *input, char *output); / 败 falsevoid compare(char *input, char *output);较void compare2(char *input, char *output);

7、/Word资料private: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类中

8、功能函数：1:压缩函数 bool 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个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优树。权值越大的结点离根越近的二叉树才是最优

10、二叉树( huffman树)。按照上面的算法， 则可按照下面图的构造过程生成huffman树。主程序模块：主函数huffmanTree 类Huffman编码流程，那就huffman编码是采用等长编码还浦础松容施即脾，采用不登长袖嵯酗频俏的二义性或多义性。假设用0表示字符D,用01表示字符C则当接受到编码串“ 01”，并译到字符0时，是立即译出对应的字符 D,还是接着与下一个字符 1 一起译为对应的字符 C,这就产生了二义性。因此，若对某一个字符集进行不等长编码，则要求字符集合中任何一个字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。显然等长编码是前缀编码，这从等长编码所对应

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

12、后编译通过。运行程序如下图所示图5程序主菜单压缩：在命令行下输入1对文件进行压缩，根据提示输入刚刚建的文本文件( huffman.txt ), 和要生成的压缩文祚名称，按回车确认进行压缩。图6压缩文本成功执行完毕后如下图所示。 H：,安程设计、哈夫曼压隽餐压ede huffmanDebughuffmari.exe- - Jn Jn -n - Jn LX-I 3 45678 901245679013 5-: 0 000000 1 11111 1122 2 2 n-lsl-nhuffnan的huffman 的huffman2 的huFFmdnS ijlhLLf FmAn 的huFFman 的huF

13、fman 的 hu man 的huFFman huffMn Hl huff man &Hhuffman的 huff的 huffmanman位的 huFFE&n 拧的 huFFn&n 符的 huFFman17249 B1/te14330 Byte0773 X码: 码: 就 通 通 碎 码: 通 fe： 通 相:码:R111111111111B111011010 10011111111101 SB1001111111 HH0011111Hlaeineiii 10011111110 11100011011 11110101101until 0111R QB11011100 801101110110

14、1901111110101001101110111B111111111F)0 lefliilliliiiis laoiiiiiiiini图7压缩完毕恢复：在命令行下输入2对本程序压缩的文件进行恢复，根据提示输入待恢复的文件名称 和恢复后的文件名称，按回车确定，成功执行后如下图所示。图7文件恢复完毕对比:在命令行下输入3对恢复后的文件和原文件对比，根据提示输入要对比的文件，按回车确认，成功执行后如下图所示。图8文件恢复完毕bug,详细可参见 五使用说明。五、测试结果程序功能满足设计要求，测试未发现明显程序如下:/ stdafX.h#include /#include /#include / us

15、ing namespace std;输入输出头文件文件操作的类和方法 队列容器const int leaf = 256;const long MAX = 99999999;/最多可能出现的不同字符数/表示无穷大/huffman树的结点结构体 typedef struct HTnodelong weight;int parent;int Ichild;int rchild;int *code;int codelen;/记录结点的权值记录结点的双亲结点位置结点的左孩子结点的右孩子记录该结点的huffman编码记录该结点huffman编码的长度/初始化结点，令其权值为无穷大，无双亲及左右孩子HTno

16、de()weight = MAX;parent = -1;lchild = -1;rchild = -1;codelen = 0; HTnode;/，L，L，L，L，L，L，L，L，L，L，L，L，L，L，L，L， / / a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ahuffmanTree.h/huffman 树类class huffmanTreepublic:huffmanTree();vir

17、tual huffmanTree();bool count(char *input);点的权值void create。;/压缩时统计各字符出现的次数，将其写入对应结/压缩时根据各结点的权值构造huffman树void code(); huffman 编码void printcode();/列出每个字符的huffman编码void addbit(int bit);/ 压缩时对一个未满void resetbyte();/ 将 byte 清空bool compress(char *input, char *output);返回true 失败falsebool decompress(char *inp

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

19、int bitsnum;int lacknum;/压缩文件时用来缓冲bit的变量/byte中bit的个数/压缩到最后byte中的bit不满8个时填充的0的个/，L，L，L，L，L，L，L，L，L，L，L，L，L，L,，L， / / a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a/huffmanTree.cpp#include stdafx.h#include huffmanTree.h/ Cons

20、truction/Destruction/huffmanTree:huffmanTree()/初始化成员变量root = 0;leafnum = 0;byte = 0;bitsnum = 0;lacknum = 0;huffmanTree:huffmanTree()for(int i=0; ileaf; i+)/压缩时，利用建好的huffman树计算每个字符的if(HTi.codelen != 0) delete HTi.code;/统计各字符出现的次数bool huffmanTree:count(char *input)ifstream ifs;char c;ifs.open(input,i

21、os: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(int i=leaf; i2*leaf-1; i+)int loc1=-1, loc2=-1;for(int j=0; ji; j+)

22、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;/列出每个字符的huffman编码void huffmanTree:printcode()for(int i=0; ileaf; i+)if(HTi.codele

23、n!=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)HTi.codej = 0;elseHTi.codej = 1;loc = HTloc.parent;/压缩时对一个未满8个bit的byte中加入一个bitv

24、oid 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 失败falsebool huffmanTree:compress(char *input, char *output)if( !count(input)return fa

25、lse;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); 预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数ofs.put(root-384);将根节点的位置-384写入(为使该值不超过char的最大表示范围)for(i

26、nt 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编码并加入byte中int tmp = c+128;for(int i=0; iHTtmp.codelen; i+)addbit(HTtmp.codei);if(bitsnum=8)/若byte已满8位，则车出该byt

27、e并将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);/写入最后一个字节缺失的bit个数ifs.close();ofs.close(); return true;/恢复函数 成功执行返回true 失败false bool huffmanTree:d

28、ecompress(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 ! endl;return false;ifs.get(c);lacknum = c;读出最后一个字节缺失的bit个数ifs.get(c);root = c+384; 读出根结点的位置fo

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

30、.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 = 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

31、.close();ofs.close();return true;/将原文件与压缩后的文件比较void huffmanTree:compare(char *input, char *output)ifstream origin, compress;origin.open(input,ios:binary);compress.open(output,ios:binary);if(!origin)cout 无法打开文件 input ! endl;return;if(!compress)cout 无法打开文件 output ! endl;return;double total1=0, total2=

32、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;origin.close();compress.close();/将原文件与恢复后的文件比较void huffmanTree:compare2(char *input, char *output)ifstream origin, decompress;origin.open(inpu

33、t,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) /依次比较每个字节，不同则将 dif标志设为truedif = true;total1+;total2+;while(origin.get(c1)若原文件还有剩余的数据，将 dif设为truedif = true;total1+;while(decompress.get(c2)/若恢复文件还有剩余的数据，将 dif设为truedif = true;total2+;cout 原文件大小： totall Byte endl;cout 恢复文件大小： total2 Byte endl;if(dif=true)cout 原文件与恢复文件不同！ endl;elsecout 原文件与恢复文件相同! endl;origin.close();decompress.close