我先从一个实际场景说起你手上有一份反复出现信息论基础这个词组的文本用常规的哈夫曼编码压完总觉得体积还是偏大。原因在于哈夫曼这类熵编码只盯着单个符号的统计概率它根本看不到信息论基础这四个字作为一个整体反复出现这件事。而字典编码恰恰就是为解决这种符号之间的重复模式而生的。在信息论的框架里字典编码属于典型的把冗余搬进字典的思路它不依赖消息源的精确概率模型而是通过建立一张动态或静态的字典把重复出现的字符串替换成更短的索引号从而实现压缩。这篇文章就把字典编码从原理到实现、再到工程里常见的坑完整拆一遍。1. 为什么哈夫曼不够用字典编码的立足点1.1 熵编码的局限我在信息论基础课上第一次接触无损压缩时先学到的就是香农熵和哈夫曼编码。理论上如果信源符号的概率分布已知熵编码能把平均码长逼近到熵值附近。但这里有个前提信源模型是符号独立或至少是一阶马尔科夫的。换句话说哈夫曼把每个字符当作独立个体来处理字符之间的关联关系完全被忽略了。可现实中的文本、代码、日志、结构化数据根本不是独立符号的随机串。比如常见的英文单词the、ing中文里的我们、因为它们作为整体出现的频次极高。这时候如果只看单字符频率哈夫曼至多给常用字符分配短码却无法利用字符组合本身的更高阶冗余。换句话说熵编码的上限受限于你所选择的信源模型。你选的模型越简单能压掉的冗余就越少。字典编码直接换了个思路我不去猜概率分布而是把已经出现过的一长串字符当作一个整体记住。下次再遇到同样的串就用一个指向字典项的编号代替。这一步跳过了概率模型跳过了一阶/二阶统计直接从重复入手。1.2 字典编码的直觉字典这个词大家都不陌生。你背过四六级单词书里面每个词条对应一个解释。压缩里的字典也一样只不过词条不是单词而是任意长度的字符串。编码器维护一张表表里每个条目都有一个编号。遇到待压缩数据时先尝试匹配字典里最长的条目若能匹配就输出该条目的编号若不能匹配就把它加入字典或忽略继续推进。这种思路在信息论基础中有一个很直观的解释一个符号串如果反复出现说明它不是随机的而是有结构、有记忆的。字典编码实际上是在隐式估计条件概率——在已经读过前文的情况下下一个最可能出现的字符串是什么。你不需要显式地计算概率只需要维护出现过什么。当然字典编码的字典从哪来如何匹配如何表示匹配结果——这就是下面要展开的核心细节。2. 两大流派LZ77的滑动窗口与LZ78的字典树2.1 LZ77的核心思想1977年Jacob Ziv和Abraham Lempel提出了LZ77算法。它的核心机制叫做滑动窗口。你可以把它想象成一台在数据流上移动的显微镜当前正在编码的位置有一个前视缓冲区而在这之前的一段时间里读过的数据都被保留在一个搜索缓冲区里。编码时从前视缓冲区中取一个字符串到搜索缓冲区中去查找最长匹配。如果找到了就输出一个三元组(回溯距离, 匹配长度, 下一个字符)其中回溯距离表示从当前位置往前数多少个字节能找到匹配的起点匹配长度表示连续匹配了多少个字节下一个字符是匹配之后紧接着的那个无法匹配的字符。举个例子待编码串: abracadabra 当前位置: 在最后一个r之后窗口内已有 abraca这些细节我们在第三节用代码展示会更清楚。LZ77用一个已经看过的数据就是字典的假设免去了显式字典传输的开销因为解码器只需要维护同样的滑动窗口就能根据三元组自动重建字典。这种思路在信息论基础里被归为通用编码它不需要信源的任何先验知识。LZ77的代价也很明显匹配查找需要在前面的窗口里做字符串搜索窗口越大内存占用和搜索时间就越高。为了解决这个问题实际实现中会使用哈希表链或树结构来索引窗口中的字符串而不是朴素地从头扫到尾。2.2 LZ78与LZW的演进LZ77虽然优雅但它的距离值是没有显式字典的隐含引用而且窗口大小固定老数据会被永久挤出窗口。于是1978年Ziv和Lempel又提出了LZ78将字典显式化不再用窗口而是维护一张持续增长的字符串表。LZ78的编码过程是从左到右扫描每次尝试从前视缓冲区中读入一串已经在字典里的前缀下一个新字符把前缀的编号和新字符一起输出。具体地说维护一个字典初始时包含所有单字符项。编码时累积当前匹配前缀直到加入下一个字符后不再是字典中的条目这时输出(前缀编号, 新字符)并把前缀新字符作为新条目加入字典。解码器只需要同步构建同样的字典即可还原数据。1984年Terry Welch在此基础上提出了LZW做了关键简化初始字典包含所有可能的单字符编码时直接输出字典条目的编号不再输出下一个字符。因为解码器可以在前一个条目的基础上预测新条目的最后一个字符。LZW最大的应用就是GIF图像格式后来也用于TIFF、PDF和Unix的compress命令。LZ77和LZ78这两大流派本质上都在回答同一个问题如何把历史数据登记成可复用的索引。前者用相对位置距离和长度来表达匹配后者用全局字典编号来表达。这两者的不同直接导致了后续压缩工具选型的分叉先按住不表后面在工程对比里细说。3. 手写一个最小版LZW编码器从原理到实现3.1 编码表初始化与动态扩张为了让你真正理解字典编码我建议不要只看教材上的流程图而是自己动手写一个LZW编码器。LZW的核心是字典的动态扩张字典从单字符的完整集合出发每编码一个新串就增加一个条目因此字典会越涨越大直到达到预设上限。以8位字节流为例初始字典包含256个条目第0~255号分别对应字节值0x00~0xFF。从256号开始每新增一个前缀字符组合就分配一个新的编号。编码器维护两个变量当前前缀W和当前字符K。每次读入一个字符K判断WK是否在字典中。如果在就把W更新为WK继续读下一个字符。如果不在就输出W对应的字典编号然后把WK加入字典并令W K。这个逻辑看起来简单但有一个很微妙的点字典的条目是从无到有地创建的解码器必须能还原出完全相同的创建顺序。因此解码器的字典构建逻辑必须和编码器严格同步这也是LZW实现中容易出错的地方。3.2 Python实现与输出验证下面是一份极简的LZW编码器实现。我用Python写出编码逻辑不做位打包直接输出整数的列表方便观察中间结果。def lzw_encode(data: bytes) - list: # 初始字典所有单字节 dictionary {bytes([i]): i for i in range(256)} next_code 256 max_code 4096 # 12位码长的上限 w b result [] for b in data: k bytes([b]) wk w k if wk in dictionary and next_code max_code: w wk else: result.append(dictionary[w]) # 输出当前最长匹配的编号 if next_code max_code: dictionary[wk] next_code next_code 1 w k if w: result.append(dictionary[w]) return result # 测试 data bTOBEORNOTTOBEORTOBEORNOT codes lzw_encode(data) print(codes)等一下我在if wk in dictionary条件里加了一个next_code max_code这是为了防止字典撑爆。但条件的位置会影响行为当字典满时我们不再添加新条目但编码是否仍要输出w我们稍后在第5节专门讲字典满时的策略。这里先跑一个不设上限的版本看看基本行为。为了更直观地观察我把上面的max_code设得很大或去掉限制输出结果会是这样取决于你是否把单字符也提前输出初始字典包含全部单字节但首字符w为空所以直到w非空才输出。实际运行时你会发现TOBEORNOT这些字符每个单字符首次出现时都会输出其ASCII编号当第二个TO出现时就会输出一个大于255的编号这就是字典命中的效果。3.3 解码器的对称逻辑LZW解码器比编码器烧脑一点因为解码器看到的是一串整数需要反向推导出对应的字符串。它同样维护一个字典初始内容和编码器一致。每当读入一个编码code时解码器输出dictionary[code]然后根据前一个编码prev的输出内容构造一个新的条目dictionary[prev] first_char(current)也就是前一个串当前串的首字符。这个逻辑本质上是在复现编码器新增条目的过程。不过有一个著名的边界情况如果编码器输出的某个code恰好等于字典中还未构造出来的下一个新编号解码器会需要特殊处理即输出prev_str prev_str[0]。这个情况常在输入为连续重复字符时出现比如aaaaaa。下面给出对应解码代码def lzw_decode(codes: list) - bytes: dictionary {i: bytes([i]) for i in range(256)} next_code 256 max_code 4096 prev codes[0] out bytearray(dictionary[prev]) for code in codes[1:]: if code in dictionary: entry dictionary[code] elif code next_code: entry dictionary[prev] dictionary[prev][:1] else: raise ValueError(非法编码) out.extend(entry) if next_code max_code: dictionary[next_code] dictionary[prev] entry[:1] next_code 1 prev code return bytes(out)我个人强烈建议你在写完编码器后故意制造一个AAAAAA这样的重复串来测试。你会发现如果解码器不处理code next_code这个分支解码结果会和原文对不上这就是教科书里大名鼎鼎的KwKwKw问题。能亲手踩一遍这个坑对理解字典动态扩张是事半功倍的。4. 压缩率背后的参数博弈字典长度、窗口大小与位宽4.1 窗口大小对压缩率的影响如果是LZ77最关键的参数就是窗口大小搜索缓冲区和前视缓冲区的大小。它们的单位通常以字节计。窗口越大能找到的匹配越远但寻找匹配需要的时间也越长内存占用也越高。前视缓冲区越大单次匹配最长能覆盖的长度就越大但为了编码长度值也需要更多的位。这里有一个非常典型的信息论权衡距离和长度分别需要用多少bit来表示直接影响压缩率。假设你设定窗口为4KB那么距离值最多需要12bit前视缓冲区为256字节长度值需要8bit。那么一个三元组里距离占12bit长度占8bit未匹配字符占8bit合计至少28bit。如果实际只匹配了3个字节输出28bit比原始24bit还大。这就是为什么工程实现里如果找不到足够长的匹配LZ77会退化为字面量模式直接输出原始字符并设置标志位区分。我实测过一个场景对一份大量重复SQL日志做压缩窗口从1KB改成8KB压缩率能提升十几个百分点继续增加到64KB提升就非常有限了因为长重复模式基本被前32KB覆盖。这说明窗口大小并非越大越好还是要看数据的局部相关性半径。4.2 熵编码与字典编码的协同Ziv和Lempel的原始算法输出的是距离、长度等符号序列没有对这些符号做进一步的统计编码。而DeflateZIP/GZip的核心算法的做法是先用LZ77把数据转成匹配对字面量的中间流再用哈夫曼编码对中间流中的字面量、距离、长度分别进行二次压缩。为什么要做二次压缩因为虽然字典编码消除了重复字符串但输出的距离值、长度值、字面量各自出现的频率分布仍然是不均匀的。比如在一个C语言源文件里距离值等于跨过几个函数体的值可能集中在某个范围长度值里短匹配出现得远比长匹配频繁。对这类分布再用哈夫曼编码还能再压掉一些。这正好印证了信息论基础里的一个分层观点字典编码负责找结构熵编码负责挤概率。所以在学习字典编码时别只看它单段的输出。真正高效率的无损压缩工具几乎都是字典熵编码的联合体。理解这一层就能解释为什么你在评估一个压缩算法时不能只看字典算法本身的字长设计。5. 从教材到工程躲开那些教科书不会讲的坑5.1 字典溢出与清空策略LZW的字典如果无限增长序号位宽也要跟着无限增长。实际实现里会设定一个最大码长常见12bit编号到4095以后怎么办常见做法有三种第一冻结字典即不再新增条目后续完全依赖已有字典进行匹配编码继续输出已有编号。优点是实现简单缺点是在数据结构切换后压缩率可能明显下降。第二清空字典重新学习。很多变种会在字典满时清空所有非初始条目重新从单字符字典开始构建。优点是能适应局部特征变化很大的数据缺点是在字典刚清空的阶段压缩率很低因为大量单字符首次出现都要以原始值输出且重新积累需要时间。第三LRU式淘汰把好久没用过的条目删掉。这理论最优但实现复杂很少在主流压缩器里出现。我实际观察过GIF场景图像如果是局部渐变但整体颜色有限的图案冻结字典几乎不会造成明显劣化反而省去了清空后重新构建的停顿但如果是扫描文档这类前后内容差异极大的图清空策略能带来更好的压缩率。所以选清空还是冻结取决于数据的时间局部性。在LZ77体系里字典溢出表现为窗口直接滑过去老数据被挤出根本不需要清空操作。这算是滑动窗口天然自适应的优点——本质上它就是一个FIFO淘汰机制。5.2 匹配搜索的代价与优化LZ77最耗时的环节是在窗口中查找最长匹配。如果暴力地从窗口每个位置逐一比较前视缓冲区时间是窗口大小乘以前视缓冲区大小再乘上数据长度绝对不可用。工程上常见的加速手段是哈希链。具体做法是每遇到一个长度为3或4字节的子串就取它的哈希值在哈希表的槽位里记录一个链表的头结点。搜索匹配时只到哈希值相同的槽里的候选位置去找然后沿链表向前向后遍历若干项逐一比较真实内容找出最长匹配。这就是zlib中deflate算法的基本搜索结构。但哈希链有一个隐藏的弱点极端重复的数据会让某个哈希槽位的链表变得非常长拖慢匹配速度。因此实现时通常限制每个槽位最多追溯的候选个数比如zlib就通过max_chain_length参数控制。在使用层你不需要改代码只需要理解把压缩等级调高意味着搜索更深入压缩率略升但CPU时间成倍上涨。在服务器场景下我会直接把压缩等级从9降到6压缩率只损失约2%但速度能快一个数量级。5.3 工程应用选型参考如果你只需要在项目里选一个现成的压缩库这里给你一些基于字典编码特性的建议场景推荐方案理由通用文本/二进制文件打包Zlib/GZipDeflateLZ77哈夫曼均衡稳定生态完善图片无损压缩PNGzlib、GIFLZW图像局部重复多字典编码效果好数据库日志压缩LZ4、Zstandard以LZ77变体为核心速度优先流式协议实时压缩Zstandard或LZ4支持字典预置、增量重训练动态性强超高压缩率LZMA7z使用更大的字典窗口与更复杂的匹配模型这里格外提一下Zstandard。它在LZ77的基础上引入了一个可预置字典机制你可以预先从一个相似数据集中训练出一个小字典然后在压缩新数据时把这个字典作为初始搜索窗口。这个方案特别适合压缩大量长度很短的相似记录比如电信日志、API响应体。由于每条记录可能只有几百字节如果只用滑动窗口记录头部完全没有上下文但如果预置了一个包含常见字段名的字典开头部分的匹配率会大幅提升。这算是字典编码思想在现代工程里最具创造性的应用之一。我个人在压缩一堆JSON接口日志时用Zstandard的预置字典比直接用gzip -9体积少了将近三成而压缩速度反而快了一倍。这种收益不亲自动手试一下光看教材上的字典模型是很难体会到的。另一个容易被人忽略的坑是字典编码对加密数据毫无效果。加密后的数据伪随机性极强几乎找不到任何可用的重复模式。所以如果你想做先压后加密或先加密后压永远记得要先压后加密否则字典编码基本空转。最后再分享一个小技巧如果你正在写自己的LZW实现调试时不要一上来就压缩整个文件。先构造一些精心设计的短序列比如ABABABA、ABCABCABC、AAAAAAAAAA以及一份完全随机的长序列。前几个用来验证动态字典的建立和边界情况随机序列用来验证压缩是否退化为接近原始大小理论上随机数据不应该被压缩太多。能够同时通过这四类测试你的字典编码实现才算在行为上站得住脚。我自己当年做信息论课程实验时就是靠这几组测试数据揪出了解码器少处理一个边界分支的问题原地多花半小时后面跑全量测试时省下好几天。