有个同事把一份重复率很高的配置备份打包,发现 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,意思是「把上一个字节重复一百次」。解码端一边复制一边追加输出,后续复制能读到刚刚写出的字节,这叫重叠匹配,游程式的重复就靠它。编码端允许这种匹配,解码端必须按顺序写入,不能一次性切片拷贝。

LZ77 的距离通常用「往回退多少个字节」表示,长度表示复制多少个字节。真实格式会分别对距离和长度做变长编码或哈夫曼编码,因为短距离和小长度出现得更频繁。

真实实现还要处理几个工程问题。第一是搜索效率:上面用两层循环暴力比对,复杂度接近「窗口大小乘以数据长度」,数据一大就慢得不能用。实际实现会用哈希表把「三字节前缀」映射到候选位置,只检查少数候选,再用惰性匹配挑更好的那个。第二是距离和长度的取值范围,短距离可以用更少的位,长距离才用扩展码。第三是窗口边界,刚到文件开头时窗口里没有足够历史,不能越界读取。

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 找重复
字面量与匹配 token
哈夫曼分配码长
压缩流

DEFLATE 把数据切成块,每块可以有自己的哈夫曼表。块与块之间可以独立解码,但 LZ77 的窗口是跨块延续的,所以后面的块仍能引用前面块的内容。这个设计解释了为什么「压缩后不能随机跳到中间」:虽然块边界可以重同步,但窗口历史还需要重建,除非格式额外提供索引。

这也解释了 gzip 和 zip 的差异。zip 是容器,里面每个文件单独压缩,成员之间不共享窗口,所以可以单独解压某一个文件;gzip 通常压一整条流,窗口可以跨很远,压缩比略好,但想取中间一段就得从头解。PNG 则把 DEFLATE 用在图像的行滤波结果上,滤波把像素差值变小,LZ 和哈夫曼才有东西可抓。

DEFLATE 的块有三种类型:不压缩的存储块、固定哈夫曼表的块、以及把码表写在块头里的动态哈夫曼块。存储块给「压不动的数据」用,至少不会比原文件更糟;固定表适合小数据,省掉写码表的开销;动态表适合大数据,码表更贴合实际分布。压缩器会根据当前块的大小和分布自动挑一种,这个选择会直接影响最终体积。

窗口大小:为什么 32KB 会漏掉远处的重复

LZ77 的窗口决定了「能往回看多远」。gzip 的窗口是 32KB,意思是超过三万二千字节之前的重复,它看不见。对于日志、源码、普通文本,这个范围通常够用;对于大文件里首尾相同的大块结构、或者拼接了很多份模板的文档,远处的重复就浪费了。

zstd、7z、xz 提供了更大的窗口,从几兆到几百兆不等。窗口越大,压缩器要记住的历史越多,内存占用越高,匹配搜索也越慢。这不是「越大越好」的线性关系:窗口从 32KB 加到 8MB,可能多找到一些重复,但收益取决于数据里到底有没有那么远的重复。拿一份普通日志去试,可能只多省几个百分点,内存却翻了很多倍。

工具或格式典型窗口适合代价
gzip32KB网页文本、日志、通用分发远处重复看不见,流式解压
zstd可调,常见几 MB大文件、需要速度与压缩比平衡内存随窗口增长
xz / LZMA可调,可达几十 MB归档、安装包压缩慢,内存高
7z可调,支持多种算法冷数据归档格式复杂,解压依赖库

还有一层容易被忽略:窗口不是唯一影响压缩比的参数。匹配搜索的深度、是否尝试惰性匹配(先不急着输出,看看下一个位置有没有更长的匹配)、块的大小、哈夫曼表的重建频率,都会影响结果。两个都叫「gzip -9」的实现,如果内部策略不同,输出也可能不同。

窗口和块也不是一回事。窗口是「能往回看多远」,块是「压缩流在哪里切开」。两者都影响结果,但方向不同:窗口决定能不能找到远处的重复,块决定码表能不能贴合局部分布、错误会不会扩散到整段。调参数时把这两个概念分开,才看得懂为什么改了一个值,体积和速度的变化方向不一样。

边界与代价

LZ 系列最核心的边界是「有没有重复」。一份随机数据、已经压缩过的图片、加密后的字节,都几乎没有可利用的重复,LZ 只能原样抄,再加上格式开销,压缩比接近 1:1 甚至更差。判断方法很直接:先压一小段看看比值,不要凭文件类型猜。

第二个边界是内存与速度。窗口越大、搜索越深,压缩越慢、越吃内存。在线服务里压响应体,通常选低级别;归档冷数据,才值得用高级别慢慢压。解压端也有成本:LZ 解码本身很快,但大窗口意味着要保留更多历史数据,内存紧张的环境要算进去。

第三个边界是随机访问。LZ 的压缩流是前后依赖的,想读最后一段,理论上要把前面的窗口重建出来。视频、日志、数据库这类需要随机访问的数据,要么用分块压缩,要么额外建索引,要么换支持独立帧的格式。不能既想要高压缩比,又想要任意位置秒开,除非格式专门为此设计。

不要用「先压缩再加密」以外的顺序处理敏感数据。先加密再压缩,数据已经接近随机,压缩几乎无效;先压缩再加密,才可能既省空间又保密。顺序反了,带宽和 CPU 都白花。

最后一个代价是格式兼容。LZ77、LZ78、LZW、DEFLATE 是不同年代的产物,解码器不一定都支持。给别人发文件时,选对方一定能打开的格式,比多省几个百分点重要。自己设计格式时,也要考虑窗口和块大小,别让解码端为了解一个小文件分配几百兆内存。

还要记住 LZ 和熵编码的分工:LZ 把「重复的内容」换成「引用」,熵编码把「剩下的符号」换成更短的位。前者减少 token 数量,后者降低每个 token 的平均位数。只做其中一步,压缩比都会差一截;顺序反了,效果更差,因为熵编码之后再找重复,已经找不到原始结构了。

当天能自己验证的五个练习

  1. 把示例文本里的重复句改成只出现一次,重新跑 LZ77,记录 token 数和压缩比的变化。
  2. 把窗口从 64 改成 16,观察长句重复还能不能被匹配到,记录匹配数的下降。
  3. 用同一段文本分别跑 LZ77 玩具实现和 zlib,比较两者的字节数,解释差距来自哪里。
  4. 构造一个「开头一段、结尾完全复制开头」的大文本,分别用 gzip 和更大窗口的工具压缩,比较结果。
  5. 把一段随机字节交给 gzip,记录压缩后的字节数,确认它比原文件大,并解释多出来的部分是什么。

小结

三句话:LZ 系列靠「引用已经出现过的片段」省空间,重复越长越划算;LZ77 用滑动窗口的距离和长度,LZ78 与 LZW 用显式字典编号,DEFLATE 把 LZ77 和哈夫曼拼在一起;窗口大小决定能看多远,代价是内存、速度和随机访问能力。记住了这三点,再看任何压缩工具的「级别」参数,都不会只盯着数字猜。

下一篇进入有损压缩的核心:DCT 与心理声学。JPEG 的 8×8 块变换、MP3 的掩蔽模型,听起来是两个领域,其实都在做同一件事:把人不容易察觉的部分,用更粗的方式表示。