第 13 章

LZ77 与 ZIP——1977年，两位科学家决定让计算机不再重复保存同一句话

正在加载交互实验…

第一季 · 人类如何驯服数据

历史主线：1948—1996年 · 信息论、通用压缩、LZ77、LZ78、LZW、DEFLATE 与 ZIP1977年5月。IEEE 的《信息论汇刊》发表了一篇只有七页的论文。论文题目非常朴素：A Universal Algorithm for Sequential Data Compression《一种用于序列数据压缩的通用算法》。作者是两位以色列研究者：Jacob Ziv 与 Abraham Lempel。他们提出了一种很不寻常的想法。如果要传输：ABRACADABRA ABRACADABRA我们为什么必须把 ABRACADABRA 再发送一遍？既然接收方已经见过这段文字，为什么不能告诉它：“把前面出现过的那11个字符，再复制一次。”这听起来不过是一个小技巧。然而，正是这种思想，后来发展成 ZIP、gzip、PNG 等格式所采用的压缩技术的重要基础。更重要的是，这两位研究者希望解决的，并不只是重复单词的问题。他们试图回答一个信息论领域的根本问题：如果事先完全不知道数据中哪些字符常见、哪些模式会重复，是否仍然能够设计一种通用的压缩方法？这是比“把重复文字替换成指针”更加深刻的问题。

第一幕：香农留给下一代研究者的一道难题

上一章，我们认识了1948年的 Claude Shannon。香农证明，数据源的概率结构决定了信息熵，也给出了无损压缩的重要理论极限。1952年，David Huffman 发明了最优二元前缀码的经典构造方法。但这里存在一个容易被忽略的前提。Huffman 编码需要知道——或者至少估计——各个符号的频率。假设有一份英文文档。字母 E 非常频繁。字母 Z 比较罕见。你可以给 E 较短的编码，给 Z 较长的编码。但如果接下来的文件变成一份计算机生成的日志：

ERROR ERROR ERROR ERROR

或者一段 DNA 序列：

ACGTACGTACGTACGT

又或者一个充满重复字段的数据库导出文件，原先根据普通英文频率构造的编码不一定合适。

一个关键区别：字符频率与字符串重复

考虑两个字符串：AAAABBBB以及：ABABABAB它们都有四个 A 和四个 B。如果只按照单字符频率构造 Huffman 编码，两者的统计信息完全一样。但它们具有不同的结构。第一个字符串包含连续的相同字符。第二个字符串包含反复出现的 AB 模式。

同样的字符频率，不同的重复结构

AAAABBBB

ABABABAB

单字符频率相同，但连续模式、相邻关系和可重复利用的片段不同。

于是，一个新方向出现了。除了统计每个字符出现多少次，我们能否直接寻找文本中的重复片段？这样，算法不必提前知道文件来自英语、中文、代码还是数据库。它可以在读取数据的过程中，自己发现重复规律。这就是 Ziv 和 Lempel 研究的重要背景。

第二幕：两位研究者，为何恰好能够合作？

Jacob Ziv（1931—2023）以色列电气工程师和信息论研究者，长期研究数据压缩、通信理论与纠错编码。1970年，他加入以色列理工学院（Technion）任教，后来担任电气工程学院院长等职务。

Abraham Lempel（1936—2023）以色列计算机科学家，研究信息处理、布尔代数与数据压缩。他与 Ziv 合作提出的压缩方法，后来成为现代无损压缩技术的重要基础。

他们的合作并不是两个人碰巧在同一张纸上写下名字。Ziv 对信息论、统计通信与压缩极限有深入理解。Lempel 则更擅长计算机科学、离散结构与编码机制。在 IEEE 后来的一次采访中，Ziv 回忆，两人的专业优势恰好能够互补。他还指出，自己与 Lempel 合作时，他们并不只是想写一个比当时压缩程序快一点的工具。他们希望找到一种不必事先获知数据统计规律的普适方法。^{[IEEE Spectrum][IEEE Spectrum]}

什么叫“通用”压缩？

我们需要仔细理解这个词。它不是说：“任意输入都能被压得更小。”这是不可能的。如果所有长度为

