您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 项目/工程管理 > 哈夫曼编码课程设计报告 (2)
0《数据结构与算法分析》课程设计报告课题名称:哈夫曼编码课题设计人:李慧杰学号:2012141461171指导教师:朱宏评阅成绩:____________________________评阅意见:________________________________________________________________________________________________________________________________________________________________________________________________提交报告时间:2013年12月25日课程名称:数据结构与算法分析课程设计报告学生姓名:李慧杰学生学号:20121414611711哈夫曼编码计算机科学与技术专业学生李慧杰指导老师朱宏一、实验三:哈夫曼编码二、实验目的与要求1.要求对文件进行Huffman编码的算法,以及对一编码文件进行解码的算法。2.熟练掌握二叉树的应用。三、实验环境1.硬件环境:Intel(R)Celeron®mCPU520@1.60GHz0.99GB内存2.软件环境:操作系统:WIN7编译软件:MicroSoftVisualC++6.0四、算法描述1.概要设计1.boolInitFromFile(stringfileadd)从文件中初始化哈夫曼课程名称:数据结构与算法分析课程设计报告学生姓名:李慧杰学生学号:20121414611712树函数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.压缩算法:A核心算法:Huffman编码是一种可变长编码方式,是由美国数学家DavidHuffman创立的,是二叉树的一种特殊转化形式。编码的原理是:将使用次数多的代码转换成长度较短的代码,而使用次数少的可以使用较长的编码,并且保持编码的唯一可解性。Huffman算法的最根本的原则是:累计的(字符的统计数字*字符的编码长度)为最小,也就是权值(字符的统计数字*字符的编码长度)的和最小。B哈夫曼树构造算法:Huffman树是二叉树的一种特殊转化形式。以下是构件Huffman课程名称:数据结构与算法分析课程设计报告学生姓名:李慧杰学生学号:20121414611713树的例子:比如有以下数据,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树层数课程名称:数据结构与算法分析课程设计报告学生姓名:李慧杰学生学号:20121414611714Root┌┴┐ACDEHBFG1┌┴┐┌┴┐CDEHABFG2┌┴┐┌┴┐DEHCFG3┌┴┐DHE4┌┴┐DH5取左面是1右面是0则有。注:层数就是位数或者说是代码长度,权值=代码长度*该字的统计次数。代码位数权值A=10216B=01212C=110312D=1111155课程名称:数据结构与算法分析课程设计报告学生姓名:李慧杰学生学号:20121414611715E=111048F=00139G=00026H=1111055可以看出Huffman代码是唯一可解的(uniquelydecodable),如果你读到110就一定是C,不会有任何一个编码是以110开始的。如果不使用Huffman算法,而使用普通的编码,结果是什么呢?Huffman树层数Root┌┴┐ABCDEFGH1┌┴┐┌┴┐ABCDEFGH2┌┴┐┌┴┐┌┴┐┌┴┐ABCDEFGH3课程名称:数据结构与算法分析课程设计报告学生姓名:李慧杰学生学号:20121414611716取左面是1右面是0则有代码位数权值A=111324B=110318C=101312D=10033E=01136F=01039G=00139H=00033利用Huffman编码得到的权值累计是73,如果利用普通定长编码的话,则要用84字符长度。从这个比较,可以看出,Huffman是怎么进行压缩的。C哈夫曼编码结构及算法编码:将ABCDEFGH用Huffman树产生的编码对应着写到文件中,并且保留原始的Huffman树,主要是编码段的信息。一般要编码256个元素的话需要511个单位来储存Huffman树,每个Huffman树都必须有以下的结构:code,char,left,right,probability(出现次课程名称:数据结构与算法分析课程设计报告学生姓名:李慧杰学生学号:20121414611717数),通常情况是利用一个数组结构。因为在解码的时候只需要用到code,所以只需要记录每个元素的编码就可以了。解码:利用文件中保存的Huffman编码,一一对应,解读编码,把可变长编码转换为定长编码。D写入算法的优化——使用二级1024K缓冲器在写入编码的过程中,宏观的过程是:以字节形式读取原文件,然后找到该字节的编码,进而以字节形式写到压缩文件中去。不停的字节读写会给cpu带来频繁的中断并且硬盘的磁头来回在磁道扇区中移动,减慢了速度。而如果以数据块的形式读写则可以有效地利用到DMA通讯,减少了cpu中断,并使硬盘磁头连续移动,显著加快了速度。而c++语言的iofstream类的read()与write()成员函数为此思想的实现提供了可能。所以,可以开辟一个1024K的缓冲区,先将文件前1024K的字节读入内存缓冲区中,编码后的字节也不急于写入文件中,而是先写到另一个二级缓冲区中,当其足够1024K时再以数据块的形式写到压缩文件中。然后清空缓冲区,继续做下一个1024K的编码写入。而缓冲区本身,其实就是二个整形数组,read_buffer[1048576]和write_buffer[1048576]。不过这样的数组声明已经太大了,可以课程名称:数据结构与算法分析课程设计报告学生姓名:李慧杰学生学号:20121414611718用STL的vector向量类来代替这个数组(vector结构实际也就是一个封装了的加强型数组)。3.解压算法A.基于字符匹配的解压算法读出结点数就能知道哈夫曼树存入部分的总长,方便读出树哈夫曼树(子结点值和权值),就能由次些信息重新构造完整的哈夫曼树,和各结点的哈夫曼编码。解压时,读取一个字节(8bit)用一个函数转换为8个字符(用一个数组记录,其元素只是一个0或一个1),然后按哈夫曼树从顶向下查找,如果到达叶子结点,就读出该叶子结点的值,放入缓冲区中,如果不是,则继续找,如此重复,直到缓冲区满了,就写入到解压文件中,再循环以上过程,直到处理完所有数据。B.缓冲输入输出和压缩时采用1M二级缓冲相同,如果的压缩时也采用此技术,也会有很大的速度优化,当然程序也变得更加复杂。五、源程序#includefstream#includeiostream#includeString#includecmathusingnamespacestd;structHTNode课程名称:数据结构与算法分析课程设计报告学生姓名:李慧杰学生学号:20121414611719{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;}课程名称:数据结构与算法分析课程设计报告学生姓名:李慧杰学生学号:201214146117110voiddtobin(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++;}}//////////////////压缩和写入文件//////////////////voidConvertFile(Codehcd[],stringfileadd,stringfileadd2){////////////////////////////////////////fstreaminfile(fileadd.c_str(),ios::in|ios::binary);fstreamoutfile(fileadd2.c_str(),ios::out|ios::binary);if(!infile)coutopenfilefail!endl;if(!outfile)coutcreatfilefail!endl;//unsignedcharch;/////////////写入哈夫曼树//////////////ch=nodenum;outfile.write(&ch,1);///写入结点数ch=8;outfile.write(&ch,1);///写入补位数(预写入)codelen=0;outfile.write((char*)&codelen,4);//写入压缩后的文件的哈夫曼编码总长度(预写入)inth=0;for(h=0;hnodenum;h++){outfile.write((char*)&ht[h].d
本文标题:哈夫曼编码课程设计报告 (2)
链接地址:https://www.777doc.com/doc-2584522 .html