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

《数据结构》课程设计报告设计题目：哈夫曼编码压缩解压缩学生姓名：专业：计算机科学与技术班级：学号：指导老师：完成日期：合肥工业大学计算机与信息学院一、问题分析和任务定义1.1设计任务采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。要求（1）描述压缩基本符号的选择方法。（2）运行时的压缩原文件的规模应不小于5K。（3）提供恢复文件与原文件的相同性对比功能。1.2问题分析本课题是利用哈夫曼编码思想，设计对一个文本文件（.txt）中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件（.txt）。在了解哈夫曼压缩解压缩原理之前，首先让我们来认识哈夫曼树。哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。在文本文件中多采用二进制编码。为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的节点，路径越短。哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。1.3测试用数据本实验的数据是通过读入一个名为huffman.txt的文本文档，文档中内容为字符型数据。二、概要设计和数据结构的选择以下是在任务分析对题意的理解做出的概要设计和对数据结构的选择：1、数据结构定义//huffman树的结点结构体typedefstructHTnode{longweight;//记录结点的权值intparent;//记录结点的双亲结点位置intlchild;/结点的左孩子intrchild;//结点的右孩子int*code;//记录该结点的huffman编码intcodelen;//记录该结点huffman编码的长度//初始化结点，令其权值为无穷大，无双亲及左右孩子HTnode(){weight=MAX;parent=-1;lchild=-1;rchild=-1;codelen=0;}}HTnode;2、定义huffman数类及其函数classhuffmanTree{public:huffmanTree();virtual~huffmanTree();boolcount(char*input);//压缩时统计各字符出现的次数，将其写入对应结点的权值voidcreate();//压缩时根据各结点的权值构造huffman树voidcode();//压缩时利用huffman树计算每个字符的huffman编码voidprintcode();//列出每个字符的huffman编码voidaddbit(intbit);//压缩时对一个未满8个bit的byte中加入一个bitvoidresetbyte();//将byte清空boolcompress(char*input,char*output);//压缩函数,成功返回true失败falsebooldecompress(char*input,char*output);//恢复函数,成功返回true失败falsevoidcompare(char*input,char*output);//将原文件与压缩后的文件比较voidcompare2(char*input,char*output);//将原文件与恢复后的文件比较private:introot;//记录根结点的位置intleafnum;//记录不同字符的个数HTnodeHT[leaf*2-1];//HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1charbyte;//压缩文件时用来缓冲bit的变量intbitsnum;//byte中bit的个数intlacknum;//压缩到最后byte中的bit不满8个时填充的0的个数};3、主程序的流程及模块间关系主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用switch语句进行分支执行huffmanTree类中功能函数：1:压缩函数boolcompress(char*input,char*output)2:恢复函数booldecompress(char*input,char*output)3:恢复文件与原文件的对比函数voidcompare2(char*input,char*output)并可在完成相应功能后安全退出，压缩或恢复的文件在同文件夹下生成。三、详细设计和编码核心算法----huffman算法：（1）根据给定的n个权值｛w1,w2,……,wn｝构成n棵二叉树的集合F=｛T1,T2,……,Tn｝,其中每棵二叉树T1中只有一个带权的w1的根据点，其左右子树均空。（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右树上根结点的权值之和。（3）在F中删除这两棵树，同时将所得到的二叉树加入F中。（4）重复（2）(3),直到F中只含一棵树为止。这棵树便是Huffman树。Huffman树可用于构造代码总长度最短的编码方案。为了详细说明这个问题，特以下面例子来说明：有四个叶子结点A,B,C,D,分别带权为9,4,5,2，可以构成许多种不同的带权二叉树，但各个带权二叉树的WPL（树的带权路径长度）不同，要想由n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优树。权值越大的结点离根越近的二叉树才是最优二叉树（huffman树）。按照上面的算法，则可按照下面图的构造过程生成huffman树。Huffman树产生流程:图1Huffman树产生流程主程序模块:图2程序模块主函数菜单huffmanTree类压缩函数compress恢复函数decompress对比函数compare2Huffman编码流程图3编码流程Huffman解码流程图4解码流程NOYES哈夫曼编码位操作压缩存储压缩文件成功!计算压缩率%打开文本文件统计文件长度初始化节点构建哈夫曼树计算左右分支权值大小,进行无重复前缀编码压缩文件失败NOYES解压压缩文件成功!解压缩文件失败!打开压缩文件读取原文件长度进行文件定位根据哈夫曼编码的长短,对节点进行排序通过哈夫曼编码的长短,依次解码,从原来的位存储还原到字节存储在单字节内对相应位置补0四、上机调试以下是我在上机过程中遇到的一些问题及解决方案开始考虑问题是，要对文件进行压缩，如何才能达到比较好的效果，那就huffman编码是采用等长编码还是采用不等长问题，采用不登长编码要避免译码的二义性或多义性。假设用0表示字符D,用01表示字符C则当接受到编码串“…01…”，并译到字符0时，是立即译出对应的字符D，还是接着与下一个字符1一起译为对应的字符C，这就产生了二义性。因此，若对某一个字符集进行不等长编码，则要求字符集合中任何一个字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于文件的最短长度。因此，对文件进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的huffman树的问题。基本思路大致有了后，接下来是对程序的编写工作，程序初步形成后，对其测试，发现了一些语法错误,修正后编译通过。五、使用说明用户进行本程序前，首先要在起工程文件下建立一个待压缩的文本文档，例如：huffman.txt，文档内已有内容，且文档大小大于5K。运行程序如下图所示图5程序主菜单压缩：在命令行下输入1对文件进行压缩，根据提示输入刚刚建的文本文件（huffman.txt），和要生成的压缩文件名称，按回车确认进行压缩。图6压缩文本成功执行完毕后如下图所示。图7压缩完毕恢复：在命令行下输入2对本程序压缩的文件进行恢复，根据提示输入待恢复的文件名称和恢复后的文件名称，按回车确定，成功执行后如下图所示。图7文件恢复完毕对比：在命令行下输入3对恢复后的文件和原文件对比，根据提示输入要对比的文件，按回车确认，成功执行后如下图所示。图8文件恢复完毕六、测试结果程序功能满足设计要求，测试未发现明显bug，详细可参见五使用说明。七、参考书目【1】吴国凤.C/C++程序设计（第2版）【M】.高等教育出版社，2009年9月【2】郑莉等.c++语言程序设计（第三版）【M】.北京：清华大学出版社，2003年12月附录：//stdafx.h#includeiostream//输入输出头文件#includefstream//文件操作的类和方法#includequeue//队列容器usingnamespacestd;constintleaf=256;//最多可能出现的不同字符数constlongMAX=99999999;//表示无穷大//huffman树的结点结构体typedefstructHTnode{longweight;//记录结点的权值intparent;//记录结点的双亲结点位置intlchild;//结点的左孩子intrchild;//结点的右孩子int*code;//记录该结点的huffman编码intcodelen;//记录该结点huffman编码的长度//初始化结点，令其权值为无穷大，无双亲及左右孩子HTnode(){weight=MAX;parent=-1;lchild=-1;rchild=-1;codelen=0;}}HTnode;//##############################################################//huffmanTree.h//huffman树类classhuffmanTree{public:huffmanTree();virtual~huffmanTree();boolcount(char*input);//压缩时统计各字符出现的次数，将其写入对应结点的权值voidcreate();//压缩时根据各结点的权值构造huffman树voidcode();//压缩时，利用建好的huffman树计算每个字符的huffman编码voidprintcode();//列出每个字符的huffman编码voidaddbit(intbit);//压缩时对一个未满8个bit的byte中加入一个bitvoidresetbyte();//将byte清空boolcompress(char*input,char*output);//压缩函数成功执行返回true失败falsebooldecompress(char*input,char*output);//恢复函数成功执行返回true失败fa