データ圧縮法概説　第6章−２

LZ78符号は優れた特徴を持っているため、様々な工夫を凝らした改良型が開発されています。その中で最も有名なものが、1984年にSperry社のT.Welchによって開発された「LZW符号」です。この手法は元々コンピュータのハードウェアに実装するために開発されたもので、非常にコンピュータ向きのアルゴリズムのため、色々な圧縮ツールで広く利用され、GIFファイルにおける画像データの圧縮法としても採用されています。 (ただしこの手法の特許をUNISYS社が所有しているため、この手法を利用するためにはUNISYS社にロイヤリティを払う必要があります。)

ここでは、LZ78符号の代表としてLZW符号の符号化手順を説明することにします。

元データを８ビットの記号とし、最初に256種類の全記号を登録した辞書を用意する。その場合、記号を８ビットの整数として扱った場合の整数値をそのまま参照番号とする。そして最長一致系列とその参照番号を記憶するための場所を用意し、参照番号を符号化する時のビット数ｐを９と初期化する。

語句	番号	語句	番号	…	語句	番号
(0)	0	(1)	1	…	(255)	255

最長一致系列＝(空)：参照番号＝(空)　　ｐ＝９

LZW符号では記号が辞書にないということはないので、オリジナルのLZ78符号のように記号がなかったことを表す参照番号０は必要ありません。しかも記号が１つだけの場合はそれを８ビットの整数として扱った値がそのまま参照番号になりますから、いちいち辞書を調べる必要もありません。このため最初の256個のエントリーは実用上は用意する必要がないことになりますが、原理をわかりやすくするためにここではそのエントリーも書いておきます。

最初の記号を読み込んで最長一系列とし、それを整数として扱った値を参照番号として記憶する。

例えば最初の記号がａで、それを整数化した値が97だとしますと、

最長一致系列＝ａ：参照番号＝97　　ｐ＝９

次の記号を読み込み、それを最長一致系列に追加した「現在の最長一致系列＋今読み込んだ記号」という記号列を辞書から探す。もしその記号列が辞書にあればそれを新しい最長一致系列とし、その参照番号を記憶する。この操作を、「現在の最長一致系列＋読み込んだ記号」という記号列が辞書にないものになるまで繰り返す。

例えば読み込んだ記号がｂで、それを追加した記号列の参照番号が384だとしますと、

最長一致系列＝ａ…ｂ：参照番号＝384　　ｐ＝９

「現在の最長一致系列＋読み込んだ記号」という記号列が辞書にない場合は、現在の最長一致系列の参照番号をｐビットで符号化して出力し、記号列を新しい語句として辞書に登録する。

語句	番号	語句	番号	…	語句	番号
(0)	0	(1)	1	…	(255)	255

語句	番号	…	語句	番号	…	語句	番号
××	256	…	ａ…ｂ	384	…	ａ…ｂｃ	n

読み込んだ記号＝ｃ
最長一致系列＝ａ…ｂ：参照番号＝384　　ｐ＝９
符号化データ：384＝110000000(９ビットの整数化表現)
登録語句＝ａ…ｂｃ：参照番号＝n

今読み込んだ記号をあらためて最長一致系列とし、それを整数化した値を参照番号として記憶する。

最長一致系列＝ｃ：参照番号＝99　　ｐ＝９

元データが終了するまで3.から5.を繰り返す。

元データが終了した時、直前までの最長一致系列が出力されずに残っていますので、最後にその参照番号を符号化して出力します。

途中で新しい登録語句の参照番号ｎが(2^p−1)となった時、つまりその時の辞書の登録数が2^p個に達した時、ｐを１増やして次から出力する符号のビット数を１ビット増やします。また辞書の登録数が最大登録数Ｍに達した時は、辞書をそのまま固定するか、あるいは辞書をクリアしてまた最初から作成し直します。普通は辞書の最大登録数としてＭ＝2¹²＝4096(符号の最大ビット数＝12)程度がよく利用され、辞書の登録数がＭに達した時は最初から作成し直す方法がとられます。

以上のように、LZW符号は出力する符号を辞書の参照番号だけにした点が大きな特徴です。このため、１つの符号を参照番号と記号の組み合わせで構成するオリジナルのLZ78符号と比べますと、符号のビット数が少なくなり、符号化アルゴリズムがよりすっきりしてコンピュータ向きになっています。ただし１つ１つの符号のビット数は少なくなるものの、そのぶん出力する符号数が多くなりますから、全体としての圧縮効果はそれほど大幅には改善されません。

6.3 LZW符号化の手順