n

的二进制串都能被映射成更短且互不冲突的编码，编码数量根本不够。所谓 Universal Compression，重点是：在一定的数据源模型和渐近条件下，即使编码器事先不知道具体源的统计特征，也可以随着输入增长，逐渐达到相应类别中接近最优的压缩表现。1977年的论文严谨讨论了受约束信息源上的这种性质。它不只是一篇描述压缩技巧的工程笔记，而是一篇有明确信息论目标与证明的研究论文。^{[IEEE Xplore][Israel Institute of Technology]}这正是 Lempel–Ziv 算法伟大的地方。它把压缩从“先估计概率，再分配编码”，拓展到“直接从数据序列中发现并利用重复结构”。

第三幕：1977年，LZ77 的核心发明——让历史数据成为字典

现在，让我们回到1977年的原始论文。Ziv 和 Lempel 的算法有一个非常巧妙的设计。它不需要把所有出现过的字符串都永久保存下来。而是使用一个有限长度的缓冲区，只保留最近的一部分数据。可以把这个缓冲区想象成一扇沿着文本不断前进的窗口。窗口左边，是已经处理过的历史。窗口右边，是接下来需要编码的内容。这就是**滑动窗口（Sliding Window）**思想。

假设要压缩这段文字

ABCABCABCX如果按普通字符逐一保存，一共有10个字符。我们从左向右读取。开始时，编码器还没见过任何内容。所以 A、B、C 必须作为普通字符写入。这时：

处理前三个字符之后

已经处理过的历史区

接下来，我们来到位置3。准备处理的字符又是：ABCABC而我们已经知道：位置0、1、2保存着 ABC。于是能否简单地写：“距离当前位置向前3个字符，复制6个字符。”也就是：

(\text{distance}=3,\text{length}=6)

乍一看有个问题。前面只有三个字符 ABC，怎么能够复制六个字符？这是 LZ77 中非常精彩的一个细节。

复制时，可以引用刚刚复制出来的内容

如果解码器逐字符复制：第一步，往前3格，复制 A。第二步，往前3格，复制 B。第三步，往前3格，复制 C。这时输出已经变成：ABCABC第四步，再往前3格，恰好又是刚刚产生的 A。第五步，复制 B。第六步，复制 C。最终得到：ABCABCABC复制源与输出目标可以重叠。这种重叠复制能力，让 LZ 系列算法可以高效表达周期性重复结构。不过，具体文件格式如何表达这种复制，以及是否允许重叠、一次复制多长，都由各自的编码规范规定。

交互实验：让指针替代重复文本

LZ77 滑动窗口实验室

教学版字面符号与回溯引用

0/5 个编码单元

原始文本

解码器已经重建的内容

尚无输出

编码流

等待编码……

准备从左向右处理文本。

在这个简化实验中，原始10个字符被表示成：'A'、'B'、'C'、(3,6)、'X'这里的 (3,6) 表示距离与长度。请注意，它还不是真正的压缩字节流。因为每个距离、长度、字面字符以及标识类型的控制位，都需要实际占用二进制空间。对于这么短的一段输入，编码开销可能抵消全部节省。真正的压缩器需要精心设计这些数字的比特表示。而1977年原始论文采用的是带窗口约束、指针、匹配长度和后继符号的特定编码规则，并不与上述教学记号完全相同。^{[pzs.dstu.dp.ua]}这就是学习历史算法时应该保留的区分：教学演示帮助理解核心机制；原始论文规定的具体编码方案，则要以原文为准。

第四幕：一条指令，为什么就能恢复六个字符？

这里有一个容易产生疑惑的地方。压缩时，我们发现了 ABCABC 是一段重复内容。但解压缩时，计算机并没有看到原始文件。它怎么知道 (3,6) 究竟对应哪几个字符？答案是：编码器与解码器按同样的顺序构造历史缓冲区。当解码器读取：'A'、'B'、'C'它已经重建了：ABC随后读到 (3,6)。它不需要查询外部词典。只需要在当前输出位置向前3个字符，逐字节复制6次。因此，解压缩过程可以非常直接。

