《一種用於順序資料壓縮的通用演算法》
不要重複——指回先前的那一份。每個 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.