于每个符号的叶节点的0/1串,就是该符号的二进制编码。
由于符号按概率大小的排列既可以从左至右、又可以从右至左,而且左右分枝哪个标记为0哪个标记为1是无关紧要的,所以最后的编码结果可能不唯一,但这仅仅是分配的代码不同,而代码的平均长度是相同的。
编码式压缩利用各个单字节使用频率不一样的倾向,使定长编码变为不定长编码,给使用频率高的字节更短的编码,使用频率低的字节更长的编码,起到压缩的效果。由于Huffman编码为根结点到叶子结点路径上的0和1的序列,而一个叶子结点的路径不可能是另一个叶子结点路径的前缀,因此一个Huffman编码不可能为另一个Huffman编码的前缀,这就保证了Huffman编码是可以区分的。由于用Huffman算法建立起来的树总是一棵最优二叉树,因此这又让Huffman编码能够实际应用到压缩中。
2.2.3 GZIP算法原理分析
GZIP使用deflate算法进行压缩。zlib,以及图形格式png,使用的压缩算法也是deflate算法。GZIP对于要压缩的文件,首先使用LZ77算法的一个变种进行压缩,对得到的结果再使用Huffman编码的方法(GZIP根据情况,选择使用静态Huffman编码或者动态Huffman编码)进行压缩。LZ77算法和Huffman编码结合起来,就是deflate算法的根本实现方法,也就是GZIP的压缩原理。
懒惰匹配(lazy match)是GZIP中对LZ77算法的改进,实现过程如下:
在压缩过程中,对于当前字节开始的串,寻找到了最长匹配之后,GZIP并不立即决定使用这个串进行替换。而是看看这个匹配长度是否满意,如果匹配长度不满意,而下一个字节开始的串也有匹配串的话,那么GZIP就找到下一个字节开始的串的最长匹配,看看是不是比现在这个长。这就是懒惰匹配。
如果比现在这个长的话,将不使用现在的这个匹配。如果比现在这个短的话,将确定使用现在的这个匹配。发现第二次匹配的匹配长度大,就不使用第一次的匹配串。如果直接使用第一次匹配的话,有可能将错过更长的匹配串。
在满足懒惰匹配的前提条件下,懒惰匹配不限制次数,一次懒惰匹配发现了更长的匹配串之后,仍会再进行懒惰匹配,如果这次懒匹配,发现了更长的匹配串,那么上一次的懒匹配找到的匹配串就不用了。
进行懒惰匹配是有条件的。进行懒惰匹配必须满足两个条件,第一,下一个处理字节开始的串,要有匹配串,如果下一个处理字节开始的串没有匹配串的话,那么就确定使用当前的匹配串,不进行懒惰匹配。第二,当前匹配串的匹配长度,GZIP不满意,也就是当前匹配长度小于max_lazy_match(max_lazy_match在固定的压缩级别下,有固定的值)。
2.3 开发环境
使用JBuilder2006进行程序开发。JBuilder是一个可视化JAVA开发工具。它是在Java2平台上开发商业应用程序、数据库、发布程序的优秀工具。它支持J2EE,所以程序员可以快速的转换企业版Java应用程序。使用此开发工具可以实现程序的可视化。
3 总体设计
系统总体结构设计是系统设计过程中及其重要的一步,对系统的技术层次,开发过程,功能实现及开发成本方面具有重大的影响。系统总统结构设计应尽可能的考虑人机关系,环境条件以及算法的可行性等的联系,使系统每个部分都能协调适应。
本实验论证是基于GZIP算法理论体系的,因此使用的压缩方法是参照GZIP算法的。GZIP算法理论体系主要包含三个内容:LZ77算法,Huffman算法,懒惰匹配算法。因此在设计过程中要注意如何实现这三个算法并且将其结合起来。
3.1 程序功能模块
根据设计思路,文件的压缩和解压缩是两个相反的操作,程序可分为GZIP压缩模块、UNGZIP压缩模块。现在设计出功能结构图如图3。
图3 功能结构图
3.2 模块分析与流程图
分析程序的总体流程图可以以图4来表示:
图4 总体流程图
3.2.1 压缩模块
压缩模块的实现流程为:
(1)打开要压缩的文件,使用字典算法扫描文件统计文件使用的字符集并统计每个字符集的使用次数。
(2)根据扫描的结果构建文件字符集的Huffman树。
(3)由文件的Huffman树求字符集中各字符的编码,形成Huffman编码表。
(4)建立压缩文件。
(5)将要压缩文件的字符集大小和文件的大小写入压缩文件。将字符集的Huffman树写入压缩文件,供解压缩时使用。
(6)从文件中读取一个字符集,查Huffman编码表,得到它的Huffman编码。按位流放入压缩文件的写缓冲区。
(7)检查压缩文件的写缓冲区,如果已满一个字节,写入压缩文件,如果要压缩的文件没有达到文件的结尾,转到步骤6。
(8)关闭要压缩文件和压缩文件
画出流程图如图5:
图5
图5 压缩模块流程图
3.2.2 解压缩模块
解压缩模块的实现流程为:
(1)打开压缩文件,读取字符集字符个数和文件的字节数。读入文件的Huffman树。
(2)建立解压缩文件。
(3)读入一个字节的编码,用Huffman树得到字符,将字符写入解压缩文件,如果编码已用完,就读取下一个字节,如此重复,直到读取压缩文件的全部编码。
(4)关闭压缩文件和解压缩文件。
画出流程图如图6:
图6 解压缩模块流程图
3.3 程序中各个类的初步定义
为了完成此程序,应当设计一个接口,十四个类,和二个异常处理类。其中
接口:Checksum。
类:Adler32;CRC32;CheckedInputStream;CheckedOutputStream;Deflater;DeflaterOutputStream;GZIPInputStream;GZIPOutputStream;Inflater;InflaterInputStream;ZipEntry;ZipFile;ZipInputStream;ZipOutputStream。
异常索引:DataFormatException;ZipException。
各个类的简单介绍如表1:
表1:程序各个类的作用
条目 类型 描述 Checksum 接口 被类Adler32和CRC32实现的接口 Adler32 类 使用Alder32算法来计算Checksum数目 CheckedInputStream 类 一个输入流,保存着被读取数据的Checksum CheckedOutputStream 类 一个输出流,保存着被读取数据的Checksum CRC32 类 使用CRC32算法来计算Checksum数目 Deflater 类 使用ZLIB压缩类,支持通常的压缩方式,程序核心类 DeflaterOutputStream 类 一个输出过滤流,用来压缩Deflater格式数据 GZIPInputStream 类 一个输入过滤流,读取GZIP格式压缩数据 GZIPOutputStream 类 一个输出过滤流,读取GZIP格式压缩数据 Inflater 类 使用ZLIB压缩类,支持通常的解压方式,程序核心类 InflaterInputStream 类 一个输入过滤流,用来解压Inflater格式的压缩数据 ZipEntry 类 存储ZIP条目 ZipFile 类 从ZIP文件中读取ZIP条目 ZipInputStream 类 一个输入过滤流,用来读取ZIP格式文件中的文件 ZipOutputStream 类 一个输出过滤流,用来向ZIP格式文件口写入文件 DataFormatException 异常类 抛出一个数据格式错误 ZipException 异常类 抛出一个ZIP文件 4 详细
4.1 压缩的程序流程
压缩程序的实现过程中,涉及到很多类的调用,除了压缩有关的类,还有IO类。对于IO类的调用不考虑的情况下,各个压缩功能类的调用流程(如图7):
(1)主程序gzip调用输出过滤流GZIPOutputStream,读取GZIP格式压缩数据,压缩开始。
(2)GZIPOutputStream调用CRC32来计算Checksum的数目。
(3)在CRC32返回结果后,GZIPOutputStream调用Deflater压缩类来进行压缩。在Deflater类的调用过程中,实现了对数据的压缩字符集确定与编码,也就是实现了LZ77算法、懒惰匹配与Huffman编码的结合。
(4
上一篇:
数据结构(java)走迷宫
下一篇:
高陈基于Java超市账单管理系统