压缩最优解析原理:为什么找到最长匹配不一定压得最小

贪心策略为什么会走进死胡同

大多数压缩器在处理一段数据时,做的第一件事是找最长匹配:往回看已经出现过的内容,只要能对上就一直延伸,直到接不上为止。看上去这很合直觉——匹配越长,需要记下来的东西就越少,省的字节自然越多。

问题在于"省得越多"这个前提本身就不成立。压缩器最终要写进输出流的不是"我引用了多长的旧内容",而是"在当前的概率模型下,这个选择要花多少比特"。而比特花费并不随匹配长度单调下降。当熵模型认为你接下来要写的那个字很常见时,把这一个字当作字面量直接写出去,可能比为一个短匹配付出"长度标记加距离标记加长度扩展位"的固定开销更便宜。

于是就出现了典型的贪心陷阱:每一步单看都选了当下最省的那个,合起来却不是全局最省。有点像装箱——前几个箱子塞得很满,到了后面剩下的零碎物品再也放不下,最后多出一整个箱子的体积。

把每一次选择都换算成代价

最优解析要做的,就是把这个"省不省"的模糊直觉,换成一个可以计算、可以比较的数字。

对每一个候选决策,压缩器估算写出它所需的信息量。这笔账大致分几笔:如果决定引用一段历史,就得写清楚"往回多远"和"匹配有多长";如果决定直接写字面量,就得按这个字符在当前上下文下的出现概率付出对应的比特数;而每种决策的分段边界本身还要花额外代价去标记,因为解码器需要知道哪里是引用、哪里是字面量。

有了统一的尺度之后,整个问题就变成了一个纯数学命题:在所有能表达这段输入的表示方案里,挑总代价最低的那一个。这个命题可以用动态规划一类方法求解——对每个位置,枚举所有可行的决策,算出一个延伸方案,再从中取最优。得到的不再是"每一步最贪心"的拼接,而是一个整体协调过的表示序列。

代价从哪里来:字典和熵模型各出一份账

理解最优解析的关键,是看清那笔"代价"由谁定。字典阶段和熵编码阶段不是各管一摊,而是共同参与了这个决定。

字典阶段负责回答"有哪些候选可选"。它维护的匹配查找结构,决定了一个位置向前能延伸出哪些长度的匹配,以及它们各自的距离。不同的查找策略——比如走哈希表、哈希链还是树结构——会给出略有差异的候选集合,候选集合的宽窄直接决定了后面优化的天花板。LZ77 匹配查找的三条路线里专门拆过这几条路线的取舍。

熵编码阶段负责回答"每个候选值多少钱"。它把最近见过什么、当前处于什么上下文、这类字节平时有多常见,统统折算成概率。上下文越具体,估出来的概率越准,同样的决策开销就越低。LZMA 的区间编码与字面量上下文建模展示的就是这类建模思路——判断某个字面量该花多少比特,靠的是它前后环境的统计规律。

两者一叠加,权衡就出现了:一个很长但很远的匹配,距离标记贵;一个中等长度但刚出现过的匹配,距离几乎免费;一处字面量密集、上下文又高度可预测的区域,直接写字面量反而划算。字典编码与熵编码的分工讲的就是这条流水线上两种引擎各自的职责。

解析器要在一堆候选里做组合决策

有了代价函数,事情还没有结束,因为代价之间会互相影响。

上一处选择引用了一个很远的距离,它就改变了当前的历史指针位置;这一步压缩得越好,下一步能看到的"已经出现过的内容"就越完整,可用的匹配也就越多。局部最优和全局最优在这里纠缠在一起,一个解在某个前缀上略差,却可能让后面整段都更顺。

这也是最优解析计算量大的原因:它要在候选之间做组合权衡,而不是各点独立地挑一个。代价模型也并非一次算定,而是随着解析过程不断更新——本质上是在"用未来的信息修正当下的判断"。

值得注意的是,这套权衡是有边界的。当数据本身已经很接近随机,字典里根本没有可复用的结构,可选的决策本来就很少,再优化也榨不出油水。有些文件就是压不动这件事,根子在这里,而不是算法不够聪明。

对使用者的实际意义

最优解析是一层藏在格式内部的实现细节,普通用户看不到它的中间过程。但知道它的存在,能解释几个常见现象。

一是同样内容的文件,不同工具压出来的大小不完全一样,有时候差距还挺明显。除了匹配查找策略不同,优化解析的激进程度也不同——它是拿更多计算换更小的输出。

二是"压缩等级"这个选项之所以影响的不只是速度,还在于不同等级往往对应不同的候选集宽度和代价模型精度,最终落到的解析结果自然不同。等级越高不代表一定更好,只是把更多的可能性摆上了台面让代价函数去挑。

三是格式本身承载了一部分能力。ZIP、GZIP、PNG 背后共享的是同一类字典加熵编码的引擎思路,而更新的格式把更多选择权交给了编码端——字典怎么建、代价怎么算、决策怎么拆,都可以由压缩端动态调整。这也是为什么换用不同的压缩工具去压同一份文件,结果会有肉眼可见的差别。想要按自己的需求权衡体积与耗时,可以看看文件压缩里的相关设置。

理解这一层之后,再看到"某个文件压了之后几乎没变小",就更容易判断出原因:要么数据本身已经接近不可压缩,要么所用的格式没有把优化解析的余量用出来。