def decompress(tokens):
    output = bytearray()

    for token in tokens:
        if token[0] == "lit":
            output.append(token[1])

        elif token[0] == "copy":
            distance, length = token[1], token[2]

            if distance <= 0 or distance > len(output):
                raise ValueError("Invalid back-reference")

            for _ in range(length):
                output.append(output[-distance])

    return bytes(output)


tokens = [
    ("lit", ord("A")),
    ("lit", ord("B")),
    ("lit", ord("C")),
    ("copy", 3, 6),
    ("lit", ord("X")),
]

print(decompress(tokens).decode("ascii"))
# ABCABCABCX

最关键的一行是：

output.append(output[-distance])

为什么在循环中始终读取 output[-distance]，却能得到不同字符？因为 output 在不断增长。距离保持为3，但读取位置也随着输出增长向右移动。这就天然支持了重叠复制。

一项非常重要的工程限制

实际解压缩程序必须验证数据。不能无条件相信压缩流中写入的距离和长度。例如：

引用距离不能超过已经存在的历史数据。
解压缩输出不能无上限增长。
文件长度与校验信息需要验证。
无法解析的编码或非法块必须拒绝。

否则，损坏或恶意构造的压缩数据可能造成内存耗尽、异常运行或其他安全问题。这就是为什么 ZIP 解压缩程序除了实现算法，还需要大量边界检查。

第五幕：1978年，两位研究者改变方向——让字典自己生长

1977年的方案依赖滑动窗口。只保留最近的数据。而1978年9月，Ziv 和 Lempel 又在 IEEE 发表一篇论文：Compression of Individual Sequences via Variable-Rate Coding《通过变码率编码压缩单独序列》。这就是 LZ78 的理论来源。^{[dblp][Philippe Fournier-Viger]}这一次，他们不再主要依靠固定窗口内的距离引用。而是让编码器逐步构建一部字典。

一部不断生长的短语词典

假设输入：ABABABA我们从空字典开始。规则是：找到词典中最长的已知前缀，然后添加一个新字符，组成一个新短语。输出“已有前缀编号 + 新字符”。例如：第一步：读取 A。词典没有 A。输出：(0, A)加入：1 → A第二步：读取 B。输出：(0, B)加入：2 → B第三步：接下来是 AB。词典中已经有 A。但还没有 AB。输出：(1, B)加入：3 → AB第四步：接下来是 ABA。词典中已经有 AB。但还没有 ABA。输出：(3, A)加入：4 → ABA我们就把：A | B | AB | ABA分成了四个短语。

LZ78 字典逐步生成

LZ78 自动字典

0/4

输入序列

编号

词典短语

输出编码

字典为空，编号0代表空前缀。

和 LZ77 相比，LZ78 体现了另一种设计哲学。LZ77：在最近的历史窗口中寻找相同片段。LZ78：不断扩充由输入短语构成的字典，用编号表示已经认识的短语。这两种方法都是无损压缩，而且都可以在数据到达时逐渐建立结构。但它们在内存使用、查找效率、编码方式和适用场景上具有不同的工程取舍。也要注意：字典不可能无限扩张而完全没有成本。实际系统通常需要限制字典大小，或者设计重置机制。

第六幕：1984年，Terry Welch 让字典压缩变得更实用

时间来到1984年。一位在 Sperry Research Center 从事研究的工程师 Terry A. Welch，在 IEEE Computer 发表论文：A Technique for High-Performance Data Compression《一种高性能数据压缩技术》。这篇论文提出了后来著名的 LZW 算法。^{[威斯康星大学计算机科学页面]}LZW 的名字来自：Lempel–Ziv–Welch。它是在 LZ78 思路基础上的重要改进。

LZW 改变了什么？

