匹配搜索与延迟决策

保存历史的目的，是把当前输入换成更短的表示。假设已经处理了 ABCQABCR，接下来要处理 ABCQABCX：可以先写字面量，也可以发出“向后找一段相同字节”的长度／距离对。搜索要回答的是：从哪里复制，能复制多少真实输入字节？

这一步的输入是窗口里的连续字节、当前起点，以及指向较早位置的候选链。输出先是一条供策略考虑的匹配，不是已写入压缩流的符号。若没有有用匹配，策略仍可写一个字面量，保持同样的原始字节含义。

先比较两个候选

最近的 ABCR 与当前 ABCQABCX 先相等三个字节，再在 R 与 Q 处不同，所以它提供长度 3、距离 4 的选择。更早的 ABCQ 可以相等七个字节，再在 R 与 X 处不同，提供长度 7、距离 8 的选择。这里没有作为数据的空格：两个历史片段紧接着，后面紧接当前输入。

七字节比较越过了最早那个四字符片段，继续读取同一数组后面的 ABC。候选不是孤立保存的单词，而是窗口中一串连续字节的起点。

动画用逻辑位置 0、4、8 标记这些片段。实际 zlib 把零留作 NIL；把这些位置都增加一，比较和距离不变，也就不再把哨兵当作候选。这个场景展示候选预算的影响，不代表每次真实调用都会生成完全相同的哈希表内容。

候选与距离界

候选是一个更早的字节位置，不是复制出来的字符串。为了快速找到候选，压缩器按三字节前缀的哈希值分组：桶头保存这一组最新的位置，前驱链接指向更早的位置。插入操作 INSERT_STRING 把当前位置加入索引，同时返回原来的桶头。策略把这个返回位置称为 hash_head。从旧桶头开始，就不会拿当前位置与自身匹配。

搜索还需要限制“最多能往回找多远”。当前字节在数组中的下标叫 strstart；配置的窗口尺度叫 W，在 C 中是 w_size，单位是字节。这个压缩器为补充输入和快速比较预留了 262 字节的余量，因此最大搜索距离 MAX_DIST 为 W - 262 字节。通常 W=32768，得到 32506 字节。这是实现的搜索界；DEFLATE 格式本身允许的距离上限仍是 32768。窗口章节再展开这段余量与数组布局。

调用比较例程 longest_match 之前，策略先检查非零的 hash_head 位于 strstart 之前，且两者之差 strstart - hash_head 不超过 MAX_DIST。零表示 NIL，即没有候选。

允许距离对应的最早位置记为 limit = max(strstart - MAX_DIST, 0)。例如当前下标为 1000、最大距离为 250，则边界是 750：候选 900 足够近，700 已经太旧。与零取较大值，是为了处理当前下标还小于最大距离的情形。

这个边界还要与源码的循环顺序一起读。第一个候选先进入 do 循环体；循环末尾才取下一个前驱并检查是否继续。因此，若入口候选恰好为 750，它仍可被比较；若沿链取得的下一个候选是 750，则严格条件“下一个位置大于 750”会停止循环。证明需要分别覆盖入口检查和后继检查，才能保留真实源码在边界上的行为。

从逐字节比较到快速排除

最直接的办法是从候选开头逐字节比较，遇到第一次不等就得到长度。上例的两次比较分别得到 3 和 7。如果每个候选都这样从头扫描，很多相同短前缀会被反复读取。zlib 先问一个更便宜的问题：“这个候选还有可能超过已经找到的长度吗？”只有可能改进时，才做完整扫描。

调用者先用 prev_length 提供一个待超越的匹配长度，单位是字节。搜索用 best_len 保存当前最佳长度，开始时令 best_len = prev_length。例如基线为 3，想取得改进就至少需要前 4 字节相等。如果一个候选无法超过这条基线，就没有必要把它从头完整扫描一遍。在普通逐字节分支中，例程先检查偏移 best_len、best_len-1 处的字节，再检查开头两个字节。任意位置不等，就立即排除这个候选。

实际的普通字节分支摘自固定版本 longest_match，1511–1514 行：

if (match[best_len]     != scan_end  ||
    match[best_len - 1] != scan_end1 ||
    *match              != *scan     ||
    *++match            != scan[1])      continue;

这里 scan 指向当前输入，match 指向候选；scan_end 和 scan_end1 缓存当前输入在最佳长度附近的两个字节。第一行检查能否超过最佳长度；第二行检查前一字节；第三行检查开头；第四行先推进候选指针，再检查第二字节。|| 从左到右短路，任一失败便执行 continue，转向候选链的继续条件。探测成功后，源码才进入下述连续扫描；这四行本身并未证明整段匹配。

很多字符串共享短前缀时，先探测当前最佳匹配的末端附近尤其有用。一个候选可能前二十个字节都相同，却已经在“超过现有长度所必需的那一位”失败。便宜的探测能省掉这二十次重复比较。但探测通过，也不能证明开头与末端之间所有字节相等；后续扫描仍须建立这些事实。

第三个字节还有特殊地位。在选定哈希参数下，如果三字节哈希键相同，且前两个字节相同，则第三个字节也相同。因此，实现不必在主要扫描之前再做一次普通的偏移 2 比较。这是这个短移位／异或哈希在对应参数界下的性质，不是所有哈希冲突都具备的性质。

