收稿日期:2005-05-05参考文献：《GzipZlibPNG压缩算法》JIURL《笨笨数据压缩教程》王咏刚GZIP压缩程序源码V1.2.4（HYPERLINK"http://www.gzip.org/"http://www.gzip.org/）RFC1950-ZLIBCompressedDataFormatSpecificationversion3.3RFC1951-DEFLATECompressedDataFormatSpecificationversion1.3RFC1952-GZIPfileformatspecificationversion4.3关于GZIP1.2.4的分析葛伟(南京航空航天大学信息学院计算机系学号：040130520)摘要:简要的分析了GZIP的文件格式，基本的压缩使用的算法和实现，以及对GZIP1.2.4的源码的主要函数进行了分析说明，阐述了对其中算法的一些自己的看法。关键词:GZIP1.2.4，GZIP分析1．GZIP文件的基本格式说明由于下面的分析会用到GZIP文件的格式中的内容，所以先对GZIP文件的格式进行一下简要的介绍。GZIP文件由1到多个“块”组成，实际上通常只有1个块。每个块包含头部、数据和尾部三部分。|ID1|ID2|CM|FLG|MTIME|XFL|OS|额外的头字段|压缩的数据|CRC32|ISIZE|其中，头部分包括ID1，ID2，CM，FLG，MTIME，XFL，OS，以及额外的头字段。ID1与ID2：各1字节。固定值，ID1=31(0x1F)，ID2=139(0x8B)，表示GZIP格式。CM：1字节。压缩方法。目前只有一种：CM=8，表示使用DEFLATE方法。FLG：1字节。标志。bit0FTEXT-指示文本数据bit1FHCRC-指示存在CRC16头校验字段bit2FEXTRA-指示存在可选项字段bit3FNAME-指示存在原文件名字段bit4FCOMMENT-指示存在注释字段bit5-7保留MTIME：4字节。更改时间。UINX格式。XFL：1字节。附加的标志。当CM=8时，XFL=2-最大压缩但最慢的算法；XFL=4-最快但最小压缩的算法OS：1字节。操作系统，确切地说应该是文件系统。有下列定义：0-FAT文件系统(MS-DOS,OS/2,NT/Win32)1–Amiga2-VMS/OpenVMS3–Unix4-VM/CMS5-AtariTOS6-HPFS文件系统(OS/2,NT)7–Macintosh8-Z-System9-CP/M10-TOPS-2011-NTFS文件系统(NT)12–QDOS13-AcornRISCOS255-未知额外的头字段：(若FLG.FEXTRA=1)|SI1|SI2|XLEN|长度为XLEN字节的可选项|(若FLG.FNAME=1)|原文件名(以NULL结尾)|(若FLG.FCOMMENT=1)|注释文字(只能使用iso-8859-1字符，以NULL结尾)|(若FLG.FHCRC=1)|CRC16|存在额外的可选项时，SI1与SI2指示可选项ID，XLEN指示可选项字节数。数据部分：DEFLATE数据格式，包含一系列子数据块。子块概貌如下：|BFINAL|BTYPE|数……据|BFINAL：1bit位。0-还有后续子块；1-该子块是最后一块。BTYPE：2bit位。00-不压缩；01-静态Huffman编码压缩；10-动态Huffman编码压缩；11-保留。尾部分：CRC32：4字节，保存原始数据的32位校验和。ISIZE：4字节，用来保存原始数据长度的低32位。2．GZIP所使用压缩算法的实现下面将gzip的实现分块，一部分一部分来说明。对应的gzip中所使用的各种实现技巧的出处或者灵感，gzip的作者在源码的注释中分别进行了说明。寻找匹配串算法概述：Gzip算法对遇到的每一个串，首先会把它插入到一个“字典”中。这样当以后有和它可以匹配的串，都可以直接从“字典”中查出这个串。在插入的时候，使用这个插入串的前三个字节，计算出插入的“字典”位置，然后把插入串的开始位置保存在这个“字典”位置中。查出的时候，使用查出串的前三个字节，计算出“字典”位置，由于插入和查出使用的是同一种计算方法，所以如果两个串的前三个字节相同的话，计算出的“字典”位置肯定是相同的，所以就可以直接在该“字典”位置中，取出以前插入时，保存进去的那个串的开始位置。于是查出串，就找到了一个串，而这个串的前三个字节和自己的一样，所以就找到了一个匹配串。但是会有多个串，他们的前三个字