固定位费用的LZ77最优解析

七个A，只需一个字面量加一次长回指，看上去已经很省。可是如果“长度6”本身比两次“长度3”贵，这个最少token的方案仍会多花一位。最优解析必须先说明在优化什么：同一份原文可以有很多token序列，只有码制固定以后，比较它们的bit总数才有确定答案。

形式陈述

先把价格写死

输入为字节串 $T[0..n)$ 、窗口上限 $W\ge0$ 和匹配长度上限 $C\ge0$ 。采用历史匹配接口的重叠语义。位置 $p$ 的字面量输出 $T[p]$ ；匹配 Match(ℓ,d)须满足

3\le\ell\le\min(C,n-p),\qquad 1\le d\le\min(W,p),\qquad T[p+i]=T[p+i-d]\quad(0\le i<\ell).

本页规定如下二进制payload，不包含外层文件头：

token	从左到右的比特	位数
`Lit(b)`	`0`，随后8位字节b	9
`Match(ℓ,d)`	`1`，随后 $\gamma(\ell-2)$ 、 $\gamma(d)$	$3+2\lfloor\log_2(\ell-2)\rfloor+2\lfloor\log_2d\rfloor$

对正整数 $z$ ，令 $h=\lfloor\log_2z\rfloor$ ；这里 $\gamma(z)$ 是 $h$ 个0后接 $z$ 的完整二进制表示，长 $2h+1$ 。例如 $\gamma(1)=1$ 、 $\gamma(2)=010$ 、 $\gamma(4)=00100$ 。这是常用的分组gamma写法；Elias原论文把这种排列记为 $\gamma'$ ，与其中交错排列的 $\gamma$ 码长相同。[2, §V]

解码时先数0，遇到第一个1后再取相同数目的后续位，得到该整数。两个整数码不需要分隔符；token首位又区分字面量和匹配。所有费用只依赖本token的长度、距离或字节，不会因先前token频数改变。这项条件是下面一维状态成立的关键。

optimal_parse(T,W,C)返回最小有效位数、一个达到它的token序列、全部后缀费用及恢复选择。相同位置的并列最优解不要求唯一：公开实现先选字面量，只在严格更省时替换，再按距离档、长度档顺序保留第一个胜者。

为什么只记当前位置就够

利用动态规划的状态充分性与反向求值，定义 $D[p]$ 为从已经正确恢复 $T[0..p)$ 的状态出发，编码剩余原文的最小payload位数。所有到达 $p$ 的合法解析都恢复同一个字节前缀；可用历史只由 $T,p,W$ 决定，与此前如何切token无关。价格也不依赖此前选择，所以这些历史可以合并为一个状态。

位置 $p<n$ 可以发字面量前进1，或发一个合法匹配前进 $\ell\ge3$ 。因每条边严格向右，位置图无环。基例及完整递推为

D[n]=0,\qquad D[p]=\min\left\{9+D[p+1],\ \min_{(\ell,d)\text{ 在 }p\text{ 合法}} \bigl(3+2\lfloor\log_2(\ell-2)\rfloor+2\lfloor\log_2d\rfloor+D[p+\ell]\bigr)\right\}.

从右到左求值。每个候选确实是一段合法token再接合法后缀，因此不会给出虚假低价；任取最优解析，其首token必在这些候选中，剩余部分若不是对应位置的最优后缀，就能替换得更省。两向论证给出递推正确性。[1, §5]

直接枚举所有距离和长度还很贵。接下来省的是检查转移的工作，并没有删掉某些合法长度。

距离档给一个最长见证

按 $k=0,1,\ldots$ 把距离分成

B_k=[2^k,\min(2^{k+1}-1,W,n-1)],

只保留非空档。该档所有距离的码长都是 $2k+1$ 。对每档运行前页的历史带扫描，取得每位置的最长长度 $M_k[p]$ 和见证 $q_k[p]$ 。[1, §5.2]

某个长度 $\ell$ 在该档可行，当且仅当 $3\le\ell\le M_k[p]$ 。必要性来自最大值定义；充分性来自见证的前 $\ell$ 个字节也匹配。故一个最长见证同时支持该档所有较短合法长度，且距离价格相同。这个替代只在同一档成立；全窗口任意最长见证可能来自更贵的距离档。

长度档变成一次区间最小值

对 $j\ge0$ ，等费用长度区间是

I_j=[2^j+2,\ 2^{j+1}+1].

例如 $j=0$ 只有长度3； $j=1$ 是4、5； $j=2$ 是6、7、8、9。与 $[3,M_k[p]]$ 相交得非空 $[L,U]$ 时，这整段token费用固定为 $3+2k+2j$ ，因此只需计算

