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

1、软件课程设计报告基于哈夫曼树的文件压缩/解压程序 计算机科学学院专业班号 2009-10-20一 需求分析1.课题要求（实现文件的压缩与解压并计算压缩率）A.描述压缩基本符号的选择方法B.运行时压缩原文件的规模应不小于5KC.提供恢复文件与原文件相同性对比功能2.设计目标A软件名称：基于哈夫曼编码的文件压缩实用程序系统B软件组成：Winhfm.exe dosHfm.exe C制作平台及相关调试工具： Windows2000sp4 Borland C+ Builder 6Dev-C+ 4.9.6.0 UltraEdit-32D运行环境：dos/win98/winMe/win2K/winxpE性能

2、特点：1. 软件由两个可执行文件组成，各具特点DosHfm.exe为dos系统应用程序，体积小，高效快捷，适用范围广。WinHfm.exe 为windows应用程序，界面友好，使用方便。2. 对单字节（256叶子）进行哈夫曼编码，压缩率良好2. 使用二级缓冲压缩/解压技术，速度比一般算法高75%以上3可压缩最大体积为4G的文件，达到Fat32文件系统极限4. 文件索引体积比常规算法小50%5压缩过程中显示压缩进度并有相关信息提示6WinHfm.exe可图形显示源文件的哈夫曼编码构造树二概要设计1.相关函数介绍 dos版本程序下的有关函数.void Haffman(int nodeCode,in

3、t length,int sum,vector pair &hfmCode,vector &lchild,vector &rchild)哈夫曼树编码递归函数void indexSearch(int nodeCode,vector &lchild,vector &rchild,vector &index,vector&code)索引编码递归函数void makeIndex(int nodeCode,int &tt,vector &index,int &indexNum,list &code,vector &lchild,vector &rchild)索引解码递归函数void Compress()

4、压缩函数void UnCompress()解压缩函数windows版本程序下的新增函数 AnsiString ShowNowTime()计算当前时间（精确到毫秒，以字符串返回）。.void search(int nodeCode,int &i,vector &lchild,vector &rchild)递归计算每个节点的X坐标. void searchdraw(int nodeCode,int height,vector &lchild,vector &rchild)递归做图函数.void _fastcall TForm1:Paga1OnDrawTab(TCustomTabControl *C

5、ontrol,int TabIndex, const TRect &Rect, bool Active)PageControl的标签页的色彩描绘void _fastcall TForm1:CompareFiles(TObject *Sender)文件比对函数 当然还有一些相关按钮的响应函数，在此不在赘述，详见程序清单部分 函数调用示意图三 详细设计1. 压缩算法部分A核心算法：文件由若干个字节组成，一个字节有8bits，故有28=256种字节构成形式，对应字节码为0-255。按此256种字节出现频率可构造haffman树进行重新编码，编码后每字节的新编码平均长度将8，输出前8位（用&操作可屏蔽

6、掉后24位），此时缓冲器清除前8位（a=a8）,然后一次性读入B的代码置入a中，此时a容量为3+15=18位，此时输出前8位，现在 a=10位仍然大于8,在输出8位，剩余2位与下面的编码继续组合输出。显然，无论在运算时间上和存储空间上，后者均占明显优势。当然后者出现了&与运算 王浩面向对象程序设计35-36页2 沈美明 温冬蝉ibm-pc汇编语言程度设计61-62页，而这样的运算相当于汇编语言的AND与SAL2指令，是非常高效迅速的，比从内存读编码快捷，且操作次数也少的多。F写入算法另一角度的优化使用二级1024K缓冲器在写入编码的过程中，宏观的过程是：以字节形式读取原文件，然后找到该字节的编

7、码，进而以字节形式写到压缩文件中去。不停的字节读写会给cpu带来频繁的中断并且硬盘的磁头来回在磁道扇区中移动，减慢了速度。而如果以数据块的形式读写则可以有效地利用到DMA通讯 戴梅萼 史嘉权微型计算机技术及应用第二版199-201页，减少了cpu中断，并使硬盘磁头连续移动，显著加快了速度。而c+语言的iofstream类的read（）与write（）成员函数为此思想的实现提供了可能。 所以，可以开辟一个1024K的缓冲区，先将文件前1024K的字节读入内存缓冲区中（在本设计中，这称为二级缓冲器），编码后的字节也不急于写入文件中，而是先写到另一个二级缓冲区中，当其足够1024K时再以数据块的形式

