哈夫曼编码课程设计报告

数据结构课程设计报告基于哈夫曼树的文件压缩/解压程序2009-11-102一需求分析1.课题要求（实现文件的压缩与解压并计算压缩率）A.描述压缩基本符号的选择方法B.运行时压缩原文件的规模应不小于5K2.设计目标A软件名称：基于哈夫曼编码的文件压缩实用程序系统B软件组成：huffman.exeC制作平台及相关调试工具：WindowsXPsp3MicrosoftVisualC++6.0D运行环境：dos/win2K/win2003/winxp/E性能特点：1.软件由一个可执行文件组成huffman.exe为dos系统应用程序，体积小，高效快捷，适用范围广。2.对单字节（256叶子）进行哈夫曼编码，压缩率良好3.使用二级缓冲压缩/解压技术，速度比一般算法高4.可压缩最大体积为4G的文件，达到Fat32文件系统极限5.文件索引体积比常规算法小50%二概要设计1.相关函数介绍31.boolInitFromFile(stringfileadd)从文件中初始化哈夫曼树函数2.voidHTCreat(HTNodeht[],intn)构造哈夫曼树函数3.voidHCCreat(HTNodeht[],HCodehcd[],intn)构造哈夫曼编码函数4.voidConvertFile(HCodehcd[],stringfileadd,stringfileadd2)压缩and写入文件函数5.voidDecompressionFile(stringfileadd2,stringfileadd3)文件解压函数6.stringCompression(stringfileadd)压缩函数7.stringDecompression(stringfileadd2)解压函数2.函数调用示意图三详细设计Main()Compression()Decompression()Clock()Initfromfile()Htcreat()Hccreat()Convertfile()Decompressionfile()Clock()Exit()Clock()41.压缩算法部分A核心算法：Huffman编码是一种可变长编码方式，是由美国数学家DavidHuffman创立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。B哈夫曼树构造算法：Huffman树是二叉树的一种特殊转化形式。以下是构件Huffman树的例子：比如有以下数据，ABFACGCAHGBBAACECDFGFAAEABBB先进行统计A(8)B(6)C(4)D(1)E(2)F(3)G(3)H(1)括号里面的是统计次数生成Huffman树：每次取最小的那两个节点(node)合并成一个节点(node)，并且将累计数值相加作为新的接点的累计数值，最顶层的是根节点(root)注：列表中最小节点的是指包括合并了的节点在内的所有节点，已经合并的节点不在列表中运算的过程如下：1:D+H(2)2:DE+H(4)3:F+G(6)4:C+DEH(8)5:B+FG(12)6:A+CDEH(16)7:ACDEH+BFG(28)那么转化为Huffman树就是Huffman树层数Root┌┴┐ACDEHBFG1┌┴┐┌┴┐CDEHABFG2┌┴┐┌┴┐DEHCFG3┌┴┐DHE4┌┴┐DH55取左面是1右面是0则有。注：层数就是位数或者说是代码长度，权值=代码长度*该字的统计次数。代码位数权值A=10216B=01212C=110312D=1111155E=111048F=00139G=00026H=1111055可以看出Huffman代码是唯一可解的(uniquelydecodable)，如果你读到110就一定是C，不会有任何一个编码是以110开始的。如果不使用Huffman算法，而使用普通的编码，结果是什么呢？Huffman树层数Root┌┴┐ABCDEFGH1┌┴┐┌┴┐ABCDEFGH2┌┴┐┌┴┐┌┴┐┌┴┐ABCDEFGH3取左面是1右面是0则有代码位数权值A=111324B=110318C=101312D=10033E=01136F=01039G=00139H=00033利用Huffman编码得到的权值累计是73，如果利用普通定长编码的话，则要用84字符长度。从这个比较，可以看出，Huffman是怎么进行压缩的。6C哈夫曼编码结构及算法编码：将ABCDEFGH用Huffman树产生的编码对应着写到文件中，并且保留原始的Huffman树，主要是编码段的信息。一般要编码256个元素的话需要511个单位来储存Huffman树，每个Huffman树都必须有以下的结构：code,char,left,right,probability(出现次数)，通常情况是利用一个数组结构。因为在解码的时候只需要用到code，所以只需要记录每个元素的编码就可以了。解码：利用文件中保存的Huffman编码，一一对应，解读编码，把可变长编码转换为定长编码。D写入算法的优化——使用二级1024K缓冲器在写入编码的过程中，宏观的过程是：以字节形式读取原文件，然后找到该字节的编码，进而以字节形式写到压缩文件中去。不停的字节读写会给cpu带来频繁的中断并且硬盘的磁头来回在磁道扇区中移动，减慢了速度。而如果以数据块的形式读写则可以有效地利用到DMA通讯，减少了cpu中断，并使硬盘磁头连续移动，显著加快了速度。而c++语言的iofstream类的read（）与write（）成员函数为此思想的实现提供了可能。所以，可以开辟一个1024K的缓冲区，先将文件前1024K的字节读入内存缓冲区中，编码后的字节也不急于写入文件中，而是先写到另一个二级缓冲区中，当其足够1024K时再以数据块的形式写到压缩文件中。然后清空缓冲区，继续做下一个1024K的编码写入。而缓冲区本身，其实就是二个整形数组，read_buffer[1048576]和write_buffer[1048576]。不过这样的数组声明已经太大了，可以用STL的vector向量类来代替这个数组（vector结构实际也就是一个封装了的加强型数组）。2．解压缩算法部分A.基于字符匹配的解压算法读出结点数就能知道哈夫曼树存入部分的总长，方便读出树哈夫曼树（子结点值和权值），就能由次些信息重新构造完整的哈夫曼树，和各结点的哈夫曼编码。解压时，读取一个字节（8bit）用一个函数转换为8个字符（用一个数组记录，其元素只是一个0或一个1），然后按哈夫曼树从顶向下查找，如果到达叶子结点，就读出该叶子结点的值，放入缓冲区中，如果不是，则继续找，如此重复，直到缓冲区满了，就写入到解压文件中，再循环以上过程，直到处理完所有数据。B.缓冲输入输出和压缩时采用1M二级缓冲相同，如果的压缩时也采用此技术，也会有很大的速度优化，当然程序也变得更加复杂。7四调试分析序号时间相关信息110月15日核心算法运行成功210月20日编码方案采用二重缓冲，进一步加快效率311月6日改进显示外观411月10日更正了输入错误文件时程序运行错误511月14日完善用户操作部分，避免了某些误操作五用户使用说明1.运行huffman.exe程序，出现下面的界面82.选择相应的功能，输入正确文件路径，对文件进行压缩、解压缩六测试结果各种类型文件的压缩率测试文件类型文件名称文件大小压缩后压缩率%文本文件（txt）sftxt2997222074.0741sftxt2570001678629.4491位图文件（bmp）sfbmp1132949925687.6092可执行文件（exe）sfexe34406425187773.2064音频文件（wma）sfwma1054341105336399.9072以上测试环境：CPU:AMD4400+2.31GHz,内存：DDRⅡ2048M,硬盘：160GB（7200rpm）,系统：windowsXP.9七设计心得体会通过这次课题实验的程序实践，我实在获益匪浅！数据结构是上个学期开展的一门学科，学习好这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。同时，学习这门学科也是艰辛的，因为它比较难懂，这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中领悟。这次的程序设计对我来说无疑是一个具大的考验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。因为开始时基础不是很好，过程中遇到了不少的阻碍，编写程序的进度也比较慢。虽然如此，但是通过自己的努力与老师的指导，我对这次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的基础下写出了本次实验的核心算法，并使其能够正常的运行。这一个多月的设计工作，让我体会到了作为一个编程人员的艰难，一个算法到具体实现，再到应用层面的开发是需要有一段较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程人员还要花很多的时间去完善它，其中包含的心酸，外人是不会明白的。非常感谢在背后一直给我指导的老师和同学，他们的支持和鼓励让我在遇到挫折时能够站起来战胜它，也让我走到了今天这一步，完成了实验的设计。今后，我会更加努力的学习专业知识，提高自我的能力。10八附录程序清单在此，给出huffman.exe的程序清单。#includefstream#includeiostream#includeString#includecmathusingnamespacestd;structHTNode{chardata;//节点数据intweight;//权值intparent;//父亲intlchild;//左孩子intrchild;//右孩子};typedefchar*Code;HTNode*ht;Code*hcd;intmaplist[256];//建立字符与哈夫曼编码的映射intnodenum=0;//哈夫曼树结点数intrearnum=0;//哈夫曼编码尾补码inttextlen=0;//需压缩的文件长度intcodelen=0;//压缩后的文件的哈夫曼编码总长度intconstbufferlen=1024;//设置读取缓冲区长度intclean();//清空节点及编码指针内容voiddtobin(intnum,intbin[8]);//十进制变换成二进制voidHTCreate(HTNodeht[],intn);//建立哈夫曼树voidHCCreat(HTNodeht[],Codehcd[],intn);//提取哈夫曼编码voidWriteFile(char*tmp);//写入文件unsignedcharConvertBinary(char*tmp);//变换二进制文件voidConvertFile(Codehcd[],stringfileadd,stringfileadd2);//压缩并解压文件boolInitFromFile(stringfileadd);//初始化文件voidDecompressionFile(stringfileadd2,stringfileadd3);//解压文件stringCompression(stringfileadd);//压缩文件stringDecompression(stringfileadd2);//解压文件子函数///////////////十进制转二进制函数/////////////////intclean(){delete[]ht;delete[]hcd;return1;}voiddtobin(intnum,intbin[8]){inti=0;for(i=0;i8;i++){bin[i]=0;}i=0;while(num0){bin[8-1-i]=num%2;num=num/2;i++;}11}//////////////////压缩和写入文件/