在经典 LZ78 中，编码结果包含：已有短语编号 + 新字符而 LZW 先把所有单个字符放入初始字典。之后，输出主要是字典编号，不需要在每个编码单元中额外携带那个新字符。编码器和解码器依据相同规则同步扩展字典。Welch 的论文特别关注：如何让压缩自动发生，而不要求应用程序员了解数据内容。如何让压缩系统具有足够的运行速度。如何处理磁盘、磁带和通信链路中的重复数据。这与早期压缩研究追求纯数学最优，形成了有趣的对照。1984年的挑战，已经不只是能不能压缩，而是压缩是否足够快、足够透明，能否真正部署到商业计算系统中。LZW 后来进入了 GIF 图像格式，也曾被 TIFF 等格式采用。不过，历史还出现了一个颇具争议的话题。LZW 相关专利在一段时期内影响了软件实现、授权和格式选择。GIF 与早期软件生态因此经历过专利争议。这也是后来 PNG 采用另一套无损压缩机制的重要历史背景之一。这里要区分算法的研究发表与相关实现专利：不能因为 LZ78 在1978年公开发表，就直接推断所有后续改进在当时都不受专利约束。

第七幕：1989年前后，为什么 ZIP 没有直接使用 LZW？

故事进入个人计算机时代。1980年代后期，PC 用户已经开始大量交换软件、文档和文件。但当时磁盘容量有限，调制解调器传输速度也远不如今天。压缩的价值非常现实。节省几百 KB，就可能意味着少用一张软盘。缩短几分钟传输时间，就可能省下不少通信成本。

Phil Katz 与 PKZIP

1989年，Phil Katz 发布 PKZIP 的重要早期版本。ZIP 格式后来成为 PC 世界影响极大的压缩归档格式之一。但必须澄清：ZIP 不是某一种具体的压缩算法。ZIP 是一种文件归档格式。它可以在一个容器中保存多个文件以及目录、元数据等信息。每个文件可以使用某种压缩方法，也可以不压缩。因此 ZIP 与 LZW、LZ77、DEFLATE 并不是同一个层面的概念。后来，ZIP 广泛采用的一种重要压缩方法是：DEFLATE。DEFLATE 将两个不同的压缩思想结合起来：

DEFLATE 的核心处理链

原始字节数据

LZ77 风格匹配把重复片段转换为长度、距离引用

Huffman 编码对字面符号、长度符号和距离符号进行熵编码

压缩比特流

这正是第十二章与第十三章的直接连接。LZ77 负责发现重复结构。Huffman 负责把输出符号进一步编码成紧凑的比特序列。它们不是相互竞争，而是互相补充。

1996年，DEFLATE 终于有了一份广为引用的公开规范

1996年5月，RFC 1951 正式发布：DEFLATE Compressed Data Format Specification version 1.3作者是 L. Peter Deutsch。该规范详细描述了 DEFLATE 的编码格式，其中包括长度/距离引用、固定或动态 Huffman 编码，以及未压缩块等机制。RFC 的致谢部分明确记载：Phil Katz 设计了 DEFLATE 格式，Jean-Loup Gailly 和 Mark Adler 编写了相关软件。 ^{[RFC Editor]}阅读 RFC 1951：DEFLATE 压缩格式规范这里还有三个经常被混淆的概念。

名称	主要角色
DEFLATE	压缩数据的编码方法
gzip	通常使用 DEFLATE 的单文件压缩封装格式
ZIP	支持多个文件与多种压缩方法的归档容器

这也是为什么 .gz 与 .zip 虽然都可能使用 DEFLATE，却并不是同一种文件格式。

第八幕：为什么压缩一个文件，有时反而变大了？

现在，我们已经理解两个重要的压缩机制。但我们还没有讨论一个最容易被误解的事实。压缩算法并不能保证所有输入都变短。例如：

AAAAAAAAAAAAAAAA

具有非常明显的重复结构。LZ77 很容易找到长距离的重复片段。但如果输入是：

Q7m@2Z!p9&xL4...

而且这些字节近似独立、均匀、不可预测，压缩器就很难找到有用的重复。甚至需要添加文件头、块结构和校验数据，反而让结果变大。

为什么这是数学上不可避免的？

假设我们考虑所有长度为8 bit的二进制串。一共有：

2^8=256

种不同输入。如果希望把每个8 bit输入都压缩到最多7 bit，那么可以使用的短编码总数只有：

2^0+2^1+\cdots+2^7=255

