GZIP代码分析

接上回

采用LZ77算法对原始数据进行处理之后，这些数据被划分为两类数据对象：literal即未被匹配的字节块，在此过程中会生成长度值length以及距离值distance二元组。随后Gzip压缩程序按照扫描产生的先后顺序将这些信息按生成顺序排列存储在两个缓冲数组l_buf和d_buf中，在其中l_buf存放着literal块以及length值，在此过程中d_buf则专门用于存储distance字段。值得注意的是由于上述两种信息在同一数组中混杂存放因此还必须引入一个叫做flag_buf的数据结构来标识l_buf中的元素是属于literal块还是长度值部分；尽管如此由于这两类信息在同一数组中以特定顺序混合存在所以它们原有的排列顺序仍然得以保持下来。

扫描过程中,一旦任何一个缓存填满时,gzip就会将这些被存储在多个缓存中的数据整合成一个个压缩块输出,从而实现了初步的压缩。

Lazy Match一种改进策略

该方法采用贪心策略，在每次迭代时倾向于选择最长的可能匹配长度。然而，在全局范围内的优化效果并不如预期理想。例如，在对一个简单的字符串进行LZ77编码时：

具体操作如下：

ABCBCDEABCDE

当前扫描到第二个A，即灰底字开头。那么毫无疑问，会匹配到开头的ABC：

ABCBCDEABCDE

然后接下来的DE因为没有可匹配串，就被作为两个literal了。