LZ77

読み：エルズィーなななな
外語：LZ77: Lempel-Ziv 77

品詞：固有名詞

圧縮アルゴリズムであるLZの一つで、1977(昭和52)年に発明されたもの。その後の情報圧縮に革命をもたらした。

概要

Abraham LempelとJacob Zivが1977(昭和52)年に発明した。

LZ77は、スライド辞書法と呼ばれる方法を採用している。局所的辞書(適用範囲が一部に限られる)を使い、既に読込まれた辞書の中から最も長い一致文字列を探し出して、そのポインター(位置+一致長)に置き換える。出力はポインターと記号(未一致文字)が交互に登場する。

次のような応用が確認されている。

様々なソフトウェアで広く利用されているアルゴリズムである。

LZ77自体には特許は無く、それゆえに、オープンソースコミュニティーに愛用されてきた。

しかし、ハッシュを使ったLZ77はStacが、ツリーを使ったLZ77はXeroxがそれぞれ後から(彼らが発明したのではないにも関わらず)次々と特許にするに到り、LZ77を多く使うオープンソースの存在が危ぶまれた。

もちろん、この二社は世界中から強く非難されている。

用語の所属