普通字节分支把八对连续字节的比较展开在一个条件中，短路求值会在第一次不等时停止。边界检查没有逐字节执行，所以已经建立的窗口余量必须覆盖最远读到的位置，包括偏移 258。另一个 UNALIGNED_OK 分支按双字节字比较，需要单独的宽度和对齐论证；普通字节分支的证明不会自动覆盖这种配置。

例程可能检查真实预读区之外、但已初始化的窗口空间。返回长度会截在 lookahead 以内，提前停止的目标长度也会截到可用输入。额外的可读空间支持快速比较，并不允许消费不存在的输入。如果没有候选超过 prev_length，match_start 就没有获得针对当前位置的新正确性保证；调用者必须把这个情况与真正的改进分开。

搜索预算与引擎选择

前面的七字节匹配只有在搜索确实访问较早候选时才能找到。如果第一条候选之后就停止，得到的三字节引用仍然正确，只是可能错过更好的压缩机会。配置因此控制两种不同的工作量：比较多少个候选，以及为了多长的匹配继续花时间。

这些设置决定搜索愿意花多少时间；格式仍然允许同一组合法长度和距离。下面把立即采用结果的快速引擎 deflate_fast，与多看下一位置的延迟决策引擎 deflate_slow 分开。

例如级别 6 最多访问 128 个候选，找到 128 字节的匹配即可提前停止；若上一个匹配已经达到 8 字节，则把访问预算从 128 缩为 32 次。几个代表性设置如下：

在普通 longest_match 中，若先前长度已经达到缩减预算阈值，链预算会缩小为四分之一；找到达到 nice_match 的候选时则提前停止。预算可能在所有保留候选都访问完之前耗尽，停止搜索阈值也可能在真正最长候选被找到之前结束搜索。因此，函数名并不承诺找到整个窗口中全局最长的匹配。

快速策略会立即采用当前位置上有用的匹配。匹配较短时，它把中间经过的字符串插入哈希表；匹配较长时，则可以跳过这些插入，在新位置附近重新准备滚动哈希。这节省了时间，但以后能搜索到的候选也更少。在级别 1–3 中，共用配置字段起的是插入长度限制作用，不是延迟决策引擎的延迟搜索阈值。

延迟决策策略把它解释为字节长度阈值 max_lazy_match：前一个匹配已经足够长时，可以省去下一次搜索。Z_FILTERED 还会排除部分短匹配；普通的、距离很远的三字节匹配也可能被 TOO_FAR 启发式放弃。Z_HUFFMAN_ONLY 绕过匹配搜索，Z_RLE 则寻找距离为一的重复串。这些都是在合法编码之间作选择，并没有生成不同的解压格式。deflateTune允许修改搜索参数，所以覆盖其完整定义域的论证不能暗中只使用配置表默认值。

延迟决策与符号提交

至此，搜索只比较了同一个起点的候选。延迟决策策略还要比较相邻的两个输入起点：现在采用一个短匹配，是否会挡住下一字节处更长的匹配？再用一个例子区分“找到匹配”和“提交匹配”。假设更早历史中有 XABZ 和 ABCDEFGH，当前输入为 XABCDEFGQ。把当前字节位置记为 S，S+1 就是下一字节。在 S 上，XAB 可以匹配三个字节；S+1 上，ABCDEFG 可以匹配七个字节。假设搜索到达这些候选，并且再下一个位置没有找到超过七字节匹配的改进。

剩余的 Q 随后作为字面量处理。展开结果为 X + ABCDEFG + Q，仍然是那九个输入字节。立即采用三字节匹配的另一条路径，会先覆盖 XAB，再处理后面的内容。哪条路径最终位数更少，还取决于编码和距离成本，不能只比较长度。

在表格的第三行，当前处理位置已经是 S+2，而要提交的匹配从 S+1 开始。先给这次记录调用中的值命名：prev_match 是延期匹配所引用的较早数组下标，prev_length 是它的字节长度，MIN_MATCH=3 是格式能编码的最短匹配。s 指向压缩器状态；bflush 接收一个是否需要刷新符号记录区的结果。固定版本 deflate_slow，2055–2056 行正因此写成：

_tr_tally_dist(s, s->strstart - 1 - s->prev_match,
               s->prev_length - MIN_MATCH, bflush);

第一行从 strstart-1 而非 strstart 计算距离，来源是保存的 prev_match。第二行把保存的长度减去最小匹配长度 3，交给符号记录操作；bflush 接收记录区是否需要刷新。这里记录的是长度／距离符号，还不是最终 Huffman 位串。只有满足前面分支条件、确实接受旧匹配时才执行这两行。

状态字段明确保存这一步延迟：match_available 表示有一个延期位置，prev_length 和 prev_match 保存上一个起点的候选。接受前一个匹配时，只需再消费 prev_length-1 个预读字节，因为其中一个字节已经在上一步越过。插入循环在 max_insert 处停止；这个下标是仍有三个真实字节可用的最晚起点。因此，输入尾部尚不完整的三字节串不会被拿来计算哈希。

只有某个分支决定提交字面量或匹配后，符号记录操作才写入三个字节的记录并更新编码频率。这里接到Huffman 构造和块选择。搜索可以改变选中了哪些合法符号；对应的证明思路则需要解释，为什么每一种选定序列仍然展开为已消费的字节。完整策略与公开调用的组合证明尚未完成。它还要覆盖允许的调参值，并让每次搜索结果、延期状态和实际提交记录保持同一份输入含义。