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

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

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

記号列＝(空)　　ｐ＝９

復号化の場合もこの最初の256個のエントリーは実際には用意する必要ありませんが、原理をわかりやすくするためにやはり書いておきます。

最初の符号を読み込み、それが表す辞書の参照番号に対応する記号を出力すると同時に記号列として記憶する。

最初の符号は必ず255以内の番号ですから、それを８ビットの記号として扱った場合の記号をそのまま出力します。例えば最初の番号が97で、それを８ビットの記号として扱ったものがａだとしますと、

読み込んだ番号＝97
出力データ：ａ
記号列＝ａ　　ｐ＝９

次の符号を読み込み、それが表す参照番号が辞書にあるならば、つまり(現在の辞書の語句登録数−１)以下ならばそれに対応する語句を出力し、同時にその語句の最初の記号を現在の記号列に追加したものを新しい語句として辞書に登録する。

例えば読み込んだ番号が384で、それに対応する語句が「ａ…ｂ」、現在の記号列が「ｃ…ｄ」だとしますと、

読み込んだ番号＝384
出力データ：ａ…ｂ
記号列＝ｃ…ｄａ　　ｐ＝９

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

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

登録語句＝ｃ…ｄａ：参照番号＝n

読み込んだ符号が表す参照番号が辞書にないならば、つまり(現在の辞書の語句登録数−１)より大きい値ならば、現在の記号列の最初の記号を記号列に追加したものを出力し、同時にそれを新しい語句として辞書に登録する。

例えば読み込んだ番号が384で、現在の辞書の登録語句数が384個、現在の記号列が「ｃ…ｄ」だとしますと、

読み込んだ番号＝384
記号列＝ｃ…ｄ　　ｐ＝９
出力データ：ｃ…ｄｃ

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

語句	番号	…	語句	番号
××	256	…	ｃ…ｄｃ	384

登録語句＝ｃ…ｄｃ：参照番号＝384

今出力した語句をあらためて記号列とする。

記号列＝ａ…ｂ　　ｐ＝９

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

復号化の場合、語句を辞書に登録するタイミングが符号化時に比べてワンテンポ遅れますので、途中で新しい登録語句の参照番号ｎが(2^p−2)となった時、つまりその時の辞書の登録数が(2^p−1)個になった時、ｐを１増やして次から読み込む符号のビット数を１ビット増やします。また辞書の最大登録数Ｍと登録語句数が(Ｍ−１)個に達した時の処理は、当然、符号化時と同じにします。

6.5 LZW符号の復号化手順