Huffman编码问题

1、第二章 Huffman编码问题 17第二章 Huffman编码问题2.1. 问题描述2.1.1 题目内容利用哈夫曼编码对数据进行无损压缩，实现Huffman压缩的编码器和译码器。2.1.2 基本要求然后首先建立并分析字母表，建立Huffman树。频度表建好后，就可以根据算法建立Huffman树，对读入源文件的每种字符进行Huffman编码。将得到的编码流写入到磁盘文件，并且计算压缩率。译码过程先读入被压缩的文件，将其解释为比特流，根据Huffman树，对比特流逐位译码，将译码结果逐次写入到磁盘文件。2.1.3 待测试数据表 2.1 待测试数据 字符abcde权2. 需

2、求分析2.2.1 程序所能达到的基本功能程序的主要功能是利用哈夫曼编码对数据进行无损压缩，实现Huffman压缩的编码器和译码器。具体功能有：（1）. 建立并分析字母表，对每种字符的出现频度进行统计，以频度作为建立Huffman树的权值。（2）. 建立Huffman树，并对读入的字符进行编码。（3）. 计算压缩率。（4）. 储存编码后的数据。（5）. 对已经编码的数据进行译码，建立相关文件。2.2.2 输入形式和输出值的范围 在程序中，主要有两种输入，一是手动建立权值表，程序要求用户输入用户自己想要建立的权值表的字符和对应的权重，程序根据用户的输入信息自动建立Huffman树，所以要求输入正确

3、的字符和整型权重； 二是程序在解压文件的时候要求输入文件的名字，如果该文件在程序同一个目录下则可以不输入路径，否则需输入完整的路径。程序在读入文件后会输出其中的信息，压缩后可输出得到的编码，并以将编码写入一个文件中。2.2.3 输出的形式程序中设置有两个输出，都是建立了文件流之后，分别以二进制和文本形式把编码信息和译码结果写入文件中。2.2.4 测试数据要求在程序的测试中，用户可输入少量的字符进行建表，这样可方便用户手动建树以检验程序运行的正确性2.3. 概要设计2.3.1 主程序流程及模块调用关系1. 主要流程图.字符读入与字符权重计算建立Huffman树与储存压缩数据开始开始读入文件读入各

4、字符的权重判断文件是否为空或不存在比较寻找权重最小的两个字符文件为将两个字符分别作为左右孩子接点建立 Huffman树空或不存在文件存在逐字统计权重计算从树根结点到每个叶子结点的路径得出编码计算压缩率返回相应值将文件按照一定的格式储存输出编码结果与压缩率结束结束程序图 2-1开始 解压模块流程图读入压缩文件判断文件文件为空或不存在从文件信息的开始对应到Huffman树的左右分支寻找对应的叶子接点做相应处理得到解压后的信息并输出结果结束程序图 2-22. 各模块间调用关系图编码压缩模块数据读入功能函数建立Huffman树函数字符权重计算函数主程序储存文件功能函数解压函数读入压缩文件信息

5、函数解压功能模块译码输出函数图 2-3 模块调用关系2.3.2 核心的粗线条伪码算法Algorithm main( )1. 输入任意个字符和对应的权值；2. 调用编码模块中的Huffman树建立函数，建立树；3. 读入要压缩的文件，根据所建立的Huffman树进行编码；4. 储存编码后的编码文件；5. 读取生成的编码文件；6. 根据Huffman树进行解码；7. 生成解压文件2.4. 详细设计2.4.1 实现概要设计的数据类型设计一个.h文件，它主要包含一个Huffman树中要存在的基本信息和数据类型，主要包含一个结点的结构体和一个Huffman树类，如下所示：# include<ios

6、tream># include<fstream># include<*>struct HuffmanNode /定义哈夫曼树各结点/设置一个整型weight存放结点的权值 /设置一个整型parent记录结点父亲位置/设置存放该结点的左右孩子的数据类型;class HuffmanTree /建立Huffman树类/结点的存储结构设置为*Node /设置保存各字符信息的数据类型 /用 LeafNum来记录树中的叶子结点总数HuffmanTree(); /构造函数 HuffmanTree(); /析构函数 .;2.4.2 每个操作的伪码算法.（1）建立权值表：建立权值表

7、函数（）for(j=0;j<i;j+) /在根节点中选出权值最小的两个if(为根结点) if() /判断是否比最小值要小 /确定最小的两个结点作为叶子接点 else/修改双亲结点与子结点的位置( 2 ) 利用已有的Huffman树进行编码基本原理：首先找到要编码的字符对应的叶子结点，然后找到其父亲结点，判断，如果自己是左子树(Lchild)则生成代码0,如果是右子树(Rchild)则生成代码1,这样依次向上,计算到根结点, 最后将依次得到的代码进行依次翻转(Reverse)计算,最终得到Humman编码。概要的伪代码如下：Huffman编码函数（）Fread()读入要编码的文件的字符wh

8、ile(Treek!='0') /对每一个字符编码直到字符串结束 设定整型变量 i j k ; for(i=0; i<LeafNum; i+)求出该文字所在单元的编号; (如果Infoi=Treek 则把i的值付给j)； while(Nodej.parent!=-1)/结点j非树根非根结点j的双亲结点的位置信息付给j;如果Nodej是左子树（Nodej = = 1），则生成代码0; 否则生成代码1(codestart+='1'); 最后设置串结束符codestart='0' for(i=0; i<start/2; i+)对二进制序列进