连256种输入都无法一一对应。因此，不可能给所有8 bit输入分配不同的更短编码，同时还允许无损恢复。这只是最简单的计数证明，但足以说明：无损压缩一定依赖可利用的冗余，不可能对任意数据都保证节省空间。

压缩率实验：不同数据结构对压缩的影响

下面是三个概念性例子。

大量重复字节如连续的 A

常常具有较高压缩潜力，特别适合引用重复片段或游程编码。

重复词语或字段如日志、JSON

通常可以利用键名、固定短语与重复结构获得压缩收益。

已压缩或高熵数据如许多 JPEG、随机字节

通常难以再次显著压缩，有时会因封装开销而增大。

色条仅表达定性压缩潜力，不是测量得到的压缩比。

所以，当你在工程实践中面对 ZIP、gzip、zstd、LZ4 等方法时，不能只问“谁压缩得最好”。还应关心：压缩速度。解压速度。内存占用。数据类型。重复窗口大小。文件大小。以及是否需要随机访问和流式处理。这就是为什么现代系统仍然存在许多不同的压缩算法。

第九幕：我们自己写一个简单的 LZ77 压缩器

现在，进入本章最重要的编程实践。我们不需要实现完整的 ZIP。因为 ZIP 还包括归档结构、块编码、Huffman 编码、文件元数据等大量细节。先实现一种容易理解的 LZ77 风格标记流。允许两种标记：字面符号：

("lit", 65)

表示一个字节 A。以及历史引用：

("copy", 3, 6)

表示往前3字节复制6字节。我们仍然使用上一节的解压函数。

压缩器的主要逻辑

在当前位置 i：检查最近 window_size 字节内的每个候选起点。寻找与当前位置开始的数据相同的最长片段。如果匹配足够长，就输出距离/长度引用。否则，输出当前字面字节。

def compress_lz77(data, window_size=32, min_match=3):
    tokens = []
    i = 0

    while i < len(data):
        best_length = 0
        best_distance = 0

        start = max(0, i - window_size)

        for j in range(start, i):
            length = 0

            while (
                i + length < len(data)
                and data[j + length] == data[i + length]
            ):
                length += 1

            if length > best_length:
                best_length = length
                best_distance = i - j

        if best_length >= min_match:
            tokens.append((
                "copy",
                best_distance,
                best_length
            ))
            i += best_length

        else:
            tokens.append(("lit", data[i]))
            i += 1

    return tokens

这个教学实现故意采用暴力搜索匹配位置，因此算法效率不是工业级的。而且它没有处理真实压缩格式中的最大匹配长度、位级编码、哈希链索引、懒惰匹配等优化。但是，它可以让我们完整理解 LZ77 的核心流程。配合前面的 decompress()，试一试：

data = b"ABCABCABCX"

tokens = compress_lz77(data)

print(tokens)

restored = decompress(tokens)

print(restored == data)
# True

输出的标记可以是：

[
    ("lit", 65),
    ("lit", 66),
    ("lit", 67),
    ("copy", 3, 6),
    ("lit", 88)
]

注意，这段代码比较匹配内容时直接读取完整输入，因此可以找到允许重叠复制的候选片段。真正的流式压缩器则必须根据有限窗口和前瞻缓冲区设计访问方式。

再来一个实验：为什么重叠复制很特别？

输入：AAAAAAAAAA如果已经输出了一个 A，剩下九个 A 都可以由距离1的历史引用重建：'A'、(1,9)这说明 LZ77 不只是寻找完整重复的旧片段。它甚至能够让一个已经输出的短模式，沿着新生成的数据不断延伸。这对周期性文本非常有利。

第十幕：Ziv 和 Lempel 的发明，后来如何影响整个软件世界？

1977年，两位研究者发表 LZ77。1978年，他们提出 LZ78。1984年，Welch 推动了 LZW 的实际应用。1989年前后，PKZIP 推广了 PC 端压缩归档的使用。1990年代，DEFLATE、gzip、zlib 和 PNG 等技术将 LZ 风格的重复匹配，与 Huffman 编码进一步组合和推广。今天，当你执行：

gzip access.log