8、写到压缩文件中。然后清空缓冲区，继续做下一个1024K的编码写入。而缓冲区本身，其实就是二个整形数组，read_buffer1048576和write_buffer1048576。不过这样的数组声明已经太大了，可以用STL的vector向量类来代替这个数组（vector结构实际也就是一个封装了的加强型数组）。一级缓冲器在微观上解决了写编码速度的问题，而二级缓冲器则在宏观上改善了写编码的问题，两者关系的嵌套的关系，实际的程序主结构也就是一个二重循环，外层控制二级缓冲器，内层控制一级缓冲器。G一些细节问题采用以单字节为单位构造哈夫曼树，这样数的规模不会太过庞大，构造的时间比较快，并且有比较良好的压

9、缩率（详细的压缩报告见附录二）。如果以双字节构造，则可能出现叶子数为65536的哈夫曼树，虽然压缩率可以得到相对提高，但已经提升不明显，而整个的压缩过程将变的缓慢。如果进行智能识别频率采样，一方面采样过程又要花费一定的时间，另一方面，哈夫曼树本身的结构也决定了这样做并不划算，也给解压缩和写入索引带来了许多麻烦。用left和right数组来描述一颗二叉树而没有用指针，是为了避免指针可能带来的由叶子到根的反向建树的麻烦；另一方面，树的节点和叶子数目基本确定，没太多必要使用灵活的指针和相关的内存分配语句。编码写出后，内层缓冲器可能剩几个bit，没有达到8bit,此时应补0或1以凑齐8位再写出。文件的

10、大小也不大可能正好被1024K整除，要考虑到最后的剩余部分字节的编码，即要计算好最后的实际字节读取个数，fstream的成员函数gcount() 王浩 面向对象程序设计 第245页能解决这个问题。如果把整个压缩过程作为一个函数的话，二级缓冲区的定义最好在函数外作为全局量定义，否则可能栈溢出。2解压缩算法部分A.基于字符匹配的解压算法现在从已压缩过的文件中读取一段代码，如”1001011101”,哈夫曼树结构入图，先读如第一个字节”10010111”,先取出“1”，在ABCD中均无这个编码；于是再取出“0”和刚才的“1”组成“01”，仍无此编码；再取出“0”，组成“010”，发现B叶子的编码与之

11、相等，此时解码得B,输出到解码文件中，以此类推。这是最容易想到的方法，但效率很低。首先，取出一个编码后要和所有叶子的编码比对；其次，编码比对是基于字符串的比对，比较慢。对于前者的改进可以通过：1.一旦比对成功就不再和剩下的比对2.按照编码的长度之后长度相同的编码比对等等。而后者的改进则出现了B算法。B.基于数值匹配的算法既然字符比对比较慢，我们可以把编码用2个整数表示，前者是编码的十进制值，后者是编码长度。这样只和编码长度相等的十进制相比就可以了。这样把字符串的比较优化为数字比较，据测算，速度提高了约10倍。但是这两种算法都基于与叶子编码比较，相当于不断的尝试，解压速度很难突破100KB/s。

12、C.基于循径法既然所有的编码都隐藏在一个树中，那么根据遇0向左走遇1向右走的方法自然就能很容易地找到叶子，从而得到解码。仍如前例，读入”1”向右走，发现不是叶子，继续；读入”0”向左走，发现不是叶子，继续；读入”0”向左走，发现是叶子B，即可解码为B写入解码文件。也就是说，循径法充分地利用了每次读进来的编码，能够以确定的路径找到叶子而不需要尝试。不过要使用这种方法，就必须想建立一个原文件的哈夫曼树，详见索引算法部分。使用此方法后速度有极大飞跃。D.缓冲输入输出和压缩时采用1M二级缓冲相同，如果的压缩时也采用此技术，也会有很大的速度优化，当然程序也变得更加复杂。E.细节问题读入和写出仍然基于字节

