Gzip source code analysis (2)

LZ77算法的实现

LZ77算法本质上是一个字符串匹配算法。它通过按顺序逐字节扫描待压缩文件中的每一字节来实现数据压缩。具体来说，在压缩过程中需要寻找以当前字节开头的一个特定序列（称为"当前序列"），该序列在起始位置固定但长度未知的情况下存在于之前已处理的部分中，并记录其出现的位置信息。

为提高查找效率并加速匹配过程，我们需要建立一个哈希表以存储所有已出现过的字符串及其位置信息。然而这样的哈希表规模可能会迅速扩大。因为从同一字节起始的所有可能子串数量极大，并且当处理一个体积巨大的文件时可能出现的情况是哈希表规模可能会爆炸性增长。

所以，必须做一些限制。

一个主要问题是哈希表仅能存储长度固定的字符串（如3-byte长度），然而这一缺陷并不会阻碍我们发现更长序列的可能性。实际上这一缺陷并不会阻碍我们发现更长序列的可能性是因为通过哈希表我们可以获得一些潜在候选序列的位置信息之后我们需要对这些候选进行逐字符比对直到无法继续比对为止尽可能让每次比对都能取得较长的结果片段

另一个重要限制是仅限于当前字符串前面W个字节范围内的串；这段称为滑动窗口的那一段连续区域随扫描位置变化而移动；因为压缩操作仅局限于滑动窗口内进行的原因导致压缩效果有所受限

在第一个限制中被称作"最小匹配长度"。一旦滑动窗口大小确定后，则这个最小匹配长度就能够计算出来。

因为匹配只在滑动窗口中进行,因此最大