案例库 · 工程与运营 · 技术决策 · 1977
Ziv和Lempel通过指回已发送的文本来压缩数据
LZ77通过“回退N并复制L个符号”来缩减数据，而不是预先约定的码本，使压缩变得通用。
Technion — Israel Institute of Technology
那一手
经典压缩以霍夫曼编码为中心，但霍夫曼编码需要先建立符号概率模型才能编码。直到1977年，大多数工作都假设这个模型必须来自某个地方。
在《一种用于顺序数据压缩的通用算法》中，Technion的Jacob Ziv和Abraham Lempel展示了这个模型可以被抛弃。编码器保留最近看到的文本窗口，并将输入的前瞻缓冲区与窗口中的内容进行匹配；匹配被写入为偏移量和长度，因此重复部分几乎不花费成本。
结果是一种通用方案——它压缩任何源，无需先验统计，因为字典就是数据本身。1977年的这篇论文是经典之作，使字典压缩成为gzip、PNG和ZIP系列的基础。
为什么管用
- 使用已发送的文本作为字典，不需要预先计算的概率表。
- 单一的偏移加长度标记可以处理任意重复短语，无论长短。
- 该方案适用于未知源，因此通用而非针对特定文件类型调整。
值了多少指回已经看过的文本，而不是预先计算神来之笔
可以搬走什么
不要提前构建数据模型；让数据在过程中提供自己的结构。自引用表示适应任何输入，无论它是什么。
后来呢
LZ方法成为现代无损压缩的基础：LZ77及其后代LZ78/LZW为gzip、zip、PNG和Web上使用的DEFLATE流提供动力。Ziv和Lempel的论文获得了IEEE信息论学会1997年金禧技术创新奖。
资料来源
- A universal algorithm for sequential data compression
- The Data Compression Book — Chapter 8: Sliding Window Compression
发现哪里写错了？告诉我们。