LZ77 - 通信用語の基礎知識

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

概要

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

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

特徴

応用例

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

利用例

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

特許問題

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

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

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

リンク

用語の所属

77
関連する用語