Lempel–Ziv–Storer–Szymanski

Lempel-Ziv-Storer-Szymanski (LZSS) アルゴリズムは、1982 年に James Storer と Thomas Szymanski によって開発された、効率的なデータ圧縮手法です。LZ77 アルゴリズムを改良したもので、LHA や ZIP などの多くの圧縮ソフトウェアで採用されています。

LZSS の中心的なアイデアは、データに繰り返し出現するパターンを効率的に検出し、それらを短いコードで表現することでデータサイズを削減することです。これは、データの冗長性を減らすことで圧縮を実現する手法です。

LZ77 アルゴリズムでは、データ列を (一致位置, 一致長, 次の不一致記号) の 3 つの値の組み合わせで表現します。しかし、一致が見つからない場合、(0, 0, 不一致記号) となり、冗長な情報を含んでしまうという欠点がありました。

LZSS はこの問題を解決するために、次のような工夫をしています。まず、一致が見つかったかどうかを 1 ビットで表します。一致が見つかった場合は、(1, 一致位置, 一致長) の形式で表現し、一致が見つからなかった場合は、(0, 不一致記号) の形式で表現します。この方法により、一致が見つからない場合でも、冗長な情報を最小限に抑えることができます。

具体的には、圧縮対象のデータ列において、現在処理している位置より前の部分で、最も長く一致する部分を探します。この一致の長さと、一致した部分の開始位置を記録します。一致した部分がなければ、単に次の文字をそのまま記録します。一致位置と一致長は、予め定められたビット数で表現されます。これによって、データの繰り返しパターンを効率的に符号化し、圧縮を実現します。

LZSS は LZ77 と比べて、アルゴリズム自体はそれほど複雑ではありませんが、一致が見つからない場合の処理を最適化することで、大幅な圧縮率の向上を実現しています。この高い圧縮性能が、LZSS が多くの圧縮ソフトウェアで利用されている理由です。

LZSS の特徴をまとめると以下のようになります。

LZ77 アルゴリズムの改良版
一致が見つかったかどうかの情報を 1 ビットで表現
一致位置と一致長を固定ビット数で表現
一致が見つからない場合の冗長性を削減
高い圧縮率
LHA、ZIP などの多くの圧縮ソフトウェアで使用

LZSS は、データ圧縮技術において重要な役割を果たしており、現在でも多くの応用がされています。そのシンプルなアルゴリズムと高い圧縮効率は、今後もデータ圧縮技術の発展に貢献していくでしょう。

関連項目

データ圧縮
LZ77

もう一度検索