13、单位，基于位的操作同样要在程序内部通过位运算完成。最后一个字节在解码时必须注意到压缩时最后一个字节是用”0”或”1”填充的，要避免多余解码，可以在索引中写入文件大小，详见下节。3文件索引算法A. 简介由解压缩的算法可知，一个压缩了的文件解压缩的前提是知道原文件的具体每个字节的编码。这些信息称为索引。上页的细节问题中提到最好在压缩后的文件中标出原文件的长度，这也是索引信息。一般索引信息放在文件的最前部分。B. 写入编码法最直接的方法就是，把每个字节的编码写到压缩后的文件中去。入图，先写入A及其编码0，接着是B及编码100,C101,D11。即：01000001 0 01000010 100 01

14、000011 101 01000100 11A B C D当然直接这样写会给阅读信息造成困难，因为计算机不知道A的编码是几位，它读入0后就不知道是否下一位究竟是A的编码还是B的ASCII的开始。所以我们还得标识出编码的长度A1 B3 C3 D2,即01000001 00000000 0 01000010 00000011 100 01000011 00000011 101 01000100 00000010 11A 长度0 B 长度3 C 长度3 D 长度2这样的确是区别开了，没有歧义，可是编码变长了，我们可以规定叶子是按顺序排列的，此时编码就变短了，即：00000000 0 00000011

15、 100 00000011 101 00000010 11A的长度 B的长度 C的长度 D的长度事实上最大一共有256个叶子，计算机依次读256次就可以了。这样索引占用的长度一般是512K左右。不过一旦一个文件只有5片叶子，也得有256个字节来标识编码长度，这在压缩只有几个字节的小文件时，反而文件会扩大几十倍。C. 写入树结构法如果我们知道原文件的哈夫曼树的结构，也自然就可获知每个叶子的编码，那么，把这棵树的结构作为索引存入文件也可以，如果树可大可小，索引的长度也会可大可小，解决了B方法索引长度始终大于256字节的问题。如上图，如果非叶子节点为#,这个树的结构编码 胡学钢 王浩 软件系列课程实

16、践教程第49页“扩展二叉树”就是”#A.#B.C.D.”而且哈夫曼树有一个性质，如果一个节点有左孩子，就一定有右孩子，如果没有左孩子，也必然没有右孩子。由此没有必要再用点号来表示叶子了，因而树结构简化成”#A#B#CD”,再用1表示叶子，0表示非叶子，则为”01001011”，这就是它的存储实现。如下：00000100 01000001 01000010 01000011 01000100 01001011有4个节点 A B C D 树结构对于一棵完整的有256个叶子的haffman树，大约需要320字节就可以存储它了。比前面的方法节省了38%。当然，要使用这种方法，就必须在压缩时用一个递归函

17、数来遍历这棵树以获得树结构编码。D.关于索引的解码AB两种建索引的方法都很方便于索引的解码，但空间占用大后者灵活性差，而若使用C方法，则索引的解码也成了问题。换句话说，我们得由“01001011”来还原出一棵haffman树。本系统是这样做的，首先得把树结构编码从文件中读到一个数组中，把叶子编号读到另一个数组中，然后由这两个数组用递归的方法造出树。然后由这棵树再求出每个叶子的编码。当然这一步可以略去了，因为解压缩采用寻径法，不需要再求每个叶子的具体编码了。E.相关细节问题为了给正文部分解码代码方便并显示解码进度，本系统在压缩的文件开头的四个字节记录了原文件的长度。索引中，节点的顺序和结构树的顺

18、序必须相同，例如都采用先序，中序或后续，本系统采用先序。索引的编码和解码都用到了递归，而递归的参数都相当多而且很多是数组，为了节省空间，要运用引用操作。4. 哈夫曼树显示算法A.简介在本系统的windows版本的程序中，有显示哈夫曼树的功能，这涉及到了计算机做图以及一些具体的算法。B.节点的布局一棵树在描绘之前必须要计算好每个节点的坐标，否则漫无目的地从头节点分左右画下去就很可能造成节点位置的重合。Y轴的坐标比较好控制，因为它有节点的深度决定了。X轴呢？本系统利用中序遍历haffman树，对叶子节点X坐标递增的方法来确定的。例如左树，中序依次遍历了ABCD，于是ABCD的横坐标就是1，2，3，

