Huffman压缩试验报告（文档）.pdf

05调试分析与结果.18五总结.22Huffman 压缩软件实验报告2一问题描述一问题描述用 Huffman 编码设计一个压缩软件，要求能对输入的任何类型的文件进行 Huffman 编码，产生编码后的文件压缩文件；也能对输入的压缩文件进行译码，生成压缩前的文件解压文件。二基本要求二基本要求1、初始化：能够对输入的任意长度的字符串 s 进行统计，统计每个字符的频度，并建立 Huffman 树。2、建立编码表：利用已经建好的 Huffman 树进行编码。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：利用已经建好的 Huffman 树对编码后的字符串进行译码，并输出译码结果。5、要求编码/译码的效率尽可能的高。6、用户界面可以设计为“菜单”方式：能够进行交互。三工具三工具/准备工作准备工作在开始做实验之前，应回顾或复习 c+相关内容。需要一台计算机，其中安装有 VC6.0、VC+2005、VC+2005 Express、DEV-C+或 MinGW Developer Studio 等集成开发环境软件。Huffman 压缩软件实验报告3四分析与实现四分析与实现1概要分析概要分析本次实验采用将字符用长度尽可能短的二进制数位表示的方法，即对于文件中出现的字符，无须全部都用 8 位的 ASCII 码进行存储，根据他们在文件中出现的频率不同，我们利用 Huffman 算法使每个字符能以最短的二进制字符进行存储，以达到节省存储空间，压缩文件的目的。解决了压缩需采用的算法，程序的思路已然清晰：1统计需压缩文件中每个字符出现的频率。2将每个字符的出现频率作为叶子结点构建 Huffman 树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的 0、1 序列，这样便完成了 Huffman 编码，将每个字符用最短的二进制字符表示。3打开需压缩文件，再将需压缩文件中的每个 ASCII 码对应的Huffman 编码按 bit 单位输出。4文件压缩结束。5打开需要解压的文件，读取压缩文件中的数据，生成解码信息，输出到文件。6文件解压结束。Huffman 压缩软件实验报告42算法详细分析算法详细分析（1）构造）构造 Hufffman 树的方法树的方法HuffmanHuffman算法算法I.根据给定的 n 个权值w1,w2,wn，构造 n 棵只有根结点的二叉树，令起权值为 wj。II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。III.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。IV.重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。对于 Huffman 的创建算法，有以下几点说明：a)这里的 Huffman 树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。b)将各个字符的编码存储在一个数组 charCodes 中，为了能快速找到一个字符的编码，用函数（*CharIndex）来实现字符位置的映射，使用先序遍历二叉树的方法来求各个字符的编码方案。c）采用小顶堆的方式来存储各个二叉树的根，实际是存储指向根结点的指针。Huffman 压缩软件实验报告5（2）压缩过程的实现）压缩过程的实现压缩过程的流程是清晰而简单的：1 创建 Huffman 树2 打开需压缩文件3 将需压缩文件中的每个 ASCII 码对应的 Huffman 编码按 bit 单位输出4 文件压缩结束。其中，步骤 1 和步骤 3 是压缩过程的关键。a)a)步骤步骤 1:1:这里所要做工作是得到 Huffman 数中各叶子结点字符出现的频率并进行创建。b)b)步骤步骤 3:3:将需压缩文件中的每个 ASCII 码对应的 Huffman 编码按 bit 单位输出，这是本压缩程序中最关键的部分。需定义一个字符缓存器 BufferType，以便自动将比特转化为字节。struct BufferTypechar ch;unsigned int bits;（3）解压过程类似压缩过程的实现）解压过程类似压缩过程的实现（4）输出部分）输出部分1)每个字符所对应的HuffmanCode的比特位长度不等长，不可少输，多输，输错任何一位，后一个字符的HuffmanCode要紧跟在前一个字符的HuffmanCode后面。Huffman 压缩软件实验报告6 2)最后一个要输出的HuffmanCode的最后一位，它恰好是位于最后一个有效字符的第一位，剩下的七个空位是要用无效的HuffmanCode加以填充。否则，如果填充的HuffmanCode亦为某个ascii字符的HuffmanCode时，那么在解压缩时，则该在原被压缩文件中不存在的字符便会无中生有的在解压后的文件中出现，这显然是不正确的，应在程序中加以处理。（5）main 函数部分函数部分 N Y N Y开始是否成功输入要打开文件名称是否找到文件将文件中的值作为叶子结点构建 Huffman 树实现 Huffman 编码输出字符到压缩/解压文件文件压缩/解压结束，关闭打开的文件返回Huffman 压缩软件实验报告73代码实现代码实现Huffman 树结点的抽象基类模板树结点的抽象基类模板类型类型成员功能virtualvirtual WeightTypeWeightType Weight()=0Weight()=0返回权值返回权值virtualvirtual boolbool IsLeaf()=0IsLeaf()=0判断结点是否为叶子节点判断结点是否为叶子节点virtualvirtual MyHuffmanNode*MyHuffmanNode*Left()=0Left()=0返回结点的左孩子返回结点的左孩子函函数数模模板板virtualvirtual MyHuffmanNode*MyHuffmanNode*Right()=0Right()=0返回结点的右孩子返回结点的右孩子virtualvirtual voidvoid SetLeft(MyHuffmanNodeCharType,WeigSetLeft(MyHuffmanNode*child)=0htType*child)=0设置结点的左孩子设置结点的左孩子virtualvirtual voidvoid SetRight(MyHuffmanNodeCharType,WeiSetRight(MyHuffmanNode*child)=0ghtType*child)=0设置结点的右孩子设置结点的右孩子Huffman 树叶子节点派生类模板树叶子节点派生类模板类型类型成员功能CharTypeCharType chch结点内容结点内容数据成员数据成员WeightTypeWeightType weightweight结点权值结点权值MyLeafNode(constMyLeafNode(const CharTypeCharType&ch,&ch,constconst WeightTypeWeightType&w)&w)构造函数构造函数Huffman 压缩软件实验报告8virtualMyLeafNode()virtualMyLeafNode()析构函数析构函数CharTypeCharType Char()htType*child)=0Char()htType*child)=0返回叶子节点的字符返回叶子节点的字符函函数数模模板板WeightTypeWeightType Weight()Weight()返回权值返回权值boolbool IsLeaf()IsLeaf()判断结点是否为叶子节点判断结点是否为叶子节点MyHuffmanNode*MyHuffmanNode*Left()Left()、MyHuffmanNode*MyHuffmanNode*Right()Right()返回结点的左右孩子返回结点的左右孩子voidvoid SetLeft(MyHuffmanNodeCharType,WeigSetLeft(MyHuffmanNode*child)htType*child)、voidvoid SetRight(MyHuffmanNodeCharType,WeiSetRight(MyHuffmanNode*child)ghtType*child)设置结点的左右孩子设置结点的左右孩子Huffman 内部结点派生类模板内部结点派生类模板类型类型成员功能MyHuffmanNodeMyHuffmanNode *lChild*lChild、MyHuffmanNodeCharType,WeiMyHuffmanNodeghtType *rChild*rChild结点的左右孩子结点的左右孩子数据数据成员成员WeightTypeWeightType weightweight结点权值结点权值MyNode(MyHuffmanNodeCharType,WeighMyNode(MyHuffmanNodetType *l,*l,MyHuffmanNodeMyHuffmanNode *r,*r,constconst WeightTypeWeightType&w)&w)通过左右孩子以及权值构造通过左右孩子以及权值构造HuffmanHuffman 树内部结点树内部结点virtualMyNode()virtualMyNode()析构函数析构函数函函数数WeightTypeWeightType Weight()Weight()返回权值返回权值Huffman 压缩软件实验报告9模模板板boolbool IsLeaf()IsLeaf()判断结点是否为叶子节点判断结点是否为叶子节点MyHuffmanNode*MyHuffmanNode*Left()Left()、MyHuffmanNode*MyHuffmanNode*Right()Right()返回结点的左右孩子返回结点的左右孩子voidvoid SetLeft(MyHuffmanNodeCharType,WeigSetLeft(MyHuffmanNode*child)htType*child)、voidvoid SetRight(MyHuffmanNodeCharType,WeiSetRight(MyHuffmanNode*child)ghtType*child)设置结点的左右孩子设置结点的左右孩子Huffman 树类模板树类模板类型类型成员功能MyHuffmanNode*MyHuffmanNode*rootroot根结点根结点数据数据成员成员StringString *charCodescharCodes字符编码信息字符编码信息MyHuffmanNode*MyHuffmanNode*curCodecurCode指向当前结点指向当前结点intint numnum 叶子结点的个数叶子结点的个数函函数数模模板板unsignedunsigned int(*int(*CharIndex)(constCharIndex)(const CharTypeCharType&)&)字符位置映射字符位置映射voidvoid CreatCode(MyHuffmanNodeCharType,WeCreatCode(MyHuffmanNodeightType *r,char*r,char code,intcode,int len=0)len=0)生成字符编码生成字符编码voidvoid Clear(MyHuffmanNodeCharType,WeightClear(MyHuffmanNodeType *r)*r)清空树清空树Huffman 压缩软件实验报告10MyHuffmanTree(CharTypeMyHuffmanTree(CharType ch,WeightTypech,WeightType w,intw,int n,unsignedn,unsigned intint (*ChIndex)(const(*ChIndex)(const CharType&)CharType&)构造函数构造函数virtualMyHuffmanTree()virtualMyHuffmanTree()析构函数析构函数StringString Encode(CharTypeEncode(CharType ch)ch)编码编码LinkListDecode(StringLinkListDecode(String strCode)strCode)解码解码Huffman 压缩类压缩类类型类型成员功能MyHuffmanTreechar,unsignedMyHuffmanTreelong *pMyHuffmanTreepMyHuffmanTreeHuffmanHuffman 树树数据数据成员成员ifstreamifstream infpinfp、ofstreamofstream outfpoutfp输入输出文件流输入输出文件流BufferTypeBufferType bufbuf字符缓存器字符缓存器voidvoid Write(unsignedWrite(unsigned intint bit)bit)向文件中写入信息向文件中写入信息函函数数模模板板voidvoid WriteToOutfp()WriteToOutfp()强制向文件写入信息强制向文件写入信息MyHuffmanCompress()MyHuffmanCompress()构造函数构造函数MyHuffmanCompress()MyHuffmanCompress()析构函数析构函数voidvoid Compress()Compress()压缩压缩voidvoid Decompress()Decompress()解压解压说明：在小顶堆的实现中要求各元素的大小，因为应重载关系运算符，然而重载运算符的操作数应包含非基本类型，不能全部是指针类型，为此定义一个辅助类结构模板如下：Huffman 压缩软件实验报告11templatestruct MyHuffmanNodeHelpMyHuffmanNode*ptr;4源程序源程序系统中主要函数模板代码实现：系统中主要函数模板代码实现：/生成字符编码生成字符编码templatevoid MyHuffmanTree:CreatCode(MyHuffmanNode*r,char code,int len)if(r=NULL)return;if(r-IsLeaf()/如果是叶子节点，则存储编码CharType ch=(MyLeafNode*)r)-Char();codelen=0;String strCode(code);charCodes(*CharIndex)(ch)=strCode;else/否则分别向左右两边搜索codelen=0;CreatCode(r-Left(),code,len+1);/向左分支搜索codelen=1;CreatCode(r-Right(),code,len+1);/向右分支搜索/构造构造 Huffman 树树templateHuffman 压缩软件实验报告12MyHuffmanTree:MyHuffmanTree(CharType ch,WeightType w,int n,unsigned int(*ChIndex)(const CharType&)CharIndex=ChIndex;/字符位置映射num=n;charCodes=new Stringnum;MinPriorityHeapQueueMyHuffmanNodeHelp minHeap;/小顶堆int i;for(i=0;inum;i+)MyHuffmanNodeHelp tmp;tmp.ptr=new MyLeafNode(chi,wi);/生成叶子结点minHeap.InQueue(tmp);/入栈for(i=0;inum-1;i+)MyHuffmanNodeHelp t,t1,t2;minHeap.OutQueue(t1);/出栈minHeap.OutQueue(t2);/出栈/生成新的结点t.ptr=new MyNode(t1.ptr,t2.ptr,t1.ptr-Weight()+t2.ptr-Weight();minHeap.InQueue(t);/新的结点入栈MyHuffmanNodeHelp r;minHeap.OutQueue(r);root=r.ptr/根结点curCode=root;char*code=new charnum;CreatCode(root,code);/生成编码delete code;Huffman 压缩软件实验报告13/编码编码templateString MyHuffmanTree:Encode(CharType ch)return charCodes(unsigned int)(*CharIndex)(ch);/译码templateLinkList MyHuffmanTree:Decode(String strCode)LinkListcharList;for(int pos=0;posLeft();/如果为 0 则向左分支搜索elsecurCode=curCode-Right();/否则向右分支搜索/如果到达叶子结点则说明译码完成，记录译码结果if(curCode-IsLeaf()charList.Insert(charList.Length()+1,(MyLeafNode*)curCode)-Char();curCode=root;return charList;/向目标文件写入一个比特向目标文件写入一个比特void MyHuffmanCompress:Write(unsigned int bit)buf.bits+;/缓存比特数自增 1buf.ch=(buf.ch0)for(unsigned int i=0;i8-len;i+)Write(0);/压缩文件压缩文件void MyHuffmanCompress:Compress()char infName256,outfName256;/文件名L1:cout请输入需要压缩的文件名:;cininfName;infp.open(infName,ios:out);/打开目标文件if(!infp)/打开文件失败cout打开文件失败!endl;goto L1;infp.get();if(infp.eof()/如果文件为空则提示用户cout文件为空!endl;goto L1;L2:cout请设置压缩后的文件名称:;cinoutfName;/压缩目标文件outfp.open(outfName,ios:in);Huffman 压缩软件实验报告15if(!outfp)/打开文件失败cout打开文件失败!endl;goto L2;cout正在处理，请稍后.endl;const unsigned long n=256;/字符个数char chn;/字符数组unsigned long wn;/字符权值unsigned long i,size=0;char tmpCh;for(i=0;in;i+)chi=(char)i;/初始化字符值wi=0;/初始化权值infp.seekg(0,ios:beg);/使文件指针指向文件开始处tmpCh=infp.get);/从文件中读取一个字符while(!infp.eof()w(unsigned int)(unsigned char)tmpCh)+;/字符 tmpCh 的频度自加一size+;/文件大小加一tmpCh=infp.get();/读取下一个字符infp.close();/关闭文件if(pMyHuffmanTree!=NULL)delete pMyHuffmanTree;pMyHuffmanTree=new MyHuffmanTree(ch,w,n,CharIndex);outfp.write(char*)&size,sizeof(unsigned long);/向文件中写入源文件的大小for(i=0;iEncode(tmpCh);/编码信息for(i=0;i(unsigned int)strTmp.Length();i+)/向文件中写入信息if(strTmpi=0)Write(0);elseWrite(1);tmpCh=infp.get();WriteToOutfp();/强行写入目标文件infp.close();outfp.close();cout压缩结束.endl;/解压文件解压文件void MyHuffmanCompress:Decompress()char infName256,outfName256;/文件名L1:cout请输入压缩文件名:;cininfNameinfp.open(infName,ios:out);/打开文件if(!infp)/打开文件失败cout打开压缩文件失败!endl;goto L1;infp.get();if(infp.eof()cout压缩文件为空!endl;Huffman 压缩软件实验报告17goto L1;L2:cout请设置解压后文件的名称:;cinoutfName;outfp.open(outfName,ios:in);/打开文件if(!outfp)cout打开文件失败!endl;goto L2;cout正在处理，请稍后.endl;const unsigned long n=256;char chn;unsigned long wn;unsigned long i,size=0;char tmpCh;infp.seekg(0,ios:beg);/使文件指针指向文件开始处infp.read(char*)&size,sizeof(unsigned long);/读取目标文件大小for(i=0;in;i+)chi=(char)i;/初始化 chinfp.read(char*)&wi,sizeof(unsigned long);/读取字符频度if(pMyHuffmanTree=NULL)delete pMyHuffmanTree;pMyHuffmanTree=new MyHuffmanTree(ch,w,n,CharIndex);/建立 Huffman 树unsigned long len=0;tmpCh=infp.get();while(!infp.eof()/对压缩文件进行解码，并将解码后的字符写入目标文件String strTmp=;unsigned char c=(unsigned char)tmpCh;for(i=0;i8;i+)/将 c 转换成二进制类型的串if(c128)Concat(strTmp,0);Huffman 压缩软件实验报告18else Concat(strTmp,1);c=1;LinkList Text=pMyHuffmanTree-Decode(strTmp);/对串进行译码String str(Text);for(i=0;i(unsigned long)str.Length();i+)len+;/目标文件长度加一outfp.put(stri);/写入目标文件if(len=size)break;if(len=size)break;tmpCh=infp.get();/取出下一个字符infp.close();/关闭文件outfp.close();cout处理结束.endl;/主测试函数主测试函数int main(int argc,char*argv)system(color F3);char flag;/欢迎界面coutttendl;couttt Huffman 压缩 endl;couttt endl;couttt(a)添加压缩文件 endl;couttt endl;couttt(b)解压文件 endl;couttt endl;Huffman 压缩软件实验报告19couttt(c)退出 endl;coutttendl;while(cinflag)switch(flag)case a:MyHuffmanCompress compress;compress.Compress();/压缩break;case b:MyHuffmanCompress compress;compress.Decompress();/解压break;case c:cout;system(PAUSE);return 0;cout;return 0;5调试分析与结果调试分析与结果测试数据：测试数据：I love Computer。I will try my best to study it.程序运行的界面如下，通过用户输入指令运行。可用的指令有如下几条：选项选项 a：添加压缩文件Huffman 压缩软件实验报告20选项选项 b：解压文件选项选项 c：退出程序添加压缩文件：添加压缩文件：Huffman 压缩软件实验报告21解压文件：解压文件：将测试数据记录在名为将测试数据记录在名为 Source.txtSource.txt 的文件里：的文件里：Huffman 压缩软件实验报告22压缩之后的内容写入压缩之后的内容写入 Compress.txtCompress.txt 的文件里：的文件里：解压之后的结果存放在解压之后的结果存放在 Decompress.txtDecompress.txt 的文件里：的文件里：Huffman 压缩软件实验报告23由测试截图可以看出，解压之后文件夹 Decompress.txt 文件夹内的内容跟测试数据文件夹 Source.txt 内的内容相吻合，说明了程序的正确性。五总结五总结利用 Huffman 树进行编码进行文件的压缩,这一思想在多媒体技术基础课程里我有接触到,好在当时学的还不错,所以在构建 Huffman树和编码这一过程还是很容易接受的。困难就在于怎么构造出函数，构造出一个工程，做出一个能够顺利实现压缩的程序。这是动手能力，实践能力，需要长时间的编程训练作为基础。数据结构是计算机程序设计的重要理论技术基础，是计算机学科的核心课程之一。它将各个抽象的数据之间的关系建立起来，无论是线性的、循环的还是分支的，都是为了建立一种方便程序的实现和运行的结构，使得数据之间不再是孤立的。它能使得我们在编程时在脑海中显现更为清晰的数据关系画面。而且在学习数据结构时Huffman 压缩软件实验报告24我们更应该联系所属语言（我们所学的是 C+语言版）的特性，这样才能更好的理解数据结构的思想体系。总的来说，这次实验带来的收获是很大的，提取文件数据、分析数据、构建 Huffman 树、替换数据对文件进行压缩、输出文件，一次大的实验几乎运用到了我们一学期所学的所有知识。经过分、析调试和了解程序的代码，巩固了上课学习的知识。