依赖匹配长度的滑动窗口能提升 LZ77 压缩率吗？

WLZ 让窗口大小随匹配长度变化

经典 LZ77 把重复子串编码为向后距离加匹配长度，而每个匹配都使用同一段 W 个符号的历史。这对短匹配是浪费：一个两字节的重复很少需要指向遥远过去的指针，却要付出与长重复相同的固定宽度距离字段。WLZ 改为给每个匹配长度 ℓ 分配一个窗口 W(ℓ)，于是短匹配使用更小的窗口和更短的距离字段，长匹配则保留对远处重复串的访问能力。解码器从解出的长度推断距离范围，因此不需要单独的长度类别标识符。

论文始终严格区分两个量：以输入符号数衡量的窗口大小，以及以比特衡量的距离字段宽度。长度为 ℓ 的匹配有窗口 W(ℓ) 和宽度 w(ℓ) := log2 W(ℓ)；最大窗口 W 的宽度为 B := log2 W。这一区分很重要，因为窗口收窄带来的压缩节省是每个匹配节省的比特数，而窗口本身是以符号数计的搜索空间限制。

转移界同时计入窗口限制与漏掉的匹配

限制窗口会破坏经典 LZ77 分析所依赖的一个性质：合法复制串的后缀可能保留一个超出其较短长度窗口的距离，因此标准比较所依赖的后缀封闭性失效。论文的解析转移不等式通过同时计入窗口限制和解析器漏掉或放弃的匹配来修补这一点。有了这项计入，既有的短语计数界仍然适用于 WLZ。

其结果是：在子串复杂度界下，精确贪心 WLZ 保持了普通 LZ77 的收敛速率；当窗口与输入长度相当时，也保持其有限类极小极大阶。当全窗口匹配从长度 o(B) 开始时，一个更精细的分块计入证明了精确贪心 WLZ 的平稳遍历普适性。这些都是保持性结果：只要解析器是精确的、且漏匹配项被计入，WLZ 不会丢失 LZ77 已有的保证。

校准后的调度从不提高最小词元代价

核心比较固定了一个单窗口对照方案：使用一个窗口 2^B、相同的字面量代价，以及匹配代价 a(ℓ)+B。给定任意对照解析，其匹配被分为依赖长度的窗口所接纳的和被排除的两类。接纳第一类每个匹配节省 B−w(ℓ) 比特；把每个被排除的匹配替换为其字面量则花费 bℓ−a(ℓ)−B 比特。引理 4.3 表明，一个可接纳解析的最小词元代价至多等于对照代价减去被接纳的节省、再加上排除代价。

由此得到两点实用解读。第一，仅靠更短的距离字段并不能保证改进：对于带有超额词元代价 E_W 和头部差异 ΔΓ 的启发式编码器，严格改进要求被接纳的节省超过排除代价加上 E_W 再加上 ΔΓ。第二，窗口宽度可以按边际规则选择——把窗口扩大一位恰好有帮助，当且仅当新接纳匹配的节省超过向每个此前已接纳匹配额外收取的那一位。于是，跨长度类非递减的宽度可以通过前缀最小动态规划在直方图构建后以 O(J(B_max+1)) 时间选出，它优化的是固定轨迹，而不是窗口选择与重新解析的联合优化。

窗口带来的节省真实但只是多项式量级

在指定的 iid 信源上，经过校准的窗口调度以 β>2 节省 Ω(BW^−β) 的码率。相对于单窗口基线，这是真实的渐近改进，但它随窗口大小多项式衰减，因此并不是大增益所在之处。论文直接说明了这一点：其余增益来自词元编码，而不是窗口。

另一项阻碍进一步强化了这一点。对于 iid 均匀信源，若存在一个与 B 无关的固定整数阈值 t，使每个长度至少为 t 的匹配都获得全窗口和恰好 B 个距离位，则冗余至少为 h + c·h·log B/B − O(B^−1)。在该模型中，这排除了 p>1 时的冗余 O(B^−p)，甚至排除了 O(B^−1)。因此，仅改变短匹配窗口无法带来更好的指数；该界背后的长度代价假设对常见的通用整数编码成立，但并不能仅由前缀可解码性推出。

廉价长度符号与游程重编码带来更大增益

