有个同事把一份重复率很高的配置备份打包,发现 gzip 只压到原来的三分之一,而他用另一个工具能压到五分之一。他以为是 gzip 不行,换了几次参数,结果只差几个百分点。真正的原因是那份文件里有大量跨很远的重复片段,而 gzip 的窗口只有 32KB,超出窗口的重复它根本看不见。
这类「找重复」的压缩方法,统称 LZ 系列,名字来自两位作者 Lempel 和 Ziv。它们不统计符号频率,而是回答另一个问题:这段内容之前是不是已经出现过?出现过的话,与其再写一遍,不如写「往回退多少、复制多长」。gzip、zip、PNG、GIF、7z 的压缩比,很大一部分来自这一步。
这篇讲三条主要分支:LZ77 用滑动窗口记录距离和长度,LZ78 和 LZW 用显式字典给片段编号,DEFLATE 把 LZ77 和哈夫曼拼成今天最常见的组合。下一篇讲 DCT 与心理声学,进入有损压缩的地盘。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 文本和日志压得很好,照片几乎压不动 | LZ 找的是重复片段,照片的像素噪声没有长重复 | 看数据里有没有连续重复的字节序列,或直接算压缩比 |
| 同一个算法压大文件比压小文件效果好 | 窗口和字典需要足够的数据才能积累出可复用的片段 | 看文件大小、窗口参数和块大小 |
| 把文件追加一段再压,前面的压缩结果也变了 | 新内容改变了后续匹配,压缩流是整体的,不是逐块独立 | 看格式是否支持独立块,是否每次都全量重压 |
| 压缩后不能直接跳到文件中段读取 | 后面的数据依赖前面解压出的历史窗口 | 查格式有没有关键帧式的重同步点或块索引 |
| 两个工具都叫 gzip,压缩比差不少 | 实现不同、块策略不同、匹配搜索深度不同 | 记录版本、级别和窗口参数,做同输入对比 |
| GIF 转成 PNG 体积变化很大 | GIF 受 256 色调色板限制,颜色量化那一步不在 LZW 里 | 看位深和调色板,不要只比较压缩算法 |
| 压缩速度慢到不可接受 | 暴力搜索每个位置的所有历史片段,复杂度接近平方 | 看实现有没有用哈希链、后缀数组或限制搜索深度 |
LZ 的基本动作:回头找一样的片段
想象你在抄一段文字。抄到某一句时,你发现它和前面第三段一模一样,于是写「见上文第三段,整段照抄」,而不是重新抄一遍。LZ 压缩做的就是这件事,只不过「上文」有范围限制,「照抄」要写成距离和长度两个数字。
这个动作有两个好处。第一,重复越长,收益越大:一段一百字节的重复,只需要一个距离加一个长度,可能只花两三个字节。第二,它不要求重复是「同一种字符反复出现」,任何长度的相同片段都能利用,包括整行日志、整个函数体、整块配置。
它也有一个硬限制:只能在已经出现过的内容里找。压缩器不能引用未来的数据,因为解码端还没解到那里。所以「重复在前还是在后」很关键,同一个模式第一次出现时只能原样写,第二次开始才省。
这也是为什么压缩器总在想办法「看更远」。一份大文件里,相同的模板可能相隔几十兆字节,如果窗口只有 32KB,第二次出现时早就滑出了视野,压缩器只能当新内容再写一遍。窗口大小因此成了 LZ 类算法最直接的调节旋钮之一。
LZ77:滑动窗口、距离和长度
LZ77 的做法是维护一个窗口,窗口里是刚刚处理过的数据。每读到一个新位置,就在窗口里找最长的匹配;找到足够长的匹配,就输出三元组「距离、长度」,然后跳过这段;找不到,就输出一个字面量,往前走一个字节。窗口随着处理不断向后滑,太老的数据被挤出去,不再参与匹配。
下面是一个可以运行的简化实现。为了看清结构,窗口设成 64 字节,最短匹配长度设成 3,输出用 Python 的元组表示,不追求真实格式的紧凑性。它包含编码和解码,解码后逐字节比对,确保可逆。
text = (
"the quick brown fox jumps over the lazy dog. "
"the quick brown fox jumps over the lazy dog. "
"the quick brown fox jumps over the lazy dog. "
"a slower white cat sleeps under the warm sun. "
"a slower white cat sleeps under the warm sun. "
)
data = text.encode()
def lz77(data, window=64):
i, out = 0, []
while i < len(data):
best_len, best_dist = 0, 0
for j in range(max(0, i - window), i):
length = 0
while (i + length < len(data)
and data[j + length] == data[i + length]
and length < 255):
length += 1
if length > best_len:
best_len, best_dist = length, i - j
if best_len >= 3:
out.append(("M", best_dist, best_len))
i += best_len
else:
out.append(("L", data[i]))
i += 1
return out
tokens = lz77(data)
def decode(tokens):
out = bytearray()
for t in tokens:
if t[0] == "L":
out.append(t[1])
else:
_, dist, length = t
for _ in range(length):
out.append(out[-dist])
return bytes(out)
assert decode(tokens) == data, "往返校验失败"
lits = sum(1 for t in tokens if t[0] == "L")
matches = len(tokens) - lits
orig_bits = len(data) * 8
toy_bits = lits * 9 + matches * 15
print(f"raw={len(data)} tokens={len(tokens)} literals={lits} matches={matches}")
print(f"toy={toy_bits} bits ({toy_bits/8:.1f} bytes) ratio={orig_bits/toy_bits:.2f}:1")
本机实际输出:
raw=227 tokens=76 literals=68 matches=8
toy=732 bits (91.5 bytes) ratio=2.48:1
二百二十七字节的文本,压缩后按玩具格式只占 91.5 字节。八次匹配各自覆盖了整句重复,剩下六十八个字面量是第一次出现的字符。这个数字不漂亮,因为玩具格式里一个字面量算九位、一个匹配算十五位,真实实现会用哈夫曼进一步压缩这些 token 的长度编码,还会用更聪明的匹配搜索。
注意解码时的那个细节:复制长度可以超过距离,比如距离 1、长度 100,意思是「把上一个字节重复一百次」。解码端一边复制一边追加输出,后续复制能读到刚刚写出的字节,这叫重叠匹配,游程式的重复就靠它。编码端允许这种匹配,解码端必须按顺序写入,不能一次性切片拷贝。
真实实现还要处理几个工程问题。第一是搜索效率:上面用两层循环暴力比对,复杂度接近「窗口大小乘以数据长度」,数据一大就慢得不能用。实际实现会用哈希表把「三字节前缀」映射到候选位置,只检查少数候选,再用惰性匹配挑更好的那个。第二是距离和长度的取值范围,短距离可以用更少的位,长距离才用扩展码。第三是窗口边界,刚到文件开头时窗口里没有足够历史,不能越界读取。
LZ78 与 LZW:把片段编成字典编号
LZ78 换了一种记账方式:不再输出「距离、长度」,而是维护一本字典,每遇到一个新片段就给它一个编号,输出时直接写编号。字典从空开始,读入字符,如果「当前前缀加下一个字符」已经在字典里,就继续延长;不在,就输出当前前缀的编号,把新片段加进字典,然后从下一个字符重新开始。
LZW 是 LZ78 的变体,最著名的作用是 GIF 和 TIFF 里的压缩。它预先把所有单字节填进字典,编号 0 到 255,然后从 256 开始分配新片段。编码时不断延长当前前缀,直到「前缀加下一个字符」不在字典里,输出前缀的编号,把新组合加进去。解码端可以一边读编号一边重建字典,不需要额外传输。
def lzw(data):
table = {bytes([i]): i for i in range(256)}
next_code, w, codes = 257, b"", []
for byte in data:
wb = w + bytes([byte])
if wb in table:
w = wb
else:
codes.append(table[w])
table[wb] = next_code
next_code += 1
w = bytes([byte])
if w:
codes.append(table[w])
return codes, table
codes, table = lzw(data)
bits = len(codes) * 9
print(f"codes={len(codes)} dict={len(table)}")
print(f"9bit={bits} bits ({bits/8:.1f} bytes) ratio={len(data)*8/bits:.2f}:1")
本机实际输出:
codes=136 dict=391
9bit=1224 bits (153.0 bytes) ratio=1.48:1
同一段文本,LZW 用固定九位编号只压到 1.48 倍,比 LZ77 的玩具结果差。原因不在算法笨,而在「固定九位」:字典里只有三百九十一个条目,却给每个编号都留了九位,编号 300 和编号 3 花一样多的空间。真实 LZW 会在字典变大时切换码长,从九位逐步加到十二位,GIF 就是这么做的。即便如此,LZW 对长距离重复的利用仍不如带大窗口的 LZ77。
LZW 曾经引发过一段著名的专利争议:GIF 用的 LZW 有专利,导致很多项目转向 PNG。专利早已过期,今天的重点不是法律,而是理解它的取舍:字典是显式的,解码端能同步重建;不需要传码表;但字典容量有限,满了要重置或停止增长,长文件后半段的收益会下降。
DEFLATE:LZ77 加哈夫曼,今天最常见的组合
gzip、zip、PNG 内部用的都是 DEFLATE。它不是一种新算法,而是把前面两条思路拼起来:先用 LZ77 找出重复,把数据变成「字面量、长度、距离」的混合流;再对这些符号做哈夫曼编码,给常见的长度和距离分配短码。LZ 负责减少符号数量,哈夫曼负责让剩下的符号表示得更短。
DEFLATE 把数据切成块,每块可以有自己的哈夫曼表。块与块之间可以独立解码,但 LZ77 的窗口是跨块延续的,所以后面的块仍能引用前面块的内容。这个设计解释了为什么「压缩后不能随机跳到中间」:虽然块边界可以重同步,但窗口历史还需要重建,除非格式额外提供索引。
这也解释了 gzip 和 zip 的差异。zip 是容器,里面每个文件单独压缩,成员之间不共享窗口,所以可以单独解压某一个文件;gzip 通常压一整条流,窗口可以跨很远,压缩比略好,但想取中间一段就得从头解。PNG 则把 DEFLATE 用在图像的行滤波结果上,滤波把像素差值变小,LZ 和哈夫曼才有东西可抓。
DEFLATE 的块有三种类型:不压缩的存储块、固定哈夫曼表的块、以及把码表写在块头里的动态哈夫曼块。存储块给「压不动的数据」用,至少不会比原文件更糟;固定表适合小数据,省掉写码表的开销;动态表适合大数据,码表更贴合实际分布。压缩器会根据当前块的大小和分布自动挑一种,这个选择会直接影响最终体积。
窗口大小:为什么 32KB 会漏掉远处的重复
LZ77 的窗口决定了「能往回看多远」。gzip 的窗口是 32KB,意思是超过三万二千字节之前的重复,它看不见。对于日志、源码、普通文本,这个范围通常够用;对于大文件里首尾相同的大块结构、或者拼接了很多份模板的文档,远处的重复就浪费了。
zstd、7z、xz 提供了更大的窗口,从几兆到几百兆不等。窗口越大,压缩器要记住的历史越多,内存占用越高,匹配搜索也越慢。这不是「越大越好」的线性关系:窗口从 32KB 加到 8MB,可能多找到一些重复,但收益取决于数据里到底有没有那么远的重复。拿一份普通日志去试,可能只多省几个百分点,内存却翻了很多倍。
| 工具或格式 | 典型窗口 | 适合 | 代价 |
|---|---|---|---|
| gzip | 32KB | 网页文本、日志、通用分发 | 远处重复看不见,流式解压 |
| zstd | 可调,常见几 MB | 大文件、需要速度与压缩比平衡 | 内存随窗口增长 |
| xz / LZMA | 可调,可达几十 MB | 归档、安装包 | 压缩慢,内存高 |
| 7z | 可调,支持多种算法 | 冷数据归档 | 格式复杂,解压依赖库 |
还有一层容易被忽略:窗口不是唯一影响压缩比的参数。匹配搜索的深度、是否尝试惰性匹配(先不急着输出,看看下一个位置有没有更长的匹配)、块的大小、哈夫曼表的重建频率,都会影响结果。两个都叫「gzip -9」的实现,如果内部策略不同,输出也可能不同。
窗口和块也不是一回事。窗口是「能往回看多远」,块是「压缩流在哪里切开」。两者都影响结果,但方向不同:窗口决定能不能找到远处的重复,块决定码表能不能贴合局部分布、错误会不会扩散到整段。调参数时把这两个概念分开,才看得懂为什么改了一个值,体积和速度的变化方向不一样。
边界与代价
LZ 系列最核心的边界是「有没有重复」。一份随机数据、已经压缩过的图片、加密后的字节,都几乎没有可利用的重复,LZ 只能原样抄,再加上格式开销,压缩比接近 1:1 甚至更差。判断方法很直接:先压一小段看看比值,不要凭文件类型猜。
第二个边界是内存与速度。窗口越大、搜索越深,压缩越慢、越吃内存。在线服务里压响应体,通常选低级别;归档冷数据,才值得用高级别慢慢压。解压端也有成本:LZ 解码本身很快,但大窗口意味着要保留更多历史数据,内存紧张的环境要算进去。
第三个边界是随机访问。LZ 的压缩流是前后依赖的,想读最后一段,理论上要把前面的窗口重建出来。视频、日志、数据库这类需要随机访问的数据,要么用分块压缩,要么额外建索引,要么换支持独立帧的格式。不能既想要高压缩比,又想要任意位置秒开,除非格式专门为此设计。
最后一个代价是格式兼容。LZ77、LZ78、LZW、DEFLATE 是不同年代的产物,解码器不一定都支持。给别人发文件时,选对方一定能打开的格式,比多省几个百分点重要。自己设计格式时,也要考虑窗口和块大小,别让解码端为了解一个小文件分配几百兆内存。
还要记住 LZ 和熵编码的分工:LZ 把「重复的内容」换成「引用」,熵编码把「剩下的符号」换成更短的位。前者减少 token 数量,后者降低每个 token 的平均位数。只做其中一步,压缩比都会差一截;顺序反了,效果更差,因为熵编码之后再找重复,已经找不到原始结构了。
当天能自己验证的五个练习
- 把示例文本里的重复句改成只出现一次,重新跑 LZ77,记录 token 数和压缩比的变化。
- 把窗口从 64 改成 16,观察长句重复还能不能被匹配到,记录匹配数的下降。
- 用同一段文本分别跑 LZ77 玩具实现和 zlib,比较两者的字节数,解释差距来自哪里。
- 构造一个「开头一段、结尾完全复制开头」的大文本,分别用 gzip 和更大窗口的工具压缩,比较结果。
- 把一段随机字节交给 gzip,记录压缩后的字节数,确认它比原文件大,并解释多出来的部分是什么。
小结
三句话:LZ 系列靠「引用已经出现过的片段」省空间,重复越长越划算;LZ77 用滑动窗口的距离和长度,LZ78 与 LZW 用显式字典编号,DEFLATE 把 LZ77 和哈夫曼拼在一起;窗口大小决定能看多远,代价是内存、速度和随机访问能力。记住了这三点,再看任何压缩工具的「级别」参数,都不会只盯着数字猜。
下一篇进入有损压缩的核心:DCT 与心理声学。JPEG 的 8×8 块变换、MP3 的掩蔽模型,听起来是两个领域,其实都在做同一件事:把人不容易察觉的部分,用更粗的方式表示。