LZW圧縮アルゴリズムの概要。

GIF画像を取扱うのに欠かせないLZW圧縮について解説します。

特にGIF画像の処理におけるLZW圧縮について解説致します。

LZW圧縮の原理。

LZW圧縮は、LZ77圧縮を改良したものとして知られております。

LZ77圧縮は、過去に出てきた単語が再度出てきたら、それを符号化するというものでした。

しかし、LZ77圧縮の最もプリミティヴなコーディングでは、いちいち圧縮した文字列を再度検索しなければなりませんでした。

このため、効率良い圧縮を実現する為に、LZW圧縮では辞書と呼ばれる記憶領域を用意します。

辞書には、圧縮過程で出てきた単語を逐次登録する事となっており、圧縮処理ではこの辞書を検索すれば良い事になります。

具体的なLZW圧縮アルゴリズムは以下のようになります。

まず、最初の一文字を読込んで、それを変数wに入れます。
1. (※)次の一文字を読込んで、変数kに入れます。
2. また、変数wの直後に変数kが続いているストリングを変数wkに入れます。すなわち、wk:=w+kとなります。
3. この変数wkが辞書に登録されているかを調べます。
4. もし、登録されているのなら、再度(※)に戻って、更に一文字追加して検索を試みます。辞書から検索できたら同様に何文字でも追加します。こうする事で、最大限に長い単語を辞書から検索するようにしている訳です。
5. 逆に、変数wkが辞書登録されていなければ、kを継ぎ足していない状態のwまでは辞書に載っていた訳ですから、そこまでを辞書の登録番号で符号化します。一方、kを継ぎ足したものは辞書に無かった訳ですのでこの時点で辞書に登録します。そして、残りの変数kを新たに変数wに入れて、再度(※)に戻ります。つまり、新たに変数kで始まる単語の検索に入る訳です。
文字列を読み切ってしまった場合は、当然変数wに未処理の単語が入っています。更に、その単語は辞書に載っていた筈で、当然辞書の登録番号で符号化出来ます。

つまり、検索出来なくなるまで単語を一文字づつ伸ばして行って、検索できなくなったらそこまでの単語を符号化して行くという仕組みです。

尚、一文字だけの単語は予め全て文字コードを登録番号と見做します。この事から、辞書において複数文字からなる単語は、常に文字コードの上限値より大きな値になる事が分かります。
辞書登録を際限なく行うようすると、データが続く限り辞書データも増え続け、その結果符号のビット数も長くなり過ぎて処理に支障が出る可能性があります。そこで、一般にLZW圧縮を応用する規格では、仕様で辞書に登録する単語数に上限を設け、上限を越えたら新たな単語登録は行わないものとしております。GIF画像形式では4,096個以内と決められております。

GIF画像形式では、LZW圧縮にある拡張を施しております。

具体的には、一文字単語のほか、クリアコードと終了コードと呼ばれる特別な文字を登録済みと見做します。

クリアコードは辞書データなどを全て初期化すると言う意味です。

このコードは必要に応じていつでも発行する事が出来ます。

主に辞書が一杯になって新たな単語登録ができなくなった場合にクリアコードを発行して辞書をクリアすると言う使い方があります。
但し、クリアコードを発行すると、これまで作った辞書が無効になってしまうので、辞書を引続き使いたいと言う場合は新たな辞書登録が出来なくなる事を承知の上でクリアコードを発行せずに辞書を使い続けると言う選択肢もあります。GIFデコーダは辞書が一杯になったら自動的にクリアコードが発行される事を期待してはいけない事となっております。
仕様では明確に規定されていませんが、圧縮データの始めにもクリアコードが出力されます。

一方の終了コードは圧縮データを全て出力した後に発行しなければならない事となっております。

さて、実際に圧縮されたデータをどのようにしてデータとするかという問題があります。

GIF画像で発行する圧縮データは辞書での登録番号です。

このデータのビット数は、圧縮開始時(及びクリアコード発行直後)では、圧縮前の文字を表現できる最小ビット数に 1を加えたものです( 4ビットデータなら 5ビット)。

この時点で、文字コードとクリア・終了コードが定義済みとなりますが、まだ辞書コード用の番号が割当てられます。

但し、文字が 1ビット(白黒二階調画像)の場合は、文字コードが 2個、クリア・終了コードが 2個の計 4個となり、 1ビット加えた 2ビットだとこれだけで一杯になってしまい、新たな辞書コードを割当てる事が出来ません。この為、文字のビット長が 1の場合は 2ビットデータと見做して処理する事となっております。

辞書への登録が繰返される事で、いつかは辞書コードが出力ビット数では入り切らなくなります。

その場合は発行データのビット数に 1を加える事で、新たな辞書コードの割当が出来るようにします。

但し、出力ビット数の拡張は際限なく行われる訳では無く、12ビットに達したらそれ以上はビット数を拡げない事としております。

さて、この様にGIFでは 3～12ビットの圧縮データが発行されます( 1ビットデータの場合は 2ビット扱いとしており、それに 1を加えた 3ビットから始まります。その他は文字のビット数に 1を加えた値、すなわち 3ビット～ 9ビットで始まります。

圧縮された辞書データは出力データのオクテットに順次隙間無く詰めていく事になっております。

これにより、例えば 4ビットの圧縮データなら 1オクテットに 2個入るようになり、圧縮データの更なる圧縮が期待できます。

勿論、発行したデータがオクテットに入り切らない場合は次のオクテットに流し込まれて行きます。データは最大12ビットなので、最大で 3オクテットに亘って流し込まれる事になります。

LZW圧縮のアルゴリズムが最も具体的且つ平易に書かれております。

GIFにおけるLZW圧縮について具体的に記されております。