19、4。而非叶子节点的横坐标取左右孩子的横坐标的平均值，显然这是一个递归算法。C.具体的描绘知道每个节点的坐标后，就可以开始描绘了，画圆与直线的函数都有了，因而遍历所有的节点也就可以把整个树给画出来了。D. 细节问题计算坐标和描绘节点都是递归方法，因为程序的主体就是二个递归程序。由于节点众多，整个树画出来需要非常宽的幅面，大约个象素的宽度。在windows98系统中不支持如此大的幅面，而在window2000和windowsXP中支持，因而本系统作图功能不能在win98下体现甚至出现异常而终止了整个压缩程序。因而作图这一部分得使用try/catch 任常锐 黎涛C+ builder高级编程296页

20、这样的异常处理机制以确保压缩程序在各个系统的稳定运行。画出来的图比较大，一个屏幕显示不下，而仅使用滚动条又比较麻烦，因而本系统采用了“手抓”功能，可以用鼠标拖动画面。5. 文件比对算法本系统具有文件比对功能，它的算法如下：首先，如果两个文件长度不相等，显然文件不相等，无须进一步比较了。怎么知道指定的文件的长度呢？如果把文件读一遍当然可以知道它的长度，但这样太消耗时间。可以利用库的filelength函数来直接求得文件长度。如果两个文件长度相同，则可以正式比对。同样为了加快速度，在此也用了全部变量的缓冲器。文件A可以用M的读入缓冲器，文件B可以用M的写出缓冲器。然后一一对比，一旦出现不相同，则停

21、止比对，输出“不相等”,程序返回。如果均相同，则文件相等。至此，整个算法的描述都已经叙述完了，本系统采用的算法均为以上各部分的最优算法，因而程序的结构比较复杂。四 用户使用说明（略）五 测试分析（一）各种类型文件的压缩率测试文件大小压缩后压缩率%文本文件（txt）文件1（英文文本1）77465515666657文件2（英文文本2）65194351165399文件3（中文文本1）2897722216957652文件4（中文文本2）110421660885985文件5（混合文本）1679791321817869Word文档（doc）文件1（英文文本1）2618791341725123文件2（英文文

22、本2）1464321078097362文件3（中文文本1）50688308366083文件4（中文文本2）28672150905262文件5（混合文本）8376326496757760网页文件（htm,mht）文件1（无图片）431730767125文件2（有图片）5045393734417401文件3（有图片）1658321105566674幻灯片文件（ppt）文件11996801411517068文件2102912566695506电子表格文件（xls）文件133280154524643文件23584001952865448位图文件（bmp）文件1（16色文件）30827828339591

23、92文件2（256色文件）137218407552970文件3（24位真彩）4302142631756117可执行文件（exe）文件194208674537160文件26635524974007496文件3156627814593499317（二）速度测试 为避免偶然因素，本项测试选取一个600M左右（621889873 byte）的虚拟光驱文件，压缩三次，取平均值。压缩时间压缩速率解压缩时间解压缩速率第一次110.297s5506Kb/s145.359s4178Kb/s第二次107.859s5631Kb/s150.344s4039Kb/s第三次120.359s5046Kb/s141.313s

24、4298Kb/s平均值112.838s5382Kb/s145.611s4171Kb/s以上测试环境：CPU:celeron1.7GHz,内存：DDR256M,硬盘：60GB（7200rpm）,系统：windows XP.六 总结数据结构是一门重要并且艰深的课程，学好这门课既需要聪明的大脑，更需要长期的编程实践。在做本课程设计中，前前后后花了一个半月的时间。算法也是越琢磨越明白，看问题也越来越深刻，本程序共做了四次比较大规模的修改，如果没有前面Pascal与c+的基础，光修改程序的工作量就是不可想象的，其间还重写了一次原代码，可见，数据结构和程序设计是密不可分的。另外，本课程设计中，还直接或间接

25、地联系到了计算机组成原理，微机接口，汇编语言等其它相关课程，可见，计算机是一个统一的学科，没有其他课程的知识储备，仍然是不能实现本设计的。 另外在本课程设计中，我了解到了快速应用程序开发的工具borland c+ builder 6这是一个庞大的系统，我阅读很多相关的资料和网页，这种知识则是课内所学不到的。最后，感谢老师在平时对我的指导与鼓励，正是课间给我的精辟回答使我有了更为明晰的思路，才有最终的设计结果。七 附录（此部分不用打印）程序清单在此，给出winhfm.exe的程序清单。Dos版本的程序清单在此略过。#include #pragma hdrstop#include Unit1.h#