在均匀 iid 信源上，一个不断增长的短语上限配合一个廉价的长度符号，把冗余从 1977 年原始固定字段格式的 Ω(log B/B)——无论该格式使用何种短语上限——改进到 O(log log B/B)。这一比较隔离了历史长度字段的代价，论文指出，使用相同词元编码的单窗口编码器也能获得同样的增益。

第二项重编码针对游程。把单符号游程 (r,1) 写作 (1,r)，其中对数代价的计数 r 可以超过匹配上限，就能把具有 O(n^α) 个游程（0≤α<1）的输入编码为 O(n^α log n) 比特，而 1977 年格式在短语上限 Θ(log W) 且 W=o(n) 时需要 Ω(n)。扩展规则决定适用哪个结论：位置式 varint 或通用整数编码可以满足对数假设，而像 LZ4 匹配长度格式那样每增加 255 个符号用一个扩展字节，则要花费 Θ(r) 比特。若 g(r)/r→γ 且 Γ_n=o(n)，单游程解析在常量输入上的极限码率为 γ，只要 γ < c/L，就仍然能得到严格的常数改进。

对字段做 Huffman 编码降低周期输入码率

在全局 p 周期输入上，对带有最近距离并列规则的封顶解析的字段做 Huffman 编码，把大文件码率从固定宽度编码下的 Θ(B/W) 降到至多 3/W，其中包含表和帧结构。其机制是标准的条件化恒等式：对于有 M 个匹配、解码长度类 J 和距离符号 Z 的固定解析，条件化带来的理想经验节省为 M·Î(Z;J)，因为解码出的长度无需类别选择符就能确定 J。无约束的二进制 Huffman 编码会用若干舍入项改变这一节省，当单例字母表可以使用零比特时，每个舍入项都在 [0,M) 内；此外还必须计入额外的距离位、表头和格式限制。

论文对其测量结果所能说明的内容很谨慎。在使用 WZIP 编解码器的有界动态规划解析器时，把按长度分组的偏移表替换为一张表，会使 Silesia 语料上的压缩率下降 0.58%；而在偏移仍按组编码的前提下接纳每个距离上的每种长度，则压缩率保持不变。每次消融都会重新解析输入，因此论文说这指示而非隔离了条件化的效果。

完整的 WLZ 编码还能给出熵率估计量

在完整的 WLZ 编码之间进行选择，可以得到一个几乎必然且依均值一致的熵率估计量，并对固定的非均匀 iid 信源给出有限数据误差界。该估计量的最小比特变体对每个 B≤K_n≤log n 计算 C*_{B,n}，耗时 O(n log^3 n)。

该分析带有明确的适用范围条件。普适性和收敛性结论要求精确贪心解析；限制候选数、只保留最新哈希项、跳过插入或采用惰性匹配的实际编码器是有用的速度选择，但其输出不被假定等于参考解析，分析要么明确要求精确贪心解析，要么计入漏掉和放弃的匹配。游程编码的增益取决于所指定的普通上限，而周期输入的 Huffman 比较会改变可用的短语扩展。论文还指出了开放方向：在固定长度编码模型下，为校准窗口带来的固定信源节省寻找匹配的上下界；为依赖信源给出定量的重现尾部界和搜索损失界；以及在内存和时间约束下高效联合选择窗口大小与哈希链检查预算。

下一比特压缩增益究竟来自哪里

论文自身的优先级排序就是有用的要点。如果目标是更好的压缩率，窗口调度不是应当首先拉动的杠杆：它在所分析信源上的渐近严格增益是多项式量级的，而固定阈值阻碍排除了仅靠短匹配窗口获得 p>1 时冗余 O(B^−p) 的可能。词元编码才是杠杆——配合不断增长的短语上限的廉价长度符号，把均匀 iid 冗余从 Ω(log B/B) 移到 O(log log B/B)，而游程重编码把少游程输入从 Ω(n) 移到 O(n^α log n)。

窗口调度仍因另一个理由而有其价值：它限制短匹配历史，从而减少索引资源，并且在经过校准时相对于单窗口基线从不提高最小词元代价。因此决策按目标分化。选择依赖长度的窗口，是为了内存和搜索代价，同时保持 LZ77 的收敛阶不变；当目标是压缩率本身时，则选择词元编码。在期待窗口增益之前要检查的条件是改进不等式——被接纳的节省必须超过排除代价加上启发式超额再加上头部差异；在期待游程编码增益之前要检查的条件是扩展规则，因为每 255 个符号一个字节的格式要花费 Θ(r) 比特，会丧失对数假设。

本文引用的文献