玄関＞コンピュータの部屋＞各種解説コーナー＞データ圧縮法概説
目次 第1章 第2章 第3章 第4章 第5章 第6章 第7章
１ ２ ３ ４ ５

6.6 LZW符号の復号化実例

例として、符号化の実例で符号化した「(97)(97)(98)(98)(99)(260)(99)(100)(263)(100)(101)(266)(267)(266)(102)(270)(102)」を前節の手順に従って復号化してみましょう。

  1. 元データを８ビットの記号とし、最初に256種類の全記号を登録した辞書を用意する。 その場合、記号を８ビットの整数として扱った場合の整数値をそのまま参照番号とする。 そして記号列を記憶するための場所を用意し、読み込む符号のビット数ｐを９と初期化する。
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    記号列＝(空)　　ｐ＝９
  2. 最初の符号「97」を読み込み、それを８ビットの記号としたものを出力し、同時に記号列として記憶する。
    読み込んだ番号＝97
    出力データ：ａ
    記号列＝ａ　　ｐ＝９
  3. 次の符号「97」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「97」は辞書にあるのでそれに対応する語句「ａ」を出力し、同時にその語句の最初の記号ａを現在の記号列に追加した「ａａ」を新しい語句として辞書に登録する。

    読み込んだ番号＝97
    出力データ：ａ
    記号列＝ａ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号
    ａａ256
    登録語句＝ａａ：参照番号＝256
  4. 今出力した「ａ」をあらためて記号列とする。
    記号列＝ａ　　ｐ＝９
  5. 次の符号「98」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「98」は辞書にあるのでそれに対応する語句「ｂ」を出力し、同時にその語句の最初の記号ｂを現在の記号列に追加した「ａｂ」を新しい語句として辞書に登録する。

    読み込んだ番号＝98
    出力データ：ｂ
    記号列＝ａ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号
    ａａ256ａｂ257
    登録語句＝ａｂ：参照番号＝257
  6. 今出力した「ｂ」をあらためて記号列とする。
    記号列＝ｂ　　ｐ＝９
  7. 次の符号「98」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「98」は辞書にあるのでそれに対応する語句「ｂ」を出力し、同時にその語句の最初の記号ｂを現在の記号列に追加した「ｂｂ」を新しい語句として辞書に登録する。

    読み込んだ番号＝98
    出力データ：ｂ
    記号列＝ａ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258
    登録語句＝ｂｂ：参照番号＝258
  8. 今出力した「ｂ」をあらためて記号列とする。
    記号列＝ｂ　　ｐ＝９
  9. 次の符号「99」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「99」は辞書にあるのでそれに対応する語句「ｃ」を出力し、同時にその語句の最初の記号ｂを現在の記号列に追加した「ｂｃ」を新しい語句として辞書に登録する。

    読み込んだ番号＝99
    出力データ：ｃ
    記号列＝ｂ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259
    登録語句＝ｂｃ：参照番号＝259
  10. 今出力した「ｃ」をあらためて記号列とする。
    記号列＝ｃ　　ｐ＝９
  11. 次の符号「260」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「260」は辞書にないので、現在の記号列の最初の記号ｃを現在の記号列に追加した「ｃｃ」を出力し、同時に新しい語句として辞書に登録する。

    読み込んだ番号＝260
    出力データ：ｃｃ
    記号列＝ｃ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260
    登録語句＝ｃｃ：参照番号＝260
  12. 今出力した「ｃｃ」をあらためて記号列とする。
    記号列＝ｃｃ　　ｐ＝９
  13. 次の符号「99」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「99」は辞書にあるのでそれに対応する語句「ｃ」を出力し、同時にその語句の最初の記号ｃを現在の記号列に追加した「ｃｃｃ」を新しい語句として辞書に登録する。

    読み込んだ番号＝99
    出力データ：ｃ
    記号列＝ｃｃ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261
    登録語句＝ｃｃｃ：参照番号＝261
  14. 今出力した「ｃ」をあらためて記号列とする。
    記号列＝ｃ　　ｐ＝９
  15. 次の符号「100」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「100」は辞書にあるのでそれに対応する語句「ｄ」を出力し、同時にその語句の最初の記号ｄを現在の記号列に追加した「ｃｄ」を新しい語句として辞書に登録する。

    読み込んだ番号＝100
    出力データ：ｄ
    記号列＝ｃ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262
    登録語句＝ｃｄ：参照番号＝262
  16. 今出力した「ｄ」をあらためて記号列とする。
    記号列＝ｄ　　ｐ＝９
  17. 次の符号「263」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「263」は辞書にないので、現在の記号列の最初の記号ｄを現在の記号列に追加した「ｄｄ」を出力し、同時に新しい語句として辞書に登録する。

    読み込んだ番号＝263
    出力データ：ｄｄ
    記号列＝ｄ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    登録語句＝ｄｄ：参照番号＝263
  18. 今出力した「ｄｄ」をあらためて記号列とする。
    記号列＝ｄｄ　　ｐ＝９
  19. 次の符号「100」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「100」は辞書にあるのでそれに対応する語句「ｄ」を出力し、同時にその語句の最初の記号ｄを現在の記号列に追加した「ｄｄｄ」を新しい語句として辞書に登録する。

    読み込んだ番号＝100
    出力データ：ｄ
    記号列＝ｄｄｄ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号
    ｄｄｄ264
    登録語句＝ｄｄｄ：参照番号＝264
  20. 今出力した「ｄ」をあらためて記号列とする。
    記号列＝ｄ　　ｐ＝９
  21. 次の符号「101」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「101」は辞書にあるのでそれに対応する語句「ｅ」を出力し、同時にその語句の最初の記号ｅを現在の記号列に追加した「ｄｅ」を新しい語句として辞書に登録する。

    読み込んだ番号＝101
    出力データ：ｅ
    記号列＝ｄ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号
    ｄｄｄ264ｄｅ265
    登録語句＝ｄｅ：参照番号＝265
  22. 今出力した「ｅ」をあらためて記号列とする。
    記号列＝ｅ　　ｐ＝９
  23. 次の符号「266」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「266」は辞書にないので、現在の記号列の最初の記号ｅを現在の記号列に追加した「ｅｅ」を出力し、同時に新しい語句として辞書に登録する。

    読み込んだ番号＝266
    出力データ：ｅｅ
    記号列＝ｅ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266
    登録語句＝ｅｅ：参照番号＝266
  24. 今出力した「ｅｅ」をあらためて記号列とする。
    記号列＝ｅｅ　　ｐ＝９
  25. 次の符号「267」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「267」は辞書にないので、現在の記号列の最初の記号ｅを現在の記号列に追加した「ｅｅｅ」を出力し、同時に新しい語句として辞書に登録する。

    読み込んだ番号＝267
    出力データ：ｅｅｅ
    記号列＝ｅｅ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266ｅｅｅ267
    登録語句＝ｅｅｅ：参照番号＝267
  26. 今出力した「ｅｅｅ」をあらためて記号列とする。
    記号列＝ｅｅｅ　　ｐ＝９
  27. 次の符号「266」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「266」は辞書にあるのでそれに対応する語句「ｅｅ」を出力し、同時にその語句の最初の記号ｅを現在の記号列に追加した「ｅｅｅｅ」を新しい語句として辞書に登録する。

    読み込んだ番号＝266
    出力データ：ｅｅ
    記号列＝ｅｅｅ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266ｅｅｅ267ｅｅｅｅ268
    登録語句＝ｅｅｅｅ：参照番号＝268
  28. 今出力した「ｅｅ」をあらためて記号列とする。
    記号列＝ｅｅ　　ｐ＝９
  29. 次の符号「102」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「102」は辞書にあるのでそれに対応する語句「ｆ」を出力し、同時にその語句の最初の記号ｆを現在の記号列に追加した「ｅｅｆ」を新しい語句として辞書に登録する。

    読み込んだ番号＝102
    出力データ：ｆ
    記号列＝ｅｅｆ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266ｅｅｅ267ｅｅｅｅ268ｅｅｆ269
    登録語句＝ｅｅｆ：参照番号＝269
  30. 今出力した「ｆ」をあらためて記号列とする。
    記号列＝ｆ　　ｐ＝９
  31. 次の符号「270」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「270」は辞書にないので、現在の記号列の最初の記号ｅを現在の記号列に追加した「ｆｆ」を出力し、同時に新しい語句として辞書に登録する。

    読み込んだ番号＝270
    出力データ：ｆｆ
    記号列＝ｆ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266ｅｅｅ267ｅｅｅｅ268ｅｅｆ269ｆｆ270
    登録語句＝ｆｆ：参照番号＝270
  32. 今出力した「ｆｆ」をあらためて記号列とする。
    記号列＝ｆｆ　　ｐ＝９
  33. 次の符号「102」を読み込み、その参照番号が現在の辞書にあるかどうか調べる。

    「102」は辞書にあるのでそれに対応する語句「ｆ」を出力し、同時にその語句の最初の記号ｆを現在の記号列に追加した「ｆｆｆ」を新しい語句として辞書に登録する。

    読み込んだ番号＝102
    出力データ：ｆ
    記号列＝ｆｆｆ　　ｐ＝９
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266ｅｅｅ267ｅｅｅｅ268ｅｅｆ269ｆｆ270ｆｆｆ271
    登録語句＝ｆｆｆ：参照番号＝271
  34. 今出力した「ｆ」をあらためて記号列とする。
    記号列＝ｆ　　ｐ＝９
  35. 符号データ終了。

この結果、最終的な復元データは次のようになります。

復元データ：ａａｂｂｃｃｃｃｄｄｄｄｅｅｅｅｅｅｅｅｆｆｆｆ

6.7 LZ78符号化の特徴

最終更新日：2001年7月2日 　第5節へ← →第7章へ
【我楽多頓陳館】 　〒webmaster@snap-tck.com 　Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)