LZ77滑动窗口与重叠回指

距离回答“回头多少格”，长度回答“往前写多少格”。回头的位置不是固定快照，而是随写指针一起前移。于是一个短周期就可以自我扩展：历史里只有AB，也足以再生出ABABABA。

编码器需要找匹配，解码器只需要按已经给出的指针复制。找最长匹配属于字符串匹配理路字符串匹配String matching · Exact pattern matching在文本中定位模式串全部出现位置的问题。问题；不能把编码端可能昂贵的搜索成本加到每次解码的定义里，也不能把解码的简单性反过来当作免费搜索算法。

窗口 $W=8$、最大匹配18的教学贪心解析器，将 ABABABABA 编成 Lit(A), Lit(B), Match(7,2)。读入两个字面量后，$p=2$：

• 写位置2，从0读A；输出ABA
• 写位置3，从1读B；输出ABAB
• 写位置4，从2读A；这个A是第一步刚写入的
• 写位置5、6、7、8，分别从3、4、5、6读B、A、B、A

最后输出九字节 ABABABABA。一次性复制原历史切片 out[0:7] 只能拿到AB，无法实现这个token。若一概拒绝 $\ell >d$，就会拒绝本来合法且很有用的重叠回指。

距离0没有本页定义的历史源，必须拒绝。输出还为空时，任何正距离都无效。已有一个字节时距离2也无效；“它还在文件中某处”并不等于“已经解出并在窗口中”。空文件用空token序列得到空输出，停止方式由外层格式规定。对单字母长串可以发一个A，再用距离1的匹配扩展。

长度与距离还需要编码成bit。例如DEFLATE把长度11表示为长度符号265加1个扩展bit，基值11，扩展值0；距离6表示为距离符号4加1个扩展bit，基值5，扩展值1。总费用是两个符号各自的Huffman码长再加2bit，不能仅数“一个匹配token”。本单元只复算这项参数映射，不输出DEFLATE块。

复制为何唯一且保持原文 ​

对匹配内的位置 $i$ 归纳。因为 $d\ge 1$，源位置 $p+i-d$ 严格早于目标位置 $p+i$；它要么来自此前token，要么已由更小的 $i$ 写好。编码端只有验证原文满足对应的周期匹配才可输出该token，解码端依次复制就保持每个位置与原文相同。重叠不会引入循环依赖。

用朴素搜索在每个输入位置尝试至多 $W$ 个距离、每个比较至多 $L_{max}$ 字节，编码上界为 $O(nW{L}_{max})$；后缀结构或哈希匹配可改变这个成本。解码按上述算法每写一字节花常数操作，若有 $k$ 个token、展开长度为 $n$，工作为 $O(k+n)$。只需保留最近 $W$ 字节时可流式输出，工作历史为 $O(W)$；检查器返回整个结果，因而还占 $O(n)$ 输出空间。

贪心最长匹配减少当前位置的未处理字节数，不自动最小化最终bit数：更长匹配可能需要昂贵的长度或距离符号，也可能错过下一位置更省的匹配。若要证明最优解析，需要把token费用和未来状态写进优化问题。

回指长度来自不可信文件时，先检查 $\ell \le N_{max}-p$ 和剩余工作预算，再执行复制；不要先分配 $\ell$ 大小的临时数组。这项资源契约在有界解压理路解压输出与工作预算Bounded decompression · Decompression resource limits在不可信长度触发分配之前验证输出、表、字典和工作上限，以重叠复制说明压缩长度与解码成本的差异。中与码表、字典预算统一。