既に送信されたテキストを指し示すZiv-Lempel圧縮データ

古典的な圧縮はハフマン符号化を中心としていたが、ハフマン符号化では符号化を行う前に記号確率モデルを構築する必要がある。1977年まで、ほとんどの研究はそのモデルがどこかから供給される必要があると想定していた。

TechnionのJacob ZivとAbraham Lempelは「A Universal Algorithm for Sequential Data Compression」において、そのモデルを不要にできることを示した。エンコーダは最近見たテキストのウィンドウを保持し、入力される先読みバッファと照合する。一致はオフセットと長さとして書き出されるため、繰り返しのコストはほとんどかからない。

その結果は汎用的な方式である。辞書がデータそのものであるため、事前の統計なしで任意の情報源を圧縮できる。1977年の論文は、辞書圧縮をgzip、PNG、ZIPファミリーの基盤とした古典である。

事前計算するのではなく、既に見たテキストを指し示す

既に送信されたテキストを辞書として使うため、事前計算された確率表は不要である。

単一のオフセットと長さのトークンが、長短を問わず任意の繰り返しフレーズを処理する。

この方式は未知の情報源に対して機能するため、ファイル種別に合わせて調整されたものではなく汎用的である。

事前にデータのモデルを構築するのではなく、データ自身にその構造を進行に合わせて供給させる。自己参照的な表現は、どのような入力であってもそれに適応する。

LZ方式は現代の可逆圧縮の基盤となった。LZ77とその子孫であるLZ78/LZWは、gzip、zip、PNG、そしてウェブ全体で使われるDEFLATEストリームを支えている。ZivとLempelの論文は、IEEE Information Theory Societyの1997年Golden Jubilee Technological Innovation Awardを受賞した。