数据结构课程设计_哈夫曼压缩文件.doc

数据结构基于哈夫曼算法的文件压缩程一.总体设计1目标设计：*实现目标：利用哈夫曼算法编写一个可以对文件进行压缩和解压缩的程序，即可以将指定的文件用哈夫曼算法压缩为一个新的文件，也可以将一个压缩后的文件还原，并可以将压缩或还原后的文件保存到指定位置。*功能描述：任何文件都可以看作是由字节组成的字节块，将字节看作基本编码单元，一个文件就可以看作是由字节组成的信息串。对文件中各字节的出现频率进行统计，并以出现频率作为字节的权值，就可以用字节为叶结点构造哈夫曼树，进而构造出各字节的对应哈夫曼编码。字节编码是一种8位定长编码，将各字节用哈夫曼编码进行重新编码，就有可能使得总的编码长度更短，从而达到压缩的效果。哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多位来表示。哈夫曼算法对文件的压缩和解压缩的程序就是将存储源文件的二进制编码通过利用哈夫曼算法译为长度不等的哈夫曼编码，即得到哈夫曼树。这棵树有两个目的：1 编码器使用这棵树来找到每个符号最优的表示方法，进而存储树实现文件的压缩。2 解码器使用这棵树唯一的标识在压缩流中每个编码的开始和结束，其通过在读压缩数据位的时候自顶向底的遍历树，选择基于数据流中的每个独立位的分支，一旦一个到达叶子节点，解码器知道一个完整的编码已经读出来了，即通过对哈夫曼树的遍历实现解压过程。2框架设计：定义结构体类型变量struct head 定义函数void compress() /*压缩文件*/ 在函数compress内定义变量； 读取被压缩文件； 建立并打开目标文件；逐字节读入，并进行累加计数，得到各个字节在文件中的出现频率；利用哈夫曼算法构造出字节对应的哈夫曼树；将压缩后的数据写入目标文件，并保存； 定义函数uncompress() /*解压文件*/ 在函数uncompress内定义变量; 读取需解压文件; 建立并打开目标文件; 对哈夫曼树进行遍历实现解压； 将解压后的数据写入目标文件，并保存； 定义主函数int main() 输入A，压缩文件，调用函数compress；输入B，解压文件，调用函数uncompress； 二.详细设计1、文件的字节频率统计字节共有256个，从0255，可定义长度为256的频率数组来记录每个字节的出现频率。将文件以二进制方式打开，逐字节读入，并进行累加计数，就可以得到各个字节在文件中的出现频率。for(i=0;i512;i+) if(headeri.count!=0) headeri.b=(unsigned char)i; else headeri.b=0; headeri.parent=-1; headeri.lch=headeri.rch=-1; for(i=0;i256;i+) for(j=i+1;j256;j+) if(headeri.countheaderj.count) tmp=headeri; headeri=headerj; headerj=tmp; 2、哈夫曼树的构造利用哈夫曼算法就可以构造出字节对应的哈夫曼树了。for(i=n;im;i+) min1=999999999; for(j=0;jheaderj.count) pt1=j; min1=headerj.count; continue; headeri.count=headerpt1.count; headerpt1.parent=i; headeri.lch=pt1; min1=999999999; for(j=0;jheaderj.count) pt1=j; min1=headerj.count; continue; headeri.count+=headerpt1.count; headeri.rch=pt1; headerpt1.parent=i; for(i=0;i=8) for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c0) strcat(buf,00000000); for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c1; fwrite(&c,1,1,ofp); pt1+; fseek(ofp,4,SEEK_SET); fwrite(&pt1,sizeof(long),1,ofp); fseek(ofp,pt1,SEEK_SET); fwrite(&n,sizeof(long),1,ofp); for(i=0;in;i+) fwrite(&(headeri.b),1,1,ofp); c=strlen(headeri.bits); fwrite(&c,1,1,ofp); j=strlen(headeri.bits); if(j%8!=0) for(f=j%8;f8;f+) strcat(headeri.bits,0); 5、编码头的格式编码头是压缩中的额外开销，因此不宜过大，否则将抵消压缩所减少的空间。基于字节的哈夫曼树有256个叶结点（256个字节），因此整个哈夫曼树共有511个结点。若采用静态三叉链结构表示，每个结点中有父结点下标、左子下标和右子下标三个数据项，每个数据项至少需要2个字节来表示（一个字节只能表示0255），因此整个哈夫曼树共需3*2*511=3066个字节的空间。但实际上，只要规定了左子和右子的排列规则（例如，可以约定在构造哈夫曼树，合并两棵子树时，下标较小的结点为左子，下标较大的结点为右子），左子下标和右子下标是可以不存储的，在每个结点中只存储父结点下标就可以了，这样，整棵哈夫曼树就只要2*511=1022个字节的空间。进一步分析会发现，父结点下标的取值范围是256510，因为叶结点是不可能作为父结点的。因此，如果对各结点的父结点下标作平移，平移到0254，就只需要一个字节就可以存储了，这样，整棵哈夫曼树就只要511个字节的空间就可以存储了。综上所述，可以将压缩后的511个字节的哈夫曼树作为编码头存到压缩文件中，在编码头中再加上一个字节，用来存贮压缩编码的结尾字节中的有效位数。这样，编码头共需512个字。7、解压过程解压时，先从压缩文件中读取编码头，还原哈夫曼树；再从压缩文件中逐字节读入压缩编码，并逐位扫描，进行解码，每解出一个字节，将其写入解压缩文件中。for(j=0;jf;l-) strcat(headeri.bits,0); strcat(headeri.bits,buf); headeri.bitsp=0; for(i=0;in;i+) for(j=i+1;jstrlen(headerj.bits) tmp=headeri; headeri=headerj; headerj=tmp; p=strlen(headern-1.bits); fseek(ifp,8,SEEK_SET); m=0; bx0=0;三.测试报告 *测试计划：为验证程序效果，对如下几个文件进行压缩和解压缩： 三个txt文件，分别为1KB. 9KB. 43KB，及一个JPG文件为4.27MB。 并对压缩和解压缩效果进行分析。*试验结果及结论： 如下表，对几个文件压缩和解压的结果：原文件压缩后解压后1Txt文件（1KB）Huf文件（1KB）Txt文件（1KB）2Txt文件（9KB）Huf文件（8KB）Txt文件（9KB）3Txt文件（43KB）Huf文件（36KB）Txt文件（43KB）4JPG文件(4.27MB)Huf文件（4.241KB）*#无法解压#* 结论：这个程序的基本缺陷是： 1 慢位流实现2 相当慢的解码（比编码慢）另一方面，这个程序有几个优点：1 哈夫曼树以一个紧密的形式每个符号要求12位（对于8位的符号）的方式存储；2 编码相当容易理解， 哈夫曼编码在数据有噪音的情况下非常好，这中情况下大多数基于字典方式的编码器都有问题。解码的时候，从上到下遍历树，为压缩的流选择从左/右分支，每次碰到一个叶子节点的时候，就可以将对应的字节写到解压输出流中