解決方案
古典壓縮以霍夫曼編碼為核心,但霍夫曼編碼需要先建立符號機率模型才能進行編碼。直到 1977 年,多數研究都假設該模型必須來自某處。
在《A Universal Algorithm for Sequential Data Compression》中,Technion 的 Jacob Ziv 與 Abraham Lempel 證明該模型可以被捨棄。編碼器保留一個近期所見文字的視窗,並將即將到來的預看緩衝區與之進行比對;一處相符會被寫成一個位移與一個長度,因此重複內容幾乎不花成本。
結果是一種通用方案——它能壓縮任何來源而無需事先的統計資料,因為字典就是資料本身。1977 年的論文是經典之作,使字典壓縮成為 gzip、PNG 與 ZIP 家族的基礎。
它達成了什麼
指回已經看過的文字,而非事先計算
為何有效
使用已傳送的文字作為字典,不需要事先計算的機率表。
單一位移加長度的權杖可處理任何重複片語,無論長短。
此方案適用於未知來源,因此它是通用的,而非針對某種檔案類型調校。
可套用之處
不要事先建立資料的模型;讓資料在過程中自行提供其結構。自我參照的表示法能適應任何輸入,無論那是什麼。
後續發展
LZ 方法成為現代無損壓縮的基礎:LZ77 及其後繼 LZ78/LZW 支撐了 gzip、zip、PNG 以及網路上廣泛使用的 DEFLATE 串流。Ziv 與 Lempel 的論文獲得了 IEEE 資訊理論學會 1997 年 Golden Jubilee Technological Innovation Award。
追溯依據
參考來源
- A universal algorithm for sequential data compression IEEE Information Theory Society · itsoc.org
- The Data Compression Book — Chapter 8: Sliding Window Compression Mark Nelson · cmd.inp.nsk.su