3+2k+2j+\min_{L\le\ell\le U}D[p+\ell].

把已算好的 $(D[x],x)$ 存进区间最小值线段树，一次查询半开区间 $[p+L,p+U+1)$ ，同时得到最小费用与达到它的目的位置 $x$ 。同费用时按较小 $x$ 决胜。用该距离档见证输出 Match(x-p,p-q_k[p])，不需要为每个长度再查一个来源。

text

D[n] = 0; 其余位置暂存 infinity = 9n+1
for p = n-1 .. 0:
    best = 9+D[p+1]; choice = Lit(T[p])
    for each nonempty distance band k:
        M,q = precomputed_match[k][p]
        for each length-cost interval [L,U] clipped to [3,M]:
            suffix_bits,x = tree.minimum(p+L,p+U+1)
            candidate = 3+2k+2j+suffix_bits
            if candidate < best:
                best = candidate; choice = Match(x-p,p-q)
    D[p] = best; save choice; tree.assign(p,best)

查询时所有目的位置都大于 $p$ ，已经定值。各距离档、长度档分别不重不漏地覆盖其正整数范围，最长见证又完整覆盖该档可行长度，故分组后的最小值等于原递推。这里没有依赖“只保留最长边就行”的额外假设。

直觉

原递推像一张很密的价目表：每个距离、每个长度都写一行。同一个距离价格档内，来源是哪一个不重要，只要能复制所选长度；同一个长度价格档内，token价格也不变，差别全在落脚位置之后还要付多少。

于是先问“这个价格档最远能复制多长”，再问“允许的落脚区间中哪一格后续最便宜”。线段树没有替我们证明最优性，它只快速回答第二个问题。若遗漏一个价格变化点，或者把区间端点写错一格，再快的查询也只是在高效计算错误递推。

七个A的反向费用表与两条解析路径；一个长回指花16bit，两个长度3回指花15bit — 长度价格档与后缀最优费用

例子与边界

七个A：少一个token，却多一位

取 $T=\texttt{AAAAAAA}$ 、 $W=8,C=18$ 。贪心先发 Lit(A)，再用距离1一次复制长度6。费用为

9+\bigl(1+|\gamma(4)|+|\gamma(1)|\bigr)=9+7=16.

而 Lit(A), Match(3,1), Match(3,1) 花 $9+3+3=15$ 位。完整后缀表是

p	0	1	2	3	4	5	6	7
$D[p]$	15	6	5	5	3	18	9	0

$D[5]=18$ 并非笔误：只剩两个A，长度下限3使它们只能分别发字面量。 $D[p]$ 没有随位置单调变化的保证，不能把每个档的最右端当最优目的位置。

在 $p=1$ 、距离档 $[1,1]$ ，最长长度6。三个长度档的候选分别为：长度3到 $p=4$ ， $3+D[4]=6$ ；长度4、5到 $p=5,6$ ， $5+\min(18,9)=14$ ；长度6到末尾， $7+D[7]=7$ 。最短的这个合法匹配反而给出最佳首步。

逐位编码结果可以直接核查：

text

贪心：001000001 | 1001001       共16位，payload十六进制20c9
最优：001000001 | 111 | 111     共15位，补1个0后十六进制20fe

两份payload都占2个物理字节。结论是一位有效payload的节省，不是一字节文件大小的节省，更未计入外层元数据。

最长见证不能跨价档复用

前页 ABAABABA 在 $p=5$ 的全窗口见证给长度3、距离5，其token费7bit；距离带 $[2,3]$ 同样支持长度3，却只收5bit。本页先对每档求最长值，保留了这个区别。把所有距离合并再用一个见证计价，会在进入DP以前就丢掉可行的低价边。

空输入与模型变化

空串的答案为0位、空token与空payload。 $W=0$ 、 $C<3$ 或没有长度至少3的历史匹配时，全部发字面量，费用恰好 $9n$ 。因此 $9n+1$ 是未定状态的安全无穷大哨兵，不需要假定数据能被压短。

即使正文相同，若后续码价会随token频数、字典状态、分块选择或前一个距离改变，仅有 $p$ 就未必充分。DEFLATE的长度/距离符号、扩展位、Huffman表和块头不同于本页gamma码；尤其动态表涉及整块统计。不能把本页最优性称作“最优DEFLATE”或“所有压缩器的最优解析”。[3]

推论与应用

从选择恢复token，再恢复字节

