Lempel–Ziv–Welch

Lempel-Ziv-Welch (LZW) 圧縮アルゴリズム

Lempel-Ziv-Welch (LZW) アルゴリズムは、1984年にTerry Welch氏によって開発されたデータ圧縮アルゴリズムです。Lempel-Zivアルゴリズム(LZ78)を改良したもので、その効率性と速度から、画像ファイル形式のGIFやTIFF、PDFなどの圧縮に広く利用されています。

アルゴリズムの概要

LZWは辞書を用いた圧縮方式です。初期状態では、すべての可能な文字（またはシンボル）が辞書に登録されます。アルゴリズムは入力データを読み込み、辞書に登録されている最長の文字列を探し、その文字列に対応するインデックス（コード）を出力します。次に、見つかった文字列の次に続く文字を付け加えた新たな文字列を辞書に追加します。この処理をデータの最後まで繰り返すことで圧縮を行います。

同じパターンが繰り返されるデータに対して高い圧縮率を発揮します。初期段階では圧縮率は低くなりますが、辞書が成長するにつれて圧縮率は向上します。入力データは文字列に限らず、例えば画像データであれば、カラーテーブルのインデックスなどを文字として扱うことができます。

効率を上げるために、可変長コード、辞書クリアコード、ストップコードといった工夫が凝らされています。可変長コードは、コードの長さを状況に応じて変更することで、より効率的な圧縮を可能にします。辞書クリアコードは、辞書が満杯になった際に辞書を初期化し、圧縮効率を維持します。ストップコードはデータの終端を示します。

圧縮データには辞書情報を含める必要がないため、データサイズを小さく保てます。ただし、エンコーダーとデコーダーは、文字サイズ、最大辞書サイズ、可変長エンコーディングの有無、初期コード幅、クリアコードとストップコードの有無といったパラメータについて、事前に合意しておく必要があります。多くのフォーマットでは、これらの情報はフォーマット仕様またはヘッダーに記述されています。

エンコーディングとデコーディング

エンコーディング

1. 使用可能な文字すべてで辞書を初期化する。
2. 入力文字列と最長のマッチする文字列Wを辞書から探す。
3. Wのインデックスを出力する。
4. 入力文字列からWを除去する。
5. 次の文字sをWに付け加えたW+sを辞書に追加する。
6. 2に戻る。

デコーディング

1. 辞書を初期化する。
2. 入力からコードを読み込み、対応する文字列Wを得る。
3. Wを出力する。
4. 次のコードを読み込む。
5. 次のコードに対応する文字列の最初の文字sをWに付け加えたW+sを辞書に追加する。
6. 2に戻る。

可変幅コードとEarly Change

可変幅コードを使用する場合、エンコーダーとデコーダーはコード幅の変更を同期する必要があります。コード幅の変更タイミングの違いによって、Early Changeと呼ばれる問題が発生することがあります。Early Changeは、エンコーダーとデコーダーでコード幅の変更タイミングがずれることで、デコード結果が異なる問題です。アドビはPDFファイルで両方のバージョンを許容していますが、ヘッダーにEarly Changeの有無を示すフラグを含めています。TIFFはEarly Changeを使用しますが、GIFなどは使用しません。

パッキング順序

コードはバイト境界に一致しないため、エンコーダーとデコーダーはコードをバイトにパックする順序を合意する必要があります。LSB-FirstとMSB-Firstの2つの方法があります。GIFはLSB-First、TIFFとPDFはMSB-Firstを使用します。

LZWの特許問題

LZWアルゴリズムは、かつてスペリー社（後にユニシス社）によって特許が取得されていました。この特許はGIF画像の圧縮にも影響を与え、いわゆる「GIF特許問題」を引き起こしました。現在、この特許は期限切れとなっています。

まとめ

LZWは、効率的な辞書ベースの圧縮アルゴリズムであり、多くのファイルフォーマットで利用されています。可変長コードや辞書クリアなどの高度な技術により、高い圧縮率と速度を実現しています。ただし、エンコーダーとデコーダー間の同期や、かつて存在した特許の問題にも注意が必要です。

もう一度検索