或者：

import zlib

data = b"ABCABCABCX" * 1000

compressed = zlib.compress(data)

restored = zlib.decompress(compressed)

assert restored == data

背后就有这些历史思想的直接传承。当然，zlib.compress() 输出的不是我们教学中的字面字符与 (distance,length) 文本标记，而是遵循 zlib 封装与 DEFLATE 编码规则的二进制数据。

一次非常有意思的历史访谈

多年之后，Ziv 在接受 IEEE 采访时回忆，当他们研究 LZ78 时，已经意识到它很有商业价值，并尝试考虑专利保护。不过，软件专利在当时的法律和商业环境中还面临诸多不确定性。Bell Labs 对纯软件方案的申请兴趣有限。而 Lempel 所在的 Sperry 则更愿意尝试通过硬件实现与相关专利路径推动商业化。这也与后来 LZW 的发展相联系。^{[IEEE Spectrum]}这段真实经历提醒我们：算法的发明、公开发表、专利保护与商业推广，是四件互相关联却并不相同的事情。一个算法可以先在论文中出现，再经过多年工程优化，才真正成为大众软件中的基础技术。

尾声：两个人，让计算机学会了“引用过去”

1977年，Jacob Ziv 和 Abraham Lempel 并没有像今天的软件开发者一样，直接打开一个现成的压缩库。他们从信息论的深层问题出发：既然现实数据具有统计规律和重复结构，能不能让编码器自己发现这些规律，而不必事先知道数据属于什么类型？他们提出的答案，是让过去出现过的内容成为未来编码的依据。LZ77 通过历史窗口复用片段。LZ78 通过逐渐增长的字典复用短语。LZW 进一步简化字典编码。DEFLATE 则把重复匹配与 Huffman 编码结合起来。至此，我们把第十二章和第十三章真正连接起来了。香农告诉我们压缩的理论基础。Huffman 让高频符号使用更短的编码。Ziv 和 Lempel 则让重复的整段内容可以由简短的引用代替。你会发现，计算机科学中很多最重要的进步，都来自同一种思想：不要重复保存已经知道的信息，也不要重复计算已经得到的结果。这与我们学习过的动态规划、KMP、哈希表，甚至缓存系统，都具有深刻的联系。

第十三章知识总结

技术	年份	核心思想
LZ77	1977	在历史窗口中寻找重复片段
LZ78	1978	动态建立短语字典
LZW	1984	使用不断增长的字典编号编码
ZIP / PKZIP	1989起	压缩归档容器及工具
DEFLATE	1990年代广泛应用	LZ77 风格匹配 + Huffman 编码
gzip / zlib	1990年代	基于 DEFLATE 的格式与实现

本章原始资料

IEEE 信息论学会：Ziv 与 Lempel 1977年论文档案 LZ77 原始论文 PDF：《A Universal Algorithm for Sequential Data Compression》LZ78 原始论文 PDF：《Compression of Individual Sequences via Variable-Rate Coding》Welch 1984年 LZW 论文 PDF IEEE Spectrum：Jacob Ziv 的研究生涯与两人合作经历 RFC 1951：DEFLATE 压缩格式完整规范

下一章预告

第十四章：密码学的革命——1976年，为什么公开一把钥匙反而更安全？

1976年，Whitfield Diffie 和 Martin Hellman 发表论文：New Directions in Cryptography。在此之前，密码通信长期面临一个难题：如果两个人想要加密通信，他们首先需要以安全方式共享秘密密钥。但如果双方从未见过面，又该如何建立共同秘密？Diffie 与 Hellman 提出了一种彻底改变密码学研究方向的思想。双方可以通过公开通信，协商出只有彼此知道的秘密。而后来的 RSA 等公钥密码技术，又进一步展示了：一部分密钥甚至可以直接公开给全世界。下一章，我们将回到1970年代斯坦福大学及更早的英国密码研究历史，从真实论文出发，理解公钥密码、密钥交换、模运算和单向计算的联系。最令人不可思议的问题是：如果攻击者能够听到双方交换的全部消息，为什么仍然不一定能得到最后的秘密密钥？