前几年我帮朋友做一批历史对话日志的压缩归档日志是纯文本去掉空白字符之后单文件接近700MB。一开始我想的都是统计编码——字符频率这么集中霍夫曼压一遍应该差不多了吧。试下来确实能到55%左右但总觉得哪里不对劲因为真正占空间的其实是那些一遍又一遍重复出现的错误堆栈、日志模板、时间戳前缀。霍夫曼只看单个符号出现的概率完全看不到“序列”层面的重复。后来换用LZ系列编码的经典实现同样的数据一口气压到了约20%。从那次之后我养成了一个习惯评估任何压缩方案之前先问一句数据里到底有多少“重复结构”。LZ系列编码正是信息论通向工程压缩时最关键的桥梁之一。1. 从统计编码到字典压缩LZ系列在信息论坐标里的位置香农的信息论给了压缩一个理论下限一个信源的熵决定了无损压缩平均每符号至少需要多少比特。霍夫曼编码、算术编码这类统计编码都是在“已知或估计符号概率分布”的前提下向这个下限逼近。问题是现实中的数据往往不是按单符号独立出现的大量信息隐藏在连续片段的结构里。典型如一段C语言代码if (x 0)可能出现了几百次统计编码会把i、f、空格等符号的频率算得很好但它不知道“if (x 0)这个整体”才是真正值得压缩的单元。上个世纪70年代末Jacob Ziv和Abraham Lempel提出了完全不同的思路与其去猜符号概率不如直接在原始数据里找已经出现过的重复片段然后把“重复的位置和长度”记录下来。这就是LZ系列编码的起点。它最大的特点是通用性压缩器不需要事先知道任何概率模型纯粹靠数据自身的自相似性就能完成压缩。理论上甚至可以证明对于平稳遍历信源LZ算法的渐近压缩率会逼近熵率这让它和统计编码一样有着扎实的理论背书。LZ系列主要分两支LZ77和LZ78。LZ77后来衍生出DEFLATE、LZMA、LZ4、Zstandard这些随处可见的算法LZ78衍生出LZW曾经是GIF和TIFF的标配。不管是哪一支核心思想都可以浓缩成一句话用“历史引用”代替“重新描述”。就像写文章时不把同一段话抄两遍而是写“见上文第几段”解码端顺着引用把它恢复出来。维度统计编码霍夫曼/算术编码LZ77LZ78/LZW依赖模型符号概率分布无自适应无自适应找冗余的基本单位单符号任意长度的重复片段任意长度的重复短语一次扫描需要两遍或概率估计一遍一遍适合场景符号分布集中的数据文本、日志、结构化数据文本、图像索引流代表算法Huffman、Range CoderDEFLATE、LZMA、ZstdLZW、GIF信息论里经常讲“熵编码”和“字典编码”是两条路线。我在实际工程里明显感觉到统计编码解决的是“符号分布不平均”的问题而LZ系列解决的是“符号序列重复出现”的问题。大多数真实文件两种冗余都有所以才会有DEFLATE这种“先用LZ77扫掉序列重复再用霍夫曼处理符号频率”的组合拳。理解了这个坐标位置后面看LZ77、LZ78的细节就不容易迷路。2. LZ77核心机制拆解滑动窗口与三元组输出LZ77的思想非常直观当前要编码的位置之前已经编码过的历史数据就是一本“不断滚动的字典”。把最近一段历史放进一个滑动窗口然后在窗口里寻找与待编码区开头最长的匹配子串。一旦找到就输出一个三元组——(匹配起点相对当前位置的距离distance匹配长度length匹配后的下一个字符next)。手动走一遍例子最清楚。假设要压缩字符串abacababac压缩器的窗口大小设为8当前已经处理了前4个字符情况是这样步骤窗口已编码历史待编码区最长匹配输出1abacababac窗口开头的aba匹配长度3距离4(4, 3, b)2acababac窗口开头的ac匹配长度2距离6(6, 2, EOF)第一步里待编码区的a b a b a c和窗口里的a b a c对齐逐位比较能找到最长匹配aba长度3。注意窗口里第4个字符是c而待编码区第4个字符是b所以匹配在3处截止。这个匹配起点离当前待编码位置往回数4个字符所以distance就是4。输出三元组后再读入下一个字面量b解码端流程也很简单看到(4, 3, b)就从当前位置往前4个字符开始复制3个字符得到aba再补上b当前输出变成abacab正好和原始串对齐。这里有个很多初学者会忽略的细节LZ77允许匹配的length大于distance。什么意思呢比如字符串是abcabcabc窗口里刚编码完abcabc待编码区是abc看起来匹配长度是3。但如果继续处理更长的重复比如abababab一旦匹配串跨过了自身复制的起点解码端就必须逐字节复制而不是一次性memcpy一整块源数据。因为源块和目标块可能在内存里重叠。写解码器的时候我见过有人直接把源内存块整段拷贝结果输出变成一堆乱码就是因为没处理这种“自重叠复制”的情况。很多文档不会提这个但实际实现里很容易翻车。LZ77真正适合什么数据回想一下我压那份700MB日志的场景错误堆栈通常几百字节完全一致地重复出现距离可能隔着几十KB甚至几MB只要窗口够大都能找到匹配。它不太适合的是短字符串、随机性强的数据。随机数据里很难出现跨长度的重复片段LZ77不仅压不动还会因为输出三元组的开销反而把数据变大。所以做压缩选型时第一个问题永远是这份数据里有没有足够多、足够长的重复结构没有的话LZ77再经典也救不了你。3. LZ78到LZW动态字典的演进与解码器的隐蔽分支LZ77的滑动窗口有一个天然短板匹配只能发生在窗口范围内窗口一旦滑过去之前的短语就彻底忘了。LZ78换了个思路——不搞滑动窗口而是维护一个全局的、持续增长的短语字典。每遇到一个新的“前缀字符”组合就给这个组合分配一个新的索引号。编码器输出的是字典索引和下一个字符的组合比如(index, next_char)之后索引就能代表整段短语。1984年Terry Welch在LZ78基础上改出了LZW算法。LZW做了一件看起来很“激进”的事输出里不再带next_char而是只输出纯索引。字典初始化时已经包含了全部单字符所以编码器从头开始累积前缀每发现prefix current不在字典里就输出prefix的索引然后把prefix current登记为新索引接着把current当作新前缀继续。这样做的好处是输出流非常紧凑每个符号都对应一个定长码字。用一个具体例子说明。要压缩ABABABALZW编码过程如下步骤读入字符当前前缀前缀字符在字典中输出索引新增字典项1AA是初始化字典含A、B--2BAB否输出A的索引113AB3ABA否输出B的索引224BA4BAB是--5AABA否输出AB的索引335ABA6BAB是--7AABA是--8结束- --输出ABA的索引5-最终输出序列1 2 3 5。解码端拿到1 2 3 5正常情况下逐个查字典、边还原边建新索引过程是顺畅的。但有一个非常隐蔽的情况——当读到某个码字时它还没有出现在字典里。这就是编码过程中“字典刚登记完索引下一个码字紧接着就引用它”造成的。解码器怎么应对看上面这个例子的第6步到第8步AB之后读入A生成了新索引5ABA紧接着编码器就输出了5。这时候解码端读到码字5发现字典里还没有5但它知道上一个输出是AB于是特殊构造上一个输出 上一个输出的首字符也就是AB A ABA输出ABA之后再把5登记进字典。这个特殊分支在某些老教材里叫超前一码引用我第一次实现LZW的时候在这上面空转了很久还以为是字典初始化顺序写错了。这里放一段简化的LZW解码核心逻辑能很直观看清这个分支dictionary {i: chr(i) for i in range(256)} prev_code None for code in code_stream: if code in dictionary: entry dictionary[code] else: # 关键分支码字指向尚未定义的字典项 entry dictionary[prev_code] dictionary[prev_code][0] output(entry) if prev_code is not None: dictionary[len(dictionary)] dictionary[prev_code] entry[0] prev_code code工程上LZW还要面对两个很现实的问题。一是码字宽度。字典索引越来越多定长码位从9位涨到10位、11位、12位压缩器要约定什么时候扩位否则解不出来。二是字典写满之后怎么办。常见策略是“冻结”——不再新增索引只输出已有索引或者“清空”——重置字典重新积累。GIF图像里就专门设计了一个Clear Code标记配合处理动态变化的图像内容。我处理过一批老GIF文件它们压缩率一直上不去就是因为字典频繁清空这是动态字典模型在短周期变化数据上的本能缺陷不是算法写错了。4. DEFLATE教材LZ77最快落地的工程形态如果你打开一个.gz文件或一张.png图片看到的压缩数据绝大多数是DEFLATE格式。DEFLATE本质上是LZ77的工程化变体它的整体流程分成两层第一层用LZ77把重复片段转成长度-距离对第二层再把这一串符号做霍夫曼编码。这种“先字典编码再熵编码”的组合是工业界对LZ77最成功的改造之一。为什么实际实现没有直接套用教科书上的(distance, length, next_char)三元组因为在DEFLATE的框架里如果每次匹配都强制带上一个next_char符号流的种类会变得很杂不利于后续霍夫曼编码。DEFLATE的做法是把字面量literal、匹配长度length、匹配距离distance统一成一张大的符号表来处理字面量和长度共用同一个符号空间用256作为块结束标记距离单独走一张距离码表。这样输出流就是一个干净的自描述符号序列再交给霍夫曼编码时结构非常规整。DEFLATE的LZ77有几个关键参数都是教材不会细讲但工程实现绕不开的最小匹配长度是3字节。为什么不是2因为输出一个匹配对本身有成本需要占用长度码、距离码还可能在霍夫曼树上占位置。如果匹配太短省下的字节数不足以抵消编码开销反而越压越大。3是长期实践压出来的经验值。最大匹配长度是258字节。这个数看着奇怪其实和DEFLATE的长度符号设计有关。长度符号3-258被映射到257-285这29个符号上配合若干额外的扩展比特位最长正好258。超出这个长度的连续重复会被拆成多个匹配对输出。滑动窗口最大32768字节。这就是为什么PNG在压缩大图时远处重复的颜色块对压缩率帮助不大——它们已经滑出窗口了。DEFLATE还会对每个block选择不同的霍夫曼策略不压缩、固定霍夫曼树、动态霍夫曼树。动态树需要先把树的描述存到块头对于小数据块反而不划算。这也是为什么一个几字节的文件用gzip压完体积反而比原文大——它连动态树都要花空间存。很多人看到这个现象会怀疑压缩实现有问题其实不是这是格式设计的正常表现。实际使用DEFLATE最方便的方式还是走zlib。下面是两个最常见的用法一个命令行一个Python都能直接看到压缩效果gzip -k file.txtimport zlib data open(file.txt, rb).read() compressed zlib.compress(data, 6) # level6 是默认档位 print(len(data), len(compressed))我经常用zlib的level参数去试不同数据得到的结论是对于日志、代码这类重复度高的文本level从1调到9压缩率通常能提升几个百分点但耗时可能差出5到10倍。如果你的场景是海量日志实时落盘真没必要上最高档默认6在很多情况下已经是性价比最好的位置。5. 参数、内存与速度LZ工程优化必须想清楚的三笔账很多年前我做一个嵌入式设备的数据同步模块设备内存只有几十MB每次同步要压缩几百MB的文本数据。当时我天真地以为LZ77就是背一个窗口在那找匹配参数随便调调就行。真做起来才发现工程优化根本不是“压缩率越高越好”而是压缩率、速度、内存三笔账一起算。这一节的参数取舍全部来自我和团队在这些账目上的真实记录。窗口大小是第一笔账。LZ77的核心搜索空间就是窗口。窗口开得越大能发现的重复距离就越远压缩率自然上限更高。但代价有两块内存占用线性增长哈希链搜索也变慢。DEFLATE把窗口定死在32KB就是考虑过当时内存和CPU的平衡点。后来的LZMA允许把窗口开到几MB甚至几十MB压缩率大幅提升代价是压缩端内存和耗时都上去了。我在日志归档场景里测过当重复片段距离分布在几百KB时窗口32KB完全不够看换LZMA的4MB窗口能多压20%左右但如果是几KB的小文件大窗口只是白占内存。选窗口大小的判断标准应该是先统计一下数据里重复片段平均距离大概在什么量级。哈希链是第二笔账。纯粹的LZ77字符串匹配要到窗口里做最长前缀搜索靠朴素比较根本扛不住。工程实现几乎都用哈希表加速把每3字节算出一个哈希值相同哈希的位置串成一条链搜索时只需要在这条链上比较候选位置。链越长找到更远更好匹配的机会越大但比较次数也跟着涨。zlib的level参数本质上就是在控制这个hash chain的长度上限。level 1时链很短快速扫过level 9时链很长压缩率拉满速度掉得厉害。压缩等级并不是线性地“越高越慢”它是压缩率曲线的渐近区堆再多的链收益也非常有限。还有一个工程细节叫lazy matching很多新手根本没听过但它在DEFLATE里影响很大。普通贪婪匹配是当前位置找到最长匹配就直接输出lazy matching会多看一个位置比较一下“当前匹配”和“下一个位置能找到的匹配”哪个更长如果下一个更长就先输出当前字符把置位让给下一轮。代价是额外多做一次匹配搜索换来的是更接近全局最优的分割。zlib在较高level下默认开启这个机制这也是为什么同样数据在不同level下输出结果差异明显。内存占用是第三笔账。LZ77压缩器除了窗口还要保存哈希表、匹配链、待处理缓冲区。zlib里有个memLevel参数控制哈希表的大小。哈希表小了哈希碰撞增多搜索质量下降哈希表大了内存占用上升。嵌入式环境下内存吃紧我一般会把memLevel调到8以下配合小窗口牺牲一点压缩率换稳定运行。经验值是这样的文本日志、JSON这类高度结构化的数据中等参数就有很好效果二进制固件、代码段重复距离往往很近窗口不用太大已经压缩过的数据比如JPEG里再套一层压缩就完全没必要上LZ只会白白增加延迟。场景推荐窗口推荐level备注实时网络日志压缩32KB-64KB1-3速度优先低延迟离线归档4MB以上9压缩率优先接受慢嵌入式设备16KB-32KB6以下内存受限平衡为主PNG图片内部32KB固定6左右格式固定无法改窗口这套参数组合我一直在用效果比较稳定。真正的优化顺序应该是先确定数据特征再确定环境限制最后才谈算法级别。参数只是实现这些策略的工具不是数字越大越好。6. LZ的测不准地带局限、改良与它留给后人的问题LZ系列再能打也不是万能的。最典型的一类失败案例对随机数、加密数据、已经压缩过的数据做LZ压缩。随机数据没有重复结构加密数据把重复模式彻底打散已经压过的数据几乎接近熵极限LZ在这些数据上要么压缩率趋近于1要么因为输出索引开销反而变大。我见过有系统对每个HTTP响应不分青红皂白都做一层gzip结果响应体本身已经是Brotli压过的再压一遍体积基本不变CPU白烧。合理的做法是在压缩链路上加一步快速判断——采样前几KB算一个经验熵如果看起来太“高熵”直接跳过压缩或改用纯存储模式。理论家们关心的是LZ的渐近最优性Ziv和Lempel在1978年的论文里证明了在一定条件下LZ78对平稳遍历信源可以达到熵率。这个结论给了无数工程实现底气我们不是在用一个没有理论支撑的野路子而是在用数学上渐进最优的通用方案。不过“渐近”两个字意味着要处理非常长的数据流才能逼近理论值这也解释了为什么小文件用LZ经常占不到便宜。后来者站在LZ的肩膀上做了大量改良。LZMA延续了LZ77的匹配思想但匹配之后不再用定长表示距离和长度而是用区间编码加上位字段压缩复杂度和压缩率双双提升。Brotli在LZ77外面套了上下文建模对网页文本尤其有效。Zstandard则专门优化了解码速度和参数灵活性成为新一代日志压缩和网络传输的热门选择。甚至LZ4这类只追求极致速度的算法也还是LZ77的变体——它宁愿牺牲压缩率也要让解压跑到几GB每秒。信息论这门学科给人的第一印象通常是数学推导和概率公式但我做了多年工程之后回头看LZ系列才是那个把理论真正“焊”进现实的关键一环。它没有要求你知道信源的熵是多少也不要求你预先建立一个精确的模型它只是相信一点真实世界产生的数据一定带着大量重复和规律只要把这些规律找出来压缩就自然发生了。而工程上的乐趣恰好在于弄明白什么样的数据在什么样的参数下重复得最明显。我自己现在判断一个压缩需求永远先问三件事数据里重复结构多不多、压缩耗时预算有多少、解码端内存压力大不大。LZ系列在这三件事之间留出的调优空间才是它真正让人着迷的地方。