|
转：http://blog.163.com/probe@126/blog/static/1046271312012112171612788 在看gzip的源码时，遇到的困难比原来想象的要大很多，这软件对可移植性的要求真jb高，好多系统都考虑了，所以搞了很多ifdef、define，甚至在各个函数中也涉及到了不同系统的实现。 这还好，更崩溃的是它的算法，我了个去啊，还涉及到了哈夫曼树，多亏哥前几个月刚刚看完数据结构啊，否则直接要放弃了。 看完了main函数后，看了源码根目录下的algorithm.doc这个文件，这个word文档是简单地描述gzip的算法的，的确是相当的粗糙，我花了两天的时间翻译了过来，译文贴在这里，留个纪念，等过段时间我吃透这个软件的源码后，再发文仔细分析吧。 －－－－－－－－－译文分割线－－－－－－－－－－－－ 1、算法
Zip和gzip使用的压缩算法是LZ77的一个变种。这种算法是找到原始数据中重复的字符串，这个字符串第二次出现时，被替换为指向前一个字符串的指针，形如这样的一个对儿：(距离，长度)。距离最大32k个字节，长度最大258个字节。如果一个字符串在前面32k个字节中都没有出现，就把它当成一个字节序列（也就是说，’string’这个字符串可以是任意的字节序列，不一定非得是可打印的字符。）
字符或匹配长度使用一个哈夫曼树压缩，匹配距离使用另一棵树。这些树存储在每个块开始的紧凑结构中。这些块可以任意大小（只是一个块的压缩数据必须要有足够的内存）。当zip决定用一个新树开始创建一个新块的时候，当前块就结束了（这有点像compress）
用哈希表寻找重复的字符串。所有长度为3的字符串都往哈希表里插入。哈希的索引用后面紧接着的3个字节计算。如果这个索引的哈希链不空，哈希链中所有的字符串都要和当前的字符串进行比较，从中选出最长匹配的那个。
哈希链从最近的字符串开始寻找，匹配小的距离并且利用了哈夫曼编码。哈希链一个个连在一起，从不做删除操作，此算法只是简单地忽略太旧的匹配。
为了避免最坏的情况，非常长的哈希链被截断成任意的特定长度，这取决于运行时的选项（zip -1 到 -9）。所以zip并不总是找到最长的匹配，但是一般找到的是足够长的匹配。
Zip也使用一种延迟机制来延迟匹配的选择。当一个长度为N的匹配找到后，zip从接下来的输入数据中查找更长的匹配。如果找到一个更长的匹配，前面的匹配被缩短为长度1（因此产生一个单独的字节）而后这个更长的匹配生成了。否则，原始的匹配被保留下来，只有N步以后才尝试下一个匹配查找。
延迟匹配求值受制于一个运行时参数。如果当前的匹配足够长，zip减少一个更长匹配的查找，从而加速整个过程。如果压缩比比速度更重要，即使第一次匹配已经足够长，zip仍然尝试完整的第二次查找。
最快的压缩模式（速度选择 -1 到 -3）不使用延迟匹配求值。在这些快速模式中，当字符串没有找到匹配，或者匹配不是太长时插入哈希表。这样降低了压缩比，因为更少的插入和更少的查找，从而节省了时间。
2. gzip 压缩文件格式
pkzip的格式在不同的头中使用了很多天花板（overhead的确是这个意思），这对一个归档是有用的，但是如果只压缩一个文件就不合适了。Gzip使用了一个更简单的结构。数字使用little endian格式（这个格式详见百度，是一种编码格式，IA架构的系统用这种编码），0位是最低有效位。 Gzip文件是各个压缩成员的序列。每个成员都包含一下结构：
2 bytes magic header 0x1f, 0x8b (\037 \213)
1 byte compression method (0..7 reserved, 8 = deflate)
1 byte flags
bit 0 set: file probably ascii text
bit 1 set: continuation of multi-part gzip file
bit 2 set: extra field present
bit 3 set: original file name present
bit 4 set: file comment present
bit 5 set: file is encrypted
bit 6,7: reserved
4 bytes file modification time in Unix format （mtime，这个要注意了）
1 byte extra flags (depend on compression method)
1 byte operating system on which compression took place
2 bytes optional part number (second part=1)
2 bytes optional extra field length
bytes optional extra field
bytes optional original file name, zero terminated
bytes optional file comment, zero terminated
12 bytes optional encryption header
bytes compressed data
4 bytes crc32
4 bytes uncompressed input size modulo 2^32
这种格式被设计允许一次扫描压缩文件，不需要倒回来重新寻找，而且不需要未压缩的输入文件的大小或者输出介质的合适大小的先验知识。如果不是从标准磁盘文件获取的输入，就将压缩开始的时间设置为文件的修改时间。
时间戳的保存很有用，特别是当压缩后的文件在网络上传输时。在这种情况下没有必要保存所有者属性。在本机模式上，所有者属性在压缩，解压的时候被保存。如果时间戳是0，将被忽略。
Flag的第一个比特只是一个可选的指示，它可以被前面小的输入数据设置。万一怀疑，这个标记就被清除，以便指示二进制数据。有不同文件格式（如文本和二进制数据）的系统上，解压程序可以用这个标记来选择一个正确的格式。
扩展区域，如果存在，必须由一个或多个子区域构成，每一个都是下面这样的格式：
subfield id : 2 bytes
subfield size : 2 bytes (little-endian format)
subfield data
id字段可以由两个包含助记值的两个字节组成。请发送id给作者的邮箱，由2个字节组成的id们留作将来使用，下面的ids被定义为：
Ap (0x41, 0x70) : Apollo file type information Ap代表：Apollo文件类型信息
Size子域是子域数据的大小，不包括id和size这两个字段。扩展域长度是扩展域的总长度，包括id和size字段。 不管压缩数据的实际大小，必须能用压缩格式检测到压缩数据的结尾。如果压缩数据不能保存在一个文件中（特别是在磁盘上），每一个部分用前文所述的一个头开始，但只有最后一部分包含crc32和原始数据大小这两个字段。解压程序可以提示多个压缩文件的附加数据。多个部分可以被单独提取是值得的，但是不是强制的，因此当其中一个数据毁坏时，部分数据可以被恢复。只有不将压缩状态保存在各个部分之间时，这才可能实现。压缩类型依赖的标记可以指示这个。
如果被压缩的文件是在不分大小写的文件系统上进行的，原始文件名字段必须被强制转换成小写。如果从标准输入压缩数据就没有原始的文件名。
即使压缩完之后的文件稍微比原始文件大一点，压缩总是能顺利执行完毕。最坏的变大是一些gzip文件头的字节，每32k的块增加5字节，或者大文件变大千分之15.注意，实际使用的磁盘块几乎不增加（俺理解，一个磁盘块在linux上默认可以存储4k字节的文件涅）
加密技术使用的是 zip1.9的。为了加密检查，解密了的头的最后一个字节必须是0.加了密的文件的时间戳可能被设置为0，以避免给出一个关于随机头的结构的线索
Jean-loup Gailly
jloup@chorus.fr
References:
[LZ77] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data
Compression", IEEE Transactions on Information Theory", Vol. 23, No. 3,
pp. 337-343.
APPNOTE.TXT documentation file in PKZIP 1.93a. It is available by
ftp in ftp.cso.uiuc.edu:/pc/exec-pc/pkz193a.exe [128.174.5.59]
Use "unzip pkz193a.exe APPNOTE.TXT" to extract (note: unzip, not gunzip).
|
