玄関コンピュータの部屋各種解説コーナーデータ圧縮法概説

6.5 LZW符号の復号化手順

LZW符号の復号化手順は以下のとおりです。

  1. 元データを8ビットの記号とし、最初に256種類の全記号を登録した辞書を用意する。 その場合、記号を8ビットの整数として扱った場合の整数値をそのまま参照番号とする。 そして記号列を記憶するための場所を用意し、読み込む符号のビット数pを9と初期化する。
    語句番号語句番号語句番号
    (0)0(1)1(255)255
    記号列=(空)  p=9

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

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

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

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

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

    読み込んだ番号=384
    出力データ:a…b
    記号列=c…da  p=9
    語句番号語句番号語句番号
    (0)0(1)1(255)255
    語句番号語句番号語句番号
    ××256a…b384c…dan
    登録語句=c…da:参照番号=n
  4. 読み込んだ符号が表す参照番号が辞書にないならば、つまり(現在の辞書の語句登録数−1)より大きい値ならば、現在の記号列の最初の記号を記号列に追加したものを出力し、同時にそれを新しい語句として辞書に登録する。

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

    読み込んだ番号=384
    記号列=c…d  p=9
    出力データ:c…dc
    語句番号語句番号語句番号
    (0)0(1)1(255)255
    語句番号語句番号
    ××256c…dc384
    登録語句=c…dc:参照番号=384
  5. 今出力した語句をあらためて記号列とする。
    記号列=a…b  p=9
  6. 符号化データが終了するまで3.から5.を繰り返す。

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