LZ77

LZ77は、1977年ねんにジェイコブ・ジヴ (Jacob Ziv) とエイブラハム・レンペル (Abraham Lempel) によって開発かいはつされたデータ圧縮あっしゅくアルゴリズム。LZ77を改良かいりょうしたLZSSにハフマン符号ふごう化かを組くみ合あわせ改良かいりょうされたDeflateが、圧縮あっしゅくツールのLHAやGZIPなどに用もちいられている。LZ77を使つかっていると書かいてあるケースでも、厳密げんみつには、ほとんどのケースでLZ77の改良かいりょうであるLZSSが使つかわれている。

LZ77やLZ78の論文ろんぶんの著者ちょしゃ名めいはZiv and Lempelの順じゅんであるが、LZの順じゅんで呼よばれることが多おおい。

符号ふごう化かの原理げんり

データを先頭せんとうから順番じゅんばんに符号ふごう化かしていく方式ほうしきである。 現在げんざい注目ちゅうもくしている位置いちから始はじまる記号きごう列れつが、それ以前いぜんに出現しゅつげんしていたかを探さがす。 もし出現しゅつげんしていたならば、記号きごう列れつをその出現しゅつげん位置いちと長ながさのポインタに置おき換かえる。 記号きごう列れつを探さがす範囲はんいをスライド窓まどと呼よび、これを辞書じしょとして使用しようするので、辞書じしょ式しき圧縮あっしゅく法ほうと呼よばれる。

もともとのLZ77では、記号きごう列れつを（一致いっち位置いち、一致いっち長ちょう、次つぎの不一致ふいっち記号きごう）という3つの値ねに置おき換かえるが、さまざまな亜種あしゅが存在そんざいする。 中なかでもLZSSは、単純たんじゅんで性能せいのうもよく、いろいろな応用おうように使用しようされている。

特許とっきょ

辞書じしょ探索たんさくにおいて、ツリーを用もちいる方法ほうほうはゼロックスが、ハッシュテーブルを使用しようする方法ほうほうはStac社しゃが特許とっきょを保持ほじしていた。その他た、色々いろいろな会社かいしゃ・人物じんぶつが様々さまざまな特許とっきょを取得しゅとくした。ただし、特許とっきょのほとんどは既すでに有効ゆうこう期限きげんが切きれている。

関連かんれん項目こうもく

• LZ78