LZ77
読み：エルズィーなななな
外語：LZ77: Lempel-Ziv 77
圧縮アルゴリズムであるLZの一つで、1977(昭和52)年に発明されたもの。その後の情報圧縮に革命をもたらした。
概要
Abraham LempelとJacob Zivが1977(昭和52)年に発明した。
LZ77は、スライド辞書法と呼ばれる方法を採用している。局所的辞書(適用範囲が一部に限られる)を使い、既に読込まれた辞書の中から最も長い一致文字列を探し出して、そのポインター(位置+一致長)に置き換える。出力はポインターと記号(未一致文字)が交互に登場する。
特徴
応用例
次のような応用が確認されている。
利用例
様々なソフトウェアで広く利用されているアルゴリズムである。
特許問題
LZ77自体には特許は無く、それゆえに、オープンソースコミュニティーに愛用されてきた。
しかし、ハッシュを使ったLZ77はStacが、ツリーを使ったLZ77はXeroxがそれぞれ後から(彼らが発明したのではないにも関わらず)次々と特許にするに到り、LZ77を多く使うオープンソースの存在が危ぶまれた。
もちろん、この二社は世界中から強く非難されている。
再検索