《一种用于顺序数据压缩的通用算法》
不要重复——指回先前的那一份。每个 ZIP 里都藏着这个想法。
每个 ZIP 文件、每张网页、每幅 PNG 图像，能变小，都归功于 1977 年的一个想法：与其把话重说一遍，不如指回你先前说过它的地方。
把这个想法拆开看
真实的数据会重复。同样的词语、同样的代码模式、图像中同样成片的颜色——它们一次又一次地回来。伦佩尔与齐夫的洞见是：重复的那一段，你根本不必存。你可以把它换成一个小小的便条：「回退这么多个字符，复制那么多个。」这样一张便条，远比它所代表的文本要小。
巧妙之处在于，这个方法是边读边学会那些重复的。它对最近的过去开着一扇窗，每当前方的文本与窗内已有的东西相匹配，就把这段匹配换成一个指针。无需事先准备任何字典，也无需在旁附送任何额外信息——接收方仅凭这些指针，就能把一切重建出来。
它从哪里来
这个想法来自两位以色列工程师，雅各布·齐夫与亚伯拉罕·伦佩尔，他们在海法的以色列理工学院工作。他们 1977 年发表于《IEEE 信息论汇刊》的论文，铺陈了滑动窗口的方法；1978 年的续作给出了证明更清爽的第二个版本。两篇论文合称为「LZ」——LZ77 与 LZ78——它们一道，成了几乎所有通用压缩的骨干。两位作者并非在追逐某件产品；他们追的，是一个理论问题「可被证明地好」的答案，而那场实用的革命，随之而来。
它为何重要
有两点让它胜出。其一，它是通用的：你可以把它对准英文、中文、程序代码、传感器日志、一幅图像——任何东西——无需任何调校，它会自行适应。其二，它并非碰巧好用的小聪明；齐夫与伦佩尔证明了，它能逼近「任何压缩器所能做到的理论最优」。「对一切都管用」加上「可被证明地接近最优」，是一种罕见的组合，而这，正是这个想法渗入计算每一个角落的原因。
一个日常的类比
想象在一场冗长的会议上记笔记。当有人第三次说出同一句长长的话，你不会再把它写一遍——你会划一个箭头，潦草地写上「同上」。又或一份编织图样，写着「重复第 2–5 行四次」，而不是把二十行都印出来。LZ77 就是这种习惯，被做得精确无比：每一段重复，都化作一个精准的箭头，说明往回看多远、复制多少。
它处在哪里
这是本馆里一个三角形的第三个角。克劳德·香农（1948）证明了，原则上数据能被压到多小。大卫·Huffman（1952）找到了压缩单个符号的最佳办法。伦佩尔与齐夫则接手了两者都未覆盖的那部分——重复的短语——而现实世界里最主流的编码器 DEFLATE，让 LZ77 与 Huffman 首尾相接地运行，于是这三个想法，就在你每天用的 gzip 与 PNG 里，实实在在地携手协作。
A universal algorithm for sequential data compression is presented. Its performance is investigated with respect to a nonprobabilistic model of constrained sources. The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable-to-block codes designed to match a completely specified source.