如果你跟我一样当年在信息论教材里第一次看到字典编码这四个字大概率会觉得它跟哈夫曼编码、算术编码比起来有点不够数学。熵编码公式一套套字典编码听起来像是在查字典像个文科操作。但后来我拿一份几十MB的服务器日志做压缩实验gzip 居然压掉了 90% 以上而按香农熵算出来的理论下限根本解释不了这个结果。我重新翻开 Ziv 和 Lempel 那两篇经典论文才意识到字典编码其实是信息论里一条完全不同的路它不统计概率不看符号分布甚至在编码的时候根本不关心熵是多少。原理简单得惊人——如果一段数据曾经出现过那以后再提到它时只需要说和前面那个一样就够了。这篇文章我会从信息论和工程落地两个角度把字典编码的完整来龙去脉拆开讲清楚包括 LZ77、LZ78、LZW 这些经典算法到底怎么工作、怎么手动复现以及真要在项目里选型和排错时该注意什么。1. 为什么信息论要讲字典编码1.1 从冗余说起字典编码解决的不只是压缩率信息论与编码课程里香农熵告诉你一个信源如果符号概率分布已知那么它的平均编码长度下限就是 H(X) -Σ p(x) log p(x)。哈夫曼编码和算术编码做的事情本质上都是围绕这个概率分布去分配码长让高频符号用短码低频符号用长码。这套理论非常优美但它有一个前提你得先拿到信源的概率分布。现实中的数据尤其是文本、日志、配置、结构化二进制很难准确建模出概率分布。更麻烦的是这类数据的冗余往往来自结构而不是频率同一个词反复出现同一句话隔几行又来一遍同一个错误码加同一段堆栈信息重复几百次。你用哈夫曼编码当然能捕捉到这个词出现得多但要捕捉这段序列整体重复出现过这种高阶相关性熵编码的模型复杂度会爆炸。字典编码的切入角度完全不同它直接在数据里找曾经出现过的片段并用一个短引用替代。从信息论视角看这相当于对信源做了一种在线估计——不需要先验概率就能逐步逼近信源的熵率。所以信息论教材里讲字典编码核心价值是引入通用编码这个概念。LZ 系列的字典编码可以在不知道统计模型的情况下对平稳遍历信源达到渐进最优的压缩效果。说人话就是它自作主张地建立模型、发现规律数据越长压缩得越好。这也是为什么字典编码后来成为文件压缩、网络传输、图像存储里最常用的无损压缩基石。1.2 熵编码与字典编码的分水岭要不要概率表把这两类编码摆在一起对比你会看到非常鲜明的边界。熵编码的思路是对单个符号或有限个符号的组合编码码长取决于概率负对数。它的天花板是香农熵需要统计模型代表算法是哈夫曼、算术编码、范围编码。字典编码的思路是把一段已出现过的符号序列整体替换为索引或距离长度不需要概率分布代表算法是 LZ77、LZ78、LZW、LZSS、Deflate。举一个生活里的例子哈夫曼编码像输入法里的常用字排序把高频率的的、了、一放在最顺手的键位字典编码像你跟朋友约饭说老地方见双方都知道老地方具体指哪个餐厅不用把地址重新念一遍。这两套方案还有一个容易被忽略的关系它们不是互斥的而是可以叠加。工业级的 Deflate 压缩流程就是先做一轮 LZ 字典编码把重复片段变成引用再对引用流做一轮哈夫曼编码。这样既吃到了结构冗余的红利又吃到了频率冗余的红利。理解这一点你就抓住了现代压缩算法的骨架之后看任何压缩软件都能一眼看出它到底在做什么。2. 两大流派LZ77 系与 LZ78 系2.1 LZ77 的滑动窗口用历史当字典LZ77 是 Jacob Ziv 和 Abraham Lempel 在 1977 年提出的它的核心思想是把字典隐式地放在滑动窗口里。编码端维护一个窗口分成两部分前面的历史区里面是已经编码过的数据后面的前瞻区是接下来要编码的数据。每次编码时在前瞻区找最长的前缀串让它能在历史区里匹配到然后输出一个三元组(距离, 长度, 下一字符)。距离是匹配串到当前位置的偏移量长度是匹配上的字符数下一字符是匹配串之后紧跟的那个字符。这个三元组里的第三项下一字符第一次接触会觉得很奇怪匹配都找到了为什么还要额外输出一个字符这是经典 LZ77 为了处理匹配不上和推进位置做的设计。比如最开始几个字符根本没有历史可参考就必须用(0, 0, c)这种形式把字面量输出出去。解码端拿到三元组后先按照距离和长度从历史里复制出一段内容再把下一字符追加在后面这样历史区就同步更新了。整个过程中解码端不需要任何额外信息就能和编码端构建出完全一样的窗口状态。工程实现时窗口到底设多大是一个关键参数。距离字段的位宽直接决定最大可回溯距离Deflate 定的窗口是 32KBLZMA 的窗口能到 4GB 量级。窗口大能发现更远距离的重复但搜索范围变大CPU 开销也大内存占用更明显。这是压缩率与速度之间最基础的一笔账。2.2 LZ78 和 LZW 的动态字典把短语表显式建出来LZ78 是 Ziv 和 Lempel 在 1978 年提出的另一种思路。它不搞历史窗口而是在编码过程中动态维护一张短语表。每条短语由前缀索引 一个字符构成。编码时从当前输入里取出最长的、能在短语表里找到的前缀输出它的索引然后再读入下一个字符把这个前缀 下一个字符作为新短语加入表里。解码端只需要跟着建立同样的表就能还原数据。LZW 是 Terry Welch 在 1984 年对 LZ78 的改进也是大众最熟悉的一个名字GIF 和 TIFF 都用它。LZW 的改进很聪明字典初始化时就把所有单个字符都放进去编码时只输出匹配到的短语索引不再输出下一个字符。因为下一个字符其实早就单独存在于字典里了省略它不影响后续建模却能让输出流更紧凑。代价是解码端多了一个著名的 corner case如果读到的索引恰好是下一个还没创建出来的字典项就必须猜它是上一个输出加上它自己的第一个字符。这个小坑当年坑过无数手写 LZW 解码器的人。2.3 为什么工业界更偏爱 LZ77 系从教学上讲LZ78 和 LZW 更直观因为字典这个词本身就直接对应一张表。但真实世界里的压缩工具绝大多数走的都是 LZ77 这条路原因有三点。第一解码速度。LZ77 的解码本质是内存拷贝知道距离和长度直接从历史区复制数据几乎没有查表开销也不存在字典增长带来的哈希查找。LZ78/LZW 的解码必须维护和查询一张动态表表大了之后哈希碰撞和内存管理都是麻烦。第二内存可控。LZ77 的字典就是固定大小的滑动窗口内存上限一开始就卡死了LZ78/LZW 的表会不停增长如果输入数据量很大要么定期清空重建要么承担越来越高的内存和查找成本。第三组合能力。LZ77 产生的(距离, 长度)流很容易再接一层熵编码Deflate 就是这么做出来的。LZ78/LZW 的输出是一个个短语索引索引空间天然很大二次压缩的效果没那么好。所以你看今天几乎每个操作系统里都有的 gzip、ZIP、PNG底层全是 LZ77 的变种。LZW 只在历史遗留的 GIF、TIFF 和一些老压缩工具里存在。这里还带出一个工程上绕不开的话题LZW 早年在多个国家有软件专利争议虽然专利已经全部过期但它给大家的教训是——选压缩算法之前一定要先看一眼授权和专利状态不然上线之后换算法是很痛苦的。3. 手把手拆解一个完整的字典编码流程3.1 LZ77 手动编码实例理论说得再多不如手算一个例子。我用字符串abcabcab来走一遍经典 LZ77 编码流程。为演示方便假设窗口足够大不设距离和长度上限并且仍采用带下一字符的经典三元组格式。位置 0历史为空a 匹配不到任何前缀输出(0, 0, a)把 a 滑入历史。位置 1历史是ab 匹配不到输出(0, 0, b)。位置 2历史是abc 匹配不到输出(0, 0, c)。位置 3剩余部分是abcab。在历史abc里找最长前缀abc能完全匹配到长度为 3距离为 3。匹配之后的下一字符是 a所以输出(3, 3, a)。位置 6剩余部分是ab。在历史abcabc里ab能匹配到距离是 3长度是 2。最后一个字符之后没有下一字符实际编码会特殊处理这里用(3, 2)收尾。所以码流语义上可以写成(0,0,a) (0,0,b) (0,0,c) (3,3,a) (3,2)。解码的时候前三个三元组直接输出 a、b、c遇到(3,3,a)回退 3 个字符得到abc然后追加 a输出abc遇到(3,2)再回退 3 个字符得到ab最后拼起来就是abcabcab一字不差。这个例子最重要的启发是解码端不需要知道编码端是怎么搜匹配的只要拿到(距离, 长度)就能用自己手里已经还原出来的历史数据完成重建。这也是 LZ 系列能够无损解码的本质——字典是编码和解码端协同推进出来的不是预先约定好的。3.2 LZW 手动编解码实例顺便拆掉那个经典的坑LZW 我再用一个非常短的串ABABAB演示。初始字典很简单索引 0 对应A索引 1 对应B下一个可用索引是 2。编码过程读A前缀为空当前串为A。读BAB不在字典里输出A的索引 0把AB加入字典作为索引 2当前串重置为B。读ABA不在字典里输出B的索引 1把BA加入字典作为索引 3当前串重置为A。读BAB在字典里索引 2当前串变为AB。读AABA不在字典里输出AB的索引 2把ABA加入字典作为索引 4当前串重置为A。读BAB在字典里当前串变为AB输入结束输出AB的索引 2。输出索引序列是0 1 2 2。解码过程相反跟着建表就能还原成ABABAB。刚才提到 LZW 解码端著名的 corner case出在解码时遇到一个还没创建的索引这个局面。举个例子编码端一旦在字典里刚加入一个新短语紧接着又遇到了同样的模式它就会立刻输出那个刚加入还没来得及广播给解码端的索引。解码端发现自己要读的索引比当前字典多一位不能慌处理规则就是输出上一个输出 上一个输出的第一个字符。这规则听着绕但在代码里其实就是一行判断。我当年第一次实现 LZW 时在这条上卡了一晚上日志里怎么都对不上后来才意识到是自引用问题。如果你也在写 LZW请把这条规则单独注释出来。3.3 编码参数怎么选才科学在手写或调参 LZ 算法时通常会碰见几个关键参数它们的取值直接决定压缩率和速度的平衡我按实际经验拆一遍。窗口大小。窗口决定能回溯多远的重复窗口越大越容易找到长距离匹配但搜索成本上升。Deflate 用 32KB 窗口这是在 90 年代的硬件条件下做的折中LZMA 的窗口可以调到几百 MB就是为了在压缩率上压榨到极致。你在嵌入式或者实时系统里如果内存吃紧就主动把窗口调小哪怕压缩率降低也比掉线强。最大匹配长度。Deflate 限制单次匹配最大 258 字节超过 258 字节的重复串会拆成多次匹配。为什么是 258因为长度字段的 Huffman 编码有长度限制超过这个值以后多编码的 bit 数反而亏。所有参数设计背后都是用多少 bit 做这个事的算账题。最小匹配长度。LZSS 一般规定匹配长度至少为 3 才用(距离, 长度)形式输出否则就用字面量。原因是距离和长度两个字段加起来至少占用 2-3 字节如果只匹配到 1-2 个字符输出匹配反而比直接写原文更费空间。这个阈值不是拍脑袋定的它是一个匹配引用的字节开销算出来的。哈希链长度和 nice length。工程实现里查找匹配通常用哈希链比如 zlib它在压缩等级参数里隐藏着这些调节项。哈希链越长越可能找到更长匹配但 CPU 时间线性上升。nice length 表示匹配长度达到多少就不用再继续搜了直接限制搜索深度。zlib 从 level 1 到 level 9 的差异本质就是这些内部参数的组合而不是算法上的大改。4. 从玩具到工业级LZSS、Deflate、LZMA 做了什么4.1 LZSS用标记位解决冗余的冗余经典 LZ77 有个明显浪费没有匹配时也要输出(0, 0, c)三个字段而这三个字段里有两个是纯粹占位的。LZSSStorer 和 Szymanski1982改进了这一点。它的做法是给每个输出项前面加一个标记位0 表示接下来是一个原始字节1 表示接下来是一个(距离, 长度)匹配。这样一来字面量abc就变成0a 0b 0c比经典 LZ77 的(0,0,a)(0,0,b)(0,0,c)紧凑得多。LZSS 还做了另一件事只有当匹配长度超过阈值时才输出匹配否则依然用字面量。这个阈值一般取 2 或 3。表面上看这是细节优化实际上它让 LZSS 在短文本上不会出现压缩后反而变大的尴尬。很多入门教程把 LZSS 当成 LZ77 的微小改动但它才是现代 LZ77 系变种的真正雏形Deflate 里采用的就是 LZSS 这种标记位 匹配/字面量的形式而不是教科书里的经典三元组。用前面的例子对照一下abcabcab用 LZSS 编码会是字面量 a、字面量 b、字面量 c、匹配(距离3, 长度3)最后剩下的ab因为长度可能低于阈值就继续用两个字面量处理。整体多了一个标记位流但少了很多无意义的零。4.2 Deflate字典编码加哈夫曼的黄金组合Deflate 是 Phil Katz 在 90 年代为 ZIP 格式设计的算法也是 gzip、PNG 图像的核心。它的工作流程分两层第一层做 LZSS 形式的字典编码把输入转换为字面量 / 匹配长度 / 匹配距离三类符号第二层用哈夫曼编码对这三类符号做熵编码。其中距离和长度可以共用一棵哈夫曼树也可以分开建树还引入了动态哈夫曼表和静态哈夫曼表的切换。为什么这个组合能成为事实标准因为它把两种正交的冗余都吃掉了。LZ77 解决的是重复串的结构冗余哈夫曼解决的是符号出现频率的统计冗余。单纯做字典编码字面量和距离长度字段的分布仍有规律的偏斜熵编码能把这部分水挤干。反过来单纯做哈夫曼遇到很长的重复段会很无力因为模型根本记不住一个超长符号。二者结合恰恰是信息论里信源编码定理和通用编码思路在工程上的完美落地。PNG 的例子特别能说明问题PNG 内部用 Deflate 压缩像素数据但在交给 Deflate 之前会先对每一行像素做滤波把像素值转成和相邻像素的差值。为什么要这么做因为图像相邻像素高度相关直接压缩 RGB 值Deflate 能发现的重复很少先做差分数据变成大量接近零的差值Deflate 和各种熵编码都能发挥更好。这说明字典编码不是万能药它的效果高度依赖输入的可压缩结构预处理往往比改压缩级别更关键。4.3 现代方案LZMA、zstd、Brotli、LZ4 都在改什么到了更现代的压缩算法你仍然能看到 LZ77 的影子只是每一层都被重新打磨过。LZMA 用 LZ77 大窗口最大 4GB加范围编码范围编码可以理解成更接近算术编码的熵编码器。它把字典匹配做到更极致所以 7z 的压缩率通常明显优于 ZIP但编码速度很慢适合压缩一次、解压很多次的场景。zstd 是 Facebook 开源的算法内核还是 LZ77但用了更高效的数据结构和 FSE 熵编码能在压缩率和速度之间取得很好的平衡现在大量用于日志、缓存、数据交换。Brotli 是 Google 为 Web 传输设计的也是 LZ77 变种最大的特色是内置了一个包含常用英文单词和 HTML 标签的预制字典所以压缩网页特别有效。LZ4 和 Snappy 则是另一个极端它们只做非常简单的 LZ77 匹配不追求高压缩率追求的是极快的解压速度在数据库、消息队列和实时日志里用得非常多。这里放一张表方便选型时直接看算法核心思路典型场景特点LZSSLZ77 标记位教学、早期压缩器结构简单是 Deflate 前身DeflateLZSS HuffmanZIP、gzip、PNG压缩比与速度均衡LZMALZ77 Range Coder7z、XZ压缩率高编码慢zstdLZ77 FSE / Huffman日志、大数据中间件速度快压缩率接近 LZMABrotliLZ77 预置字典Web 传输对网页文本友好LZ4极简 LZ77实时缓存、消息压缩率低但解压极快5. 实践中踩过的坑与排查技巧5.1 压缩率突然变差的常见原因很多人把数据丢给压缩工具发现压缩率跟文档里写的差很远就开始怀疑算法有问题。其实大部分情况是数据形态不合适。随机数据和已经加密的数据压缩后不仅不会变小还可能略微变大因为压缩器要把自己的参数和表塞进输出流里。这个要先排除。第二种常见情况是重复模式存在但距离超过窗口。比如一个超大日志文件里某段堆栈信息每隔 1MB 出现一次Deflate 的 32KB 窗口根本看不到它压缩率自然上不来。解决办法是换用 LZMA 或 zstd 这类支持大窗口的算法。第三种情况是有重复但被噪声打断比如每行日志都带时间戳时间戳每秒都在变相同前缀被切成了一个个小块。遇到这种情况我一般会先做字段拆分把时间戳、随机 ID 这类变化快的部分单独拿出来剩下的部分再交给字典编码效果会明显好很多。另外要提一个字节层面的坑UTF-8 编码的汉字一个字符占 3 个字节字典编码确实能发现字节级的重复但它不懂汉字这个概念。如果数据里有很多常见汉字词理论上用字符级分词再压缩效率更高但工程上很少这么干因为字典编码加预处理已经足够好性价比最高。5.2 解码端出错怎么定位压缩流一旦损坏LZ77 系解压会出现一错到底的连锁反应因为每个匹配都依赖前面的历史错一个字节后面全乱。所以实际容器格式都会带校验比如 gzip 有 CRC32、ZIP 和 7z 也有自己的完整性校验。如果做的是自定义协议一定要在压缩流之外加上自己的校验和版本号否则排错会非常痛苦。LZW 解码还有一个很特别的错误特征如果遇到未知索引很多人第一反应是数据坏了其实在未损坏的情况下也可能触发这就是前面说的prev prev[0]自引用规则。我的调试建议是在编解码两端各维护一份字典快照每处理一个符号就打印当前处理的索引、输出内容以及字典长度。找到第一个不一致的位置基本就是算法逻辑没对齐如果字典完全一致但解出来乱码再怀疑字节序和位宽设置。还有一个小技巧代码里把匹配长度和距离的上限写成常量并加运行时断言。很多隐藏 bug 来自编码端输出的距离越界、长度超过上限而这些断言能第一时间把问题暴露出来而不是等数据满了才爆炸。5.3 字典编码的边界内存、实时性、硬件场景字典编码不是万能的工程选型时要考虑三件事。内存。LZMA 的大窗口意味着大字典动辄几百 MB嵌入式设备根本扛不住。相反LZ4 可以把内存压在几十 KB适合单片机场景。选型前先问一句压缩和解压两端的内存预算各是多少解压端内存其实比压缩端更关键因为解压经常运行在用户设备上。实时性。流式传输场景不能等整块数据都到齐才开始压缩需要把数据切成块每块独立压缩。块越大重复跨越块边界的机会越多压缩率越高但延迟和内存也随之上升。实时视频或网络传输中一般选择 16-128KB 的块牺牲一点压缩率换取低延迟。要注意的是分块压缩的缺点不只是压缩率下降还有每块都要额外存一个头部、各块的压缩率还可能波动这些在设计协议时都要预留字段。硬件指令集。现代 CPU 上 zstd 和 LZ4 都有相关的 SIMD 优化版本解压速度可以跑到 GB/s 级别但如果你用的老平台不支持新指令压缩效率会明显下降。做底层库适配时最好用带运行时检测的构建方案对不同 CPU 使用不同的汇编内核。6. 说点我的真实选型体会6.1 我什么时候用字典编码什么时候不用做项目这么些年我慢慢形成了一套很朴素的选型经验。遇到文本、日志、配置文件、数据库导出这类人可读的数据二话不说丢给 zstd 或 gzip几乎总能拿到不错的压缩率而且解压快适合日常备份和传输。如果是要长期归档、压缩一次保存十年我会选 LZMA 或 xz因为它压缩率更高哪怕编码慢一点也没关系反正只压一次。如果数据要频繁读写、追求低延迟比如缓存或消息队列那就用 LZ4压缩率低一点无所谓但绝对不能拖慢主流程。反过来遇到已经有损压缩过的图片、视频、音频文件我一般不会再做字典编码。JPEG、MP3、H.264 这些格式内部已经去掉了大量冗余硬压只会浪费时间压缩率还很难看。另外如果输入是不可信的外部数据比如用户上传的文件服务端解压前一定要做大小限制和压缩比检查不然一个几 MB 的压缩炸弹就能把服务器内存打满。这些都是吃过亏才记住的。6.2 一个可以立刻上手的实验建议如果你想在几分钟内直观感受字典编码的能力边界我建议写一段 Python 脚本用同样的数据分别跑 zlib、lzma 和一个快速压缩器对比一下import lzma import zlib data open(your_file.log, rb).read() for name, compress in [ (gzip/zlib, lambda d: zlib.compress(d, level9)), (lzma, lambda d: lzma.compress(d, preset9)), ]: out compress(data) print(f{name}: {len(data)} - {len(out)} ({len(out) / len(data) * 100:.1f}%))跑完你会发现同一个文件在不同算法下的压缩率差异很大这很正常。再用同一个算法去压原始日志和按行排序后的日志大概率排序后的压缩率更好因为相同内容被聚拢了。这个实验最直接的价值是让你理解字典编码的收益永远来自数据中的重复结构预处理比调参更值得花时间。理解了这一点你就不会再对着参数表盲目折腾了。最后说句题外话。我这些年踩过的压缩相关的坑十个里有八个不是算法本身的问题而是没想清楚数据里到底有什么样的重复。字典编码再聪明它也只能发现曾经出现过的模式它不会帮你创造模式。所以下次拿到一份压不动或者压缩率很差的数据先别急着换算法先把数据形态翻出来看一遍问自己三个问题重复在哪里距离有多远有没有噪声打断把这三个问题答明白了选型就是顺理成章的事。