LZ - 通信用語の基礎知識

圧縮アルゴリズムの一つで、最も代表的なもの。「ユニバーサル符号」と呼ばれるものに分類される。現在主流の高圧縮率を誇るアルゴリズムの殆どが、何らかの形でこの方式を利用している。

概要

イスラエル人Abraham LempelとJacob Zivにより発明された。LZは、この二人の名前の頭文字に由来する。

LZ法が発表された当初は、論文に書かれていた考案者の名前の順番を取ってZL符号法と呼ばれていたが、ある研究者のミスからLZ符号法として一般に知られてしまった。このため現在ではZL77やZL78といった記述は一部の研究者のみが使う呼称となってしまった。

LZに様々な工夫を加えたものが広く使われている。但し現在では、彼らが考えたLZアルゴリズムに対して何の改良も加ていないもの(つまりLZ方式そのまま)は、研究目的以外で使われることはまず無い。

特徴

辞書法

LZ法は、辞書法と呼ばれる手法を用いている。これは、1970年代の研究の中心だったハフマン符号などには無かった発想である。

1977(昭和52)年に辞書法に関する最初の論文が発表されたが、情報圧縮の分野で注目する人はごくわずかだった。翌1978(昭和53)年にLZ78符号の発表がなされたが、本格的に研究が始まったのは1984(昭和59)年のLZWの発表を待ってからの事である。

符号法

符号化しようとするデータ列が、過去のデータ内に存在した時に、以前のデータ列の位置と長さを符号として用いる。つまり、同じ内容のデータ列が継続して出現する場合に高い圧縮率を得ることができる。

実際には実現方法でさらに「スライド辞書法」と「動的辞書法」の二つに分けられ、前者がLZ77法、後者がLZ78法である。

GIFなどの圧縮に使われるLZW法は後者に分類される。

種類

現在知られる範囲では、次のような亜種が存在する(順不同)。

リンク

用語の所属

LZ
関連する用語