基于哈夫曼树的文件压缩解压程序－示例文档.doc

该【基于哈夫曼树的文件压缩解压程序－示例文档 】是由【碎碎念的折木】上传分享，文档一共【45】页，该文档可以免费在线阅读，需要了解更多关于【基于哈夫曼树的文件压缩解压程序－示例文档 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。软件课程设计报告基于哈夫曼树的文件压缩/解压程序计算机科学学院××专业××班××号×××2009-10-,实现文件的压缩与解压并计算压缩率,:基于哈夫曼编码的文件压缩实用程序系统B软件组成::Windows2000sp4BorlandC++Builder6Dev-C++-32D运行环境:dos/win98/winMe/win2K/winxpE性能特点:~~体积小~高效快捷~适用范围广。~界面友好~使用方便。,256叶子,进行哈夫曼编码~~速度比一般算法高75%以上3(可压缩最大体积为4G的文件~%5(压缩过程中显示压缩进度并有相关信息提示6(,(.voidHaffman(intnodeCode,intlength,intsum,vector<pair<int,int>>&hfmCode,vector<int>&lchild,vector<int>&rchild)哈夫曼树编码递归函数,(voidindexSearch(intnodeCode,vector<int>&lchild,vector<int>&rchild,vector<int>&index,vector<int>&code)索引编码递归函数,(voidmakeIndex(intnodeCode,int&tt,vector<int>&index,int&indexNum,list<int>&code,vector<int>&lchild,vector<int>&rchild)索引解码递归函数,(press()压缩函数press()解压缩函数,(windows版本程序下的新增函数,(AnsiStringShowNowTime()计算当前时间(精确到毫秒,以字符串返回)。,.voidsearch(intnodeCode,int&i,vector<int>&lchild,vector<int>&rchild)递归计算每个节点的X坐标,.voidsearchdraw(intnodeCode,intheight,vector<int>&lchild,vector<int>&rchild)递归做图函数,.void__fastcallTForm1::Paga1OnDrawTab(TCustomTabControl*Control,intTabIndex,constTRect&Rect,boolActive)PageControl的标签页的色彩描绘,(void__fastcallTForm1::CompareFiles(TObject*Sender)文件比对函数当然还有一些相关按钮的响应函数,在此不在赘述,详见程序清单部分3,(:8文件由若干个字节组成~一个字节有8bits~故有2=256种字节构成形-255。按此256种字节出现频率可构造haffman树进行式~对应字节码为0重新编码~编码后每字节的新编码平均长度将<=8bits~将每个字节对应了压缩编码写到新文件中~从而达到压缩文件的目的。B哈夫曼树构造算法:用数组intfre[0..255]表示第0号至第255号字节节点的出现频率~找出最小的fre[a]与fre[b]~则构建第256号节点~其左孩子为a号节点~右孩子为b号节点~不妨用数组记录:left[256]=a,right[256]=b。fre[256]=fre[a]+fre[b].删除a,b节点。然后~再在剩下的节点中找出最小的fre[a]与fre[b],构建第257号节点~再删除a,b节点。由此~每做一次~新生成一个节点~删除两个节点~即减少一个节点。因而在做255次后~最后的第510号节点即为haffman树的根节点。又由left[]与right[]数组~该haffman树得到确定。C关于B部分的优化1(每次都得找最小的频率节点~所以存放节点的容器最好是已经排过序的~这样取最小的节点就非常方便了~但新生成的节点就得按顺序插入到该容器中~如果用顺序表则需要查找插入位置~比较费时——本程序采用满足以上条件的最适合容器类:STL,标准模板库,下的Set集合类~它1以二叉排序树形式存储元素~有效地解决了这个问题。2(某些节点的频率可能为0~,例如英文文档~字节码即ASCII码~在0-127之间~故fre[128..255]一般均为0,~此时~就没有必要将这些频率为0的节点加入到哈夫曼数中~因为它们在文件中没有出现~无须重新编码。D哈夫曼编码结构及算法哈夫曼树构造完毕之后~可以利用递归算法遍历该树~给每个叶子编码~如左图:A编码为0~B为编码100~C为101~D为11。直观上这样的编码可以用字符串表示~但这样给写入编码到压缩文件造成了困难~因为这涉及到字符串的拆分问题,时间上不允许。进而~可以用一个整形数组来表示一个编码例如code[B][0]=1,code[B][1]=0,code[B][2]=1即可表示B节点的编码~这样取某位压缩代码比较方便~但是因而所有叶子的编码实际上是一个二维数组~空间消耗比较大。《TheC++StandardLibrary---ATutorialandReference》第157页5在此~现提出新的编码存储结构~一个编码用两个整形数表示~第一个数来表示编码长度~例如code[B].Length=3,第二个数表示编码的十进制值~因为101=5所以code[B].Dec=5。这样极大地节省了空间。但似乎这样[2][10]会给向压缩文件写入编码带来麻烦~难道还要把Dec值再转换为101才能写到文件中,事实上不需要~而且在速度上反而比前面的结构更快。关于使用此种编码结构在速度上的优势~将在后面详细解释。E压缩编码写入算法——一级32位缓冲器算法Cpu与i/0设备通讯是并行处理的办法~最小处理单元是一个字节~即8bist,所以希望以bit为单位将编码写到压缩文件中这在硬件上就是不可能的~C++语言也更不可能提供有关的语句了。因而我们要设置一个缓冲区~当缓冲区中编码达到或超过8bits时~将前8bits做为一个byte写出到压缩文件中。如果编码存储结构是字符串~那么缓冲区也自然是一个字符串~写入文件时涉及到字符串与数字的转换~效率上是很不划算的。如果编码存储结构是整型数组~那么缓冲区实际上就是一个数值t,t初始值为0~此时读入压缩编码的第一bit加到t中~然后t左移一位,再读一t左移一位,8次之后~t已经达到8位~将t,此bit压缩编码~加到t中~时t是一个〈=255整数~正好是一个字节〉写出到压缩文件中即可。这是绝大多数人的方案。但是本软件的压缩编码是用两个整型数字表示的~无法取得某个bit的值~应该怎么办呢,在VC,C++builder和=dev-c++这些著名的编译器中~int型是32bits~也就是定义inta后~a本身就成了一个绝佳的32位缓冲器[在本设计中~称之为一级缓冲器]。如前所说~缓冲器8位就够了~a作为32位缓冲器,前面8位可用来缓冲输出~而后面的24位又为一次性向缓冲器输入压缩代码提供了空间~因为哈夫曼树的深度一般不会超过25层,参见附录1,~这样32位缓冲器既给压缩代码的输出提供了方便又给其输入提供了方便。下面就一个具体事例来比较说明。例如A的编码为**********~B的编码为1111**********按整型数组的存储和8位缓冲方案编码~则先读A的每位代码~达到8位时输出byte=10000000,再按位读入3位A的剩余编码111~然后按位读入5位B的编码11111~输出byte=11111111,以此类推~既而输出0111111~而B的最后2位与下面的字节编码再合成输出。而用双整数存储和32位缓冲器方案编码~则可一次性将A的编码(code[A].Dec)读入到缓冲器中,即缓冲器a+=code[A].Dec,,此时缓冲器容量为11位~11>8~输出前8位,用&操作可屏蔽掉后24位,~此时缓冲器清除前8位,a=a<<8,,然后一次性读入B的代码置入a中~此时a容量为3+15=18位~此时输出前8位~现在a=10位仍然大于8,在输出8位~剩余2位与下面的编码继续组合输出。显然~无论在运算时间上和存储空间上~后者均占明显优势。当然后者12出现了&与<<运算~而这样的运算相当于汇编语言的AND与SAL指令~是非常高效迅速的~比从内存读编码快捷~且操作次数也少的多。1王浩《面向对象程序设计》35-36页2沈美明温冬蝉《ibm-pc汇编语言程度设计》61-62页6F写入算法另一角度的优化——使用二级1024K缓冲器在写入编码的过程中~宏观的过程是:以字节形式读取原文件~然后找到该字节的编码~进而以字节形式写到压缩文件中去。不停的字节读写会给cpu带来频繁的中断并且硬盘的磁头来回在磁道扇区中移动~减慢了速度。1~减少了cpu中而如果以数据块的形式读写则可以有效地利用到DMA通讯断~并使硬盘磁头连续移动~显著加快了速度。而c++语言的iofstream类的read,,与write,,成员函数为此思想的实现提供了可能。所以~可以开辟一个1024K的缓冲区~先将文件前1024K的字节读入内存缓冲区中,在本设计中~这称为二级缓冲器,~编码后的字节也不急于写入文件中~而是先写到另一个二级缓冲区中~当其足够1024K时再以数据块的形式写到压缩文件中。然后清空缓冲区~继续做下一个1024K的编码写入。而缓冲区本身~其实就是二个整形数组~read_buffer[1048576]和write_buffer[1048576]。不过这样的数组声明已经太大了~可以用STL的vector向量类来代替这个数组,vector结构实际也就是一个封装了的加强型数组,。一级缓冲器在微观上解决了写编码速度的问题~而二级缓冲器则在宏观上改善了写编码的问题~两者关系的嵌套的关系~实际的程序主结构也就是一个二重循环~外层控制二级缓冲器~内层控制一级缓冲器。G一些细节问题采用以单字节为单位构造哈夫曼树~这样数的规模不会太过庞大~构造的时间比较快~并且有比较良好的压缩率,详细的压缩报告见附录二,。如果以双字节构造~则可能出现叶子数为65536的哈夫曼树~虽然压缩率可以得到相对提高~但已经提升不明显~而整个的压缩过程将变的缓慢。如果进行智能识别频率采样~一方面采样过程又要花费一定的时间~另一方面~哈夫曼树本身的结构也决定了这样做并不划算~也给解压缩和写入索引带来了许多麻烦。用left[]和right[]数组来描述一颗二叉树而没有用指针~是为了避免指针可能带来的由叶子到根的反向建树的麻烦,另一方面~树的节点和叶子数目基本确定~没太多必要使用灵活的指针和相关的内存分配语句。编码写出后~内层缓冲器可能剩几个bit~没有达到8bit,此时应补‘0’或‘1’以凑齐8位再写出。文件的大小也不大可能正好被1024K整除~要考虑到最后的剩余部分字节的编码~即要计算好最后的实际字节读取个数~fstream的成员函数2gcount()能解决这个问题。如果把整个压缩过程作为一个函数的话~二级缓冲区的定义最好在函数外作为全局量定义~否则可能栈溢出。1戴梅萼史嘉权《微型计算机技术及应用》第二版199-201页2王浩《面向对象程序设计》第245页72(~”1001011101……”,哈夫曼树结构入图~先读如第一如个字节”10010111”,先取出?1?~在ABCD中均无这个编码,于是再取出?0?和刚才的?1?组成?01?~仍无此编码,再取出?0?~组成?010?~发现B叶子的