26、include Unit3.h#include #include #include #include #include #include #include #include using namespace std;#pragma package(smart_init)#pragma resource *.dfmchar inputFileBuffer1048576;char wantFileBuffer1048576;vector X(511,0);AnsiString ShowNowTime()Word H, M, S,Ms;DecodeTime(Now(), H, M, S,Ms);Ans

27、iString sH=AnsiString(H);AnsiString sM=AnsiString(M);AnsiString sS=AnsiString(S);AnsiString sMs=AnsiString(Ms);if (sM.Length()=1)sM=0+sM;if (sS.Length()=1)sS=0+sS;if (sMs.Length()=1)sMs=00+sMs;if (sMs.Length()=2)sMs=0+sMs;return sH+点+sM+分+sS+秒+sMs;void Haffman(int nodeCode,int length,int sum,vector

28、pair &hfmCode,vector &lchild,vector &rchild) if (nodeCode=-1) return; if (nodeCode=255) hfmCodenodeCode.first=length; hfmCodenodeCode.second=sum; return; Haffman(lchildnodeCode,length+1,sum*2,hfmCode,lchild,rchild); Haffman(rchildnodeCode,length+1,sum*2+1,hfmCode,lchild,rchild);void search(int nodeC

29、ode,int &i,vector &lchild,vector &rchild) if (lchildnodeCode=-1) XnodeCode=i; i+; return; search(lchildnodeCode,i,lchild,rchild); search(rchildnodeCode,i,lchild,rchild); XnodeCode=(XlchildnodeCode+XrchildnodeCode)/2;void searchdraw(int nodeCode,int height,vector &lchild,vector &rchild) if (nodeCode=

30、-1) return; if (lchildnodeCode=-1) Form3-Image1-Canvas-Brush-Color=clWhite; Form3-Image1-Canvas-TextOut(XnodeCode*20-5,height*60+14,AnsiString(nodeCode); Form3-Image1-Canvas-Brush-Color=clRed; Form3-Image1-Canvas-Ellipse(XnodeCode*20-5,height*60-4,XnodeCode*20+10+4,height*60+10+4); Form3-Image1-Canv

31、as-TextOut(XnodeCode*20-1,height*60-1,height); Form3-Image1-Canvas-Brush-Color=clYellow; if (lchildnodeCode!=-1) Form3-Image1-Canvas-MoveTo(XnodeCode*20+5,height*60+10+4); Form3-Image1-Canvas-LineTo(XlchildnodeCode*20+5,height*60+60-4); searchdraw(lchildnodeCode,height+1,lchild,rchild); Form3-Image1

32、-Canvas-MoveTo(XnodeCode*20+5,height*60+10+4); Form3-Image1-Canvas-LineTo(XrchildnodeCode*20+5,height*60+60-4); searchdraw(rchildnodeCode,height+1,lchild,rchild); void indexSearch(int nodeCode,vector &lchild,vector &rchild,vector &index,vector&code) if (nodeCode256) index.push_back(1);code.push_back

33、(nodeCode);return; index.push_back(0); indexSearch(lchildnodeCode,lchild,rchild,index,code); indexSearch(rchildnodeCode,lchild,rchild,index,code); void makeIndex(int nodeCode,int &tt,vector &index,int &indexNum,list &code,vector &lchild,vector &rchild) if (indexindexNum+=1) lchildnodeCode=code.front

34、();code.pop_front(); else lchildnodeCode=tt+; makeIndex(lchildnodeCode,tt,index,indexNum,code,lchild,rchild); if (indexindexNum+=1) rchildnodeCode=code.front();code.pop_front(); else rchildnodeCode=tt+; makeIndex(rchildnodeCode,tt,index,indexNum,code,lchild,rchild); TForm1 *Form1;/-_fastcall TForm1:

35、TForm1(TComponent* Owner) : TForm(Owner)/-void _fastcall TForm1:Compress(TObject *Sender) if (!FileExists(Edit1-Text) ShowMessage(Edit1-Text+ 文件不存在!); return; Edit8-Text=; Edit9-Text=; Edit10-Text=; Edit11-Text=; Edit12-Text=; Edit13-Text=; Label1-Caption=; Label2-Caption=; Label3-Caption=; Label4-Caption=; Label5-Caption=; Label6-Caption=; Label20-Caption=; Label26-Font-Color=clOlive;