《哈夫曼压缩解压》由会员分享，可在线阅读，更多相关《哈夫曼压缩解压（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计数学与应用数学一班胡耕岩2012214147、问题分析和任务定义1.1设计任务采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。要求（1）运行时的压缩原文件的规模应不小于5K。（2）提供恢复文件与原文件的相同性对比功能。1.2问题分析本课题是利用哈夫曼编码思想，设计对一个文本文件（.txt）中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件（.txt）O在了解哈夫曼压缩解压缩原理之前，首先让我们来认识哈夫曼树。哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。在文本文件中多采用二进制编码。为了使文件尽可能的缩
2、短，可以对文件中每个字符出现的次数进行统计。设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，女口：左子树的权值小于右子树的权值。哈夫曼树中的左右分支各代表0和1；则从根节点到叶子节点所经历的路径分支的0和1组成的字符串，为该节点对应字符的哈夫曼编码。统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的节点，路径
3、越短。哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。1.3测试用数据本实验的数据是通过读入一个名为huffman.txt的文本文档，文档中内容为字符型数据1、概要设计和数据结
4、构的选择以下是在任务分析对题意的理解做出的概要设计和对数据结构的选择:1、数据结构定义/huffman树的结点结构体typedefstructHTnodelongweight;/记录结点的权值intparent;/记录结点的双亲结点位置intlchild;/结点的左孩子intrchild;/结点的右孩子int*code;/记录该结点的huffman编码intcodelen;/记录该结点huffman编码的长度/初始化结点，令其权值为无穷大，无双亲及左右孩子HTnode()weight=MAX;parent=-1;lchild=-1;rchild=-1;codelen=0;2、定义huffman
5、数类及其函数classhuffmanTreepublic:huffmanTree();virtualhuffmanTree();boolcount(char*input);/值voidcreate();voidcode();voidprintcode();voidaddbit(intbit);/voidresetbyte();HTnode;压缩时统计各字符出现的次数，将其写入对应结点的权/压缩时根据各结点的权值构造huffman树/压缩时利用huffman树计算每个字符的huffman编码/列出每个字符的huffman编码压缩时对一个未满8个bit的byte中加入一个bit/将byte清空压缩
6、函数,成功返回true失败恢复函数,成功返回true失/将原文件与压缩后的文件比将原文件与恢复后的文件比较boolcompress(char*input,char*output);/falsebooldecompress(char*input,char*output);/败falsevoidcompare(char*input,char*output);较voidcompare2(char*input,char*output);/private:introot;/记录根结点的位置intleafnum;/记录不同字符的个数HTnodeHTleaf*2-1;/HTnode结构的数组，用来表示huf
7、fman树，树的最大结点个数不会超过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:恢复文件与原文件的对比函数v
8、oidcompare2(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树。
9、Huffman树可用于构造代码总长度最短的编码方案。为了详细说明这个问题，特以下面例子来说明：有四个叶子结点A,B,C,D,分别带权为9,4,5,2，可以构成许多种不同的带权二叉树，但各个带权二叉树的WPL(树的带权路径长度)不同，要想由n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优树。权值越大的结点离根越近的二叉树才是最优二叉树(huffman树)。按照上面的算法，则可按照下面图的构造过程生成huffman树。主程序模块：huffmanTree类Huffman编码流程打开文本文件统计文件长度打开文本文件统计文件长度构建哈夫曼树计算左右分支权值大小，进行无重复前缀编构建哈夫
10、曼树哈夫曼编码位操作压缩存储Huffman解码流程YESNO压缩文件成功！计算压压缩文件失败缩压缩文件读取原文件长度进行文件定位通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储根据哈夫曼编码的长短，对节点进行排序在单字节内对相应位置补四、上机调试0以下是我在上机过程中遇到的一些问题及解决方案NO开始考虑问题是，要对文件进行压缩，如何才能达到比较好的效果，那就huffman编码是采用等长编码还解压压缩文件长问题，采用不登长编码要文件失败码的二义性或多义性。假设用0表示字符D,用01表示字符C则当接受到编码串“-01”，并译到字符0时，是立即译出对应的字符D,还是接着与下一个字符1一起
11、译为对应的字符C,这就产生了二义性。因此，若对某一个字符集进行不等长编码，则要求字符集合中任何一个字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于文件的最短长度。因此，对文件
12、进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的huffman树的问题。基本思路大致有了后，接下来是对程序的编写工作，程序初步形成后，对其测试，发现了一些语法错误，修正后编译通过。运行程序如下图所示图5程序主菜单压缩：在命令行下输入1对文件进行压缩，根据提示输入刚刚建的文本文件(huffman.txt)，和要生成的压缩文件名称，按回车确认进行压缩。图6压缩文本文件压缩咸功码码码码码養为104的圭直为J105的壬直为1测的字匱为1即的丰曽为価的生直为H的的壬宜为询的全曾为仆的主直为11石的之直为的壬直为丄17的壬I網籬I益籬帀气：ei码：0B码011101101
13、0码：码M1001111111科：HH001111111Biiiaxiiiiilaeineiiiliiimaiiiosaii0iii00M1101110110LMiiiiiiiiiie:征的buffmangfmanl符的huffn)an:卷的huffmanl笠的huffmanJ:签的huffMllfi智的luFFman自_:符的huFfmnln码W&5huffmanS赞的huFfman编码卷的huffman:过的AllFFman自符的huFfman自:卷的huffmanl雀的huffmanJ:签的huffMllfi智的tuFFnan岂_:特的huFFman编码17249B/te14330Byt
14、e0773X成功执行完毕后如下图所示。图7压缩完毕恢复：在命令行下输入2对本程序压缩的文件进行恢复，根据提示输入待恢复的文件名称和恢复后的文件名称，按回车确定，成功执行后如下图所示。文件压缩成功哈夫曼编码压缩恢复算法压缩恢复恢复文件与原文件的对比清屏退出请您输入相应的操作停号进行操作:M耳XXiKMEMiKKXX瓮梵梵梵算KUhuffman,hf文件恢复成功S3.0773dehuffn-txt图7文件恢复完毕对比：在命令行下输入3对恢复后的文件和原文件对比，根据提示输入要对比的文件，按回车确认，成功执行后如下图所示。图8文件恢复完毕五、测试结果程序功能满足设计要求，测试未发现明显bug,详细可
15、参见五使用说明。程序如下:/stdafx.h#ineludeII#ineludeII#ineludeIIusingnamespaeestd;输入输出头文件文件操作的类和方法队列容器constintleaf=256;constlongMAX=99999999;II最多可能出现的不同字符数II表示无穷大IIhuffman树的结点结构体typedefstructHTnodelongweight;II记录结点的权值intparent;II记录结点的双亲结点位置intlchild;II结点的左孩子intrchild;II结点的右孩子int*code;II记录该结点的huffman编码intcodelen;II记录该结点huffman编码的长度II初始化结点，令其权值为无穷大，无双亲及左右孩子HTnode()weight=MAX;parent=-1;lchild=-1;rchild=-1;codelen=