每位置保存的选择都达到 $D[p]$ 。从0开始沿它前进，步长至少1，至多经过 $n$ 个token到达 $n$ 。把各步等式 $D[p]=c+D[p']$ 相加，中间后缀项抵消，得到token总价恰为 $D[0]$ 。匹配来源来自相应距离档的合法最长见证，缩短到所选长度仍合法，因此这条恢复路径确实重建原文。

公开 encode_tokens校验token结构、窗口、长度和总展开长度，输出有效位串、有效位数和补零打包的十六进制payload；它不拿一个未提供的原文验证token内容。对解析器产生的token，正确性由上面的匹配见证保证，再以实际解码比较原文复核。

解码函数采用有界解压的先验预算检查：先核验声明输出长度、有效位数、实际payload字节数和末尾零填充，再读token。gamma的前导零计数也受本次允许最大值的位长约束；距离不得超过已经输出的窗口，长度不得超过上限或剩余输出，所有检查在复制之前完成。最后必须恰好用完有效位，尾随有效位不能被静默忽略。

这只是一个有外部参数的payload接口。接收方仍需被明确告知 $n,W,C$ 和有效位数；它们如何版本化、传输和保护，属于压缩流封装问题，本页没有另造自描述文件格式。默认预算为最多100000输出字节和1000000有效位，调用者可以另给非负整数上限；这不是取消资源限制的承诺。

真实算法账单

令 $D_{\max}=\min(W,\max(n-1,0))$ 。若其为0，令 $K=0$ ；否则 $K=1+\lfloor\log_2D_{\max}\rfloor$ ，即距离档数。令 $L_{\max}=\min(C,n)$ ；若 $L_{\max}<3$ ，令 $J=0$ ，否则 $J=1+\lfloor\log_2(L_{\max}-2)\rfloor$ ，即最多遇到的长度档数。

后缀预处理花 $O((n+1)\log(n+2))$ ； $K$ 次历史带扫描花 $O(nK\log(n+2))$ ；每位置至多 $KJ$ 次区间查询和一次赋值。因此核心总时间可统一写为

O\bigl((n+1)\log(n+2)+nK(J+1)\log(n+2)\bigr).

公开实现保存全部距离档的 $n$ 项匹配表，连同索引、DP、选择和token，共占 $O(n(K+1)+1)$ 个字。不能只报一棵树的线性空间而漏掉这张表。开启DP候选轨迹再增加至多 $O(nKJ)$ 项记录；本程序不会在这些扫描中开启前页的完整活动集合轨迹。

若payload有 $B$ 个有效位，打包与解码分别计入位串处理；解码时间为 $O(B+n+1)$ ，本参考器同时保存位串及完整输出，占 $O(B+n+1)$ 空间。最优payload由全字面量上界保证 $B\le9n$ ；任意外部token序列或贪心解析不应未经证明就使用这个界。大整数的位运算、JSON打印和测试oracle另外计费。

Ferragina等人的算法对其指定费用模型进一步压缩候选并达到更强的时间空间界。本页保留所有长度区间，用较直接的距离档扫描与树查询，明确支付上述对数因子；最小匹配长3也要求谨慎处理被截短至1或2的候选，不能不经证明搬用别的稀疏化规则。[1]

完整终点任务要求把活动历史、位价递推、token恢复和预算拒绝串成可重复的执行证据，而不只给一个“比贪心更省”的数字。

参考资料

[1] Paolo Ferragina, Igor Nitto and Rossano Venturini, On the Bit-Complexity of Lempel-Ziv Compression, SIAM Journal on Computing 42(4), 2013, pp. 1521–1541，DOI 10.1137/120869511。§2 的允许重叠变体，§3 的费用问题，§5 的最短路表述，§5.2 的等距离费用窗口。本文固定了自己的token语法并给出独立区间完备性证明，没有声称实现论文的最强界。
[2] Peter Elias, Universal Codeword Sets and Representations of the Integers, IEEE Transactions on Information Theory 21(2), 1975, pp. 194–203，§V，印刷页199的 $\gamma'$ 排列与 $1+2\lfloor\log_2z\rfloor$ 码长。这里仅使用该整数表示，不借此宣称整份压缩结果具有通用最优性。
[3] L. Peter Deutsch, RFC1951, §§3.2.5–3.2.7：DEFLATE的长度/距离扩展位和固定、动态Huffman块模式，与本文固定gamma-payload区分。

形式陈述 ​

先把价格写死 ​

为什么只记当前位置就够 ​

距离档给一个最长见证 ​

长度档变成一次区间最小值 ​

七个A：少一个token，却多一位 ​

最长见证不能跨价档复用 ​

空输入与模型变化 ​

从选择恢复token，再恢复字节 ​

真实算法账单 ​

反向链接