9、行翻转； j=codei; codei=codestart-i-1; codestart-i-1=j; 储存代码函数（）储存代码.(3). 译码伪算法与编码相反，译码是从Huffman树的根结点开始向下计算，程序首先从储存编码的文件中依次读取编码后的代码，如果遇0则向左走，寻找根结点的左子树，如果遇1则向右走寻找它的右子树，直到叶子结点则停止，然后记录该结点的字符数据，该字便是要求的译码。伪算法如下：解码函数（） while(fip2.get(ch) /读取文件内容 BitStrk=ch;/读取 /设置k的值使之指向下一个编码的地址 /关闭文件 .while(BitStri!='0&#

10、39;)/解码 如果有右自树即BitStri='1' j=Nodej.rchild;/往右右子树走 else j=Nodej.lchild;/往左子树走 if(Nodej.rchild=-1) /到叶子结点 cout<<Infoj; /输出叶子结点对应的字符 fop<<Infoj;/把译码结果储存到文件中 /重新设置使从根结点开始重新往下继续搜索 i+; .2.4.3 主程序和其它模块的伪码算法.主函数开始便调用菜单函数，然后依次调用各个功能函数。如下“函数调用关系”中所示，这里就不再重复说明了。2.4.4 函数调用关系在函数的调用中我们使用一个swit

11、ch语句实现主函数对各个功能函数的调用，如下所示：while(1) menue();cout<<"t请选择操作:"cin>>c;switch(c)case '*': /输入操对应选项，调用具体的功能函数/调用对应操作;Break;case '*': /调用相应操作； break; case '*': case '退出选项':cout<<"Quit."<<endl;exit(0); /退出程序return 0; 2.5. 调试分析2.5.1 设计

12、与调试过程中遇到的问题及分析、体会(1). 压缩之后没有代码生成程序是在先建立好了权值表之后再读入文件进行压缩的，在把压缩文件的代码完成之后，调试，出现了问题，完全得不到代码，而储存代码的文件也已经生成。发现问题后，首先考虑到的是文件的写入可能有问题，于是检查调试文件的写入代码段，结果并没有发现问题，进而想到了Huffman 树的建立是否正确，参照书上的算法思想逐步检查，最终解决了问题。原问题程序如下：for(i=WeightNum;i<2*WeightNum-1;i+) . for(j=0;j<i;j+) if(Nodej.parent=-1)/判断是否为根结点 if(Nodej

13、.weight<max1)/判断是否比最小值要小 判断并调整i, j, 的值，确定最小值与次小值 else if(Nodej.weight<max2) /修改次小值编号 Nodepos1.parent=i; /修改parent结点的位置 Nodepos2.parent=i; Nodei.lchild=pos1; /修改child结点位置 Nodei.rchild=pos2;/*注：以下程序是发现问题之后添加上的，因为少了以下语句，程序在合并结点的时候只能找到两个结点，而无法循环下去把所有的结点都合并到Huffman 树上来。*/ Nodei.parent=-1; /下一个结点为根结

14、点Nodei.weight=Nodepos1.weight+Nodepos2.weight;/这个结点的权重设置为它的两个child的权重的和(2). 解码得到的字符与原文件的字符不同可以成功编码且能编码正确后，编写了最后一个功能函数，解码函数，但是开始并没有预料的那样成功，得到解码内容后，仔细与原文件内容对比，结果发现出现了很大的偏差如下图所示，译码失败！但经过多次细心检查，纠正了下列代码：if(BitStri='1') j=Nodej.lchild; else j=Nodej.rchild;if(Nodej.rchild=-1).纠正为:if(BitStri='1&

15、#39;) j=Nodej.rchild;else j=Nodej.lchild;if(Nodej.rchild=-1).图 2-4（压缩前）图 2-5 （解压后）以上是程序编写过程当中诸多问题的几个典型，虽然得到了一定的解决，但程序任然还有很多不足和需要改进和完善的地方，须更加的努力，从以上诸多问题中我知道了书本知识与实际操作的结合任是一个还很困难的过程，需要不断的锻炼和学习。2.5.2 主要和典型算法的时间复杂度的分析建立Huffman树算法的时间复杂度分析：所有根结点的数设为n，则需要通过n-1 次合并才能建立Huffman树，而得到树的深度为n ，所以全部操作的时间复杂度应该为O(n2

16、)(n的平方)。编码算法的时间复杂度的分析：设需要编码的字符有n 个，每个字符编码的时间复杂度为O(n), 而编码之后需要作生成代码的翻转n/2 次，所以最后得出时间复杂度为O(n3).解码算法的时间复杂度为： n2.6. 使用说明进入程序界面，程序给用户提供了四个可选择的操作分别为建立权值表；压缩文件； 解压文件； 退出程序。如图6-4所示。当选择功能1时，用户便能开始进行权值表的建立，如图2-6所示，设定想要输入的表长后用户按照提示依次输入各个字符和它的权重，输入完成后，程序根据用户的输入自动建立Huffman树，如果建树成功就在屏幕上显示出“Huffman树建立成功”字样。图 2-6 图

17、 2-7 当用户选择功能2后，进入第二个功能，文件的压缩。如图2-8所示，程序提示用户输入要压缩文件的名称，要注意的是，如果文件与该程序在同一个目录下，则可直接输入文件的名称进行压缩，如果不是，则要输入完整的路径和文件名，否则会提示打开文件失败！用户正确输入文件名后，程序自动将其依照所建的Huffman树进行编码，同时输出文件的信息、编码完成后计算得出的压缩率与得到的编码后的代码。图2-8 当用户选择功能3后，进入第三个功能如图 2-9所示。要注意的是，功能3必须要在上述功能即编码功能实现后才能使用。该功能是将编码得到的文件进行译码，并把所得出的字符信息输出到屏幕上，以便用户审阅，同时将得到的字符信息保存到Text.txt 文件中去。图2-9当用户选择4后，程序结束并自动退出。2.7. 测试结果(1). 文件压缩测试及结果首先建立一个简单的权值表，其中只有a b c d e 四个数，然后输入一个要压缩的文件的