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

6.4 LZW符号化の実例

例として、LZ77符号の例と同じ「aabbccccddddeeeeeeeeffff」という元データを前節の手順に従ってLZW符号化してみましょう。

  1. 元データを８ビットの記号とし、最初に256種類の全記号を登録した辞書を用意する。 その場合、記号を８ビットの整数として扱った場合の整数値をそのまま参照番号とする。 そして最長一致系列とその参照番号を記憶するための場所を用意し、参照番号を符号化する時のビット数ｐを９と初期化する。
    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    最長一致系列＝(空)：参照番号＝(空)　　ｐ＝９
  2. 最初の記号ａを読み込んで最長一系列とし、それを整数化した値を参照番号として記憶する。
    最長一致系列＝ａ：参照番号＝97　　ｐ＝９
  3. 次の記号ａを読み込み、それを最長一致系列に追加した「ａａ」という記号列を辞書から探す。

    この場合「ａａ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ａａ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号
    ａａ256
    読み込んだ記号＝ａ
    最長一致系列＝ａ：参照番号＝97　　ｐ＝９
    出力データ：97＝001100001(９ビットの整数化表現)
    登録語句＝ａａ：参照番号＝256
  4. 今読み込んだａをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ａ：参照番号＝97　　ｐ＝９
  5. 次の記号ｂを読み込み、それを最長一致系列に追加した「ａｂ」という記号列を辞書から探す。

    この場合「ａｂ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ａｂ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号
    ａａ256ａｂ257
    読み込んだ記号＝ｂ
    最長一致系列＝ａ：参照番号＝97　　ｐ＝９
    出力データ：97
    登録語句＝ａｂ：参照番号＝257
  6. 今読み込んだｂをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｂ：参照番号＝98　　ｐ＝９
  7. 次の記号ｂを読み込み、それを最長一致系列に追加した「ｂｂ」という記号列を辞書から探す。

    この場合「ｂｂ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｂｂ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258
    読み込んだ記号＝ｂ
    最長一致系列＝ｂ：参照番号＝98　　ｐ＝９
    出力データ：98
    登録語句＝ｂｂ：参照番号＝258
  8. 今読み込んだｂをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｂ：参照番号＝98　　ｐ＝９
  9. 次の記号ｃを読み込み、それを最長一致系列に追加した「ｂｃ」という記号列を辞書から探す。

    この場合「ｂｃ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｂｃ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259
    読み込んだ記号＝ｃ
    最長一致系列＝ｂ：参照番号＝98　　ｐ＝９
    出力データ：98
    登録語句＝ｂｃ：参照番号＝259
  10. 今読み込んだｃをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｃ：参照番号＝99　　ｐ＝９
  11. 次の記号ｃを読み込み、それを最長一致系列に追加した「ｃｃ」という記号列を辞書から探す。

    この場合「ｃｃ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｃｃ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260
    読み込んだ記号＝ｃ
    最長一致系列＝ｃ：参照番号＝99　　ｐ＝９
    出力データ：99
    登録語句＝ｃｃ：参照番号＝260
  12. 今読み込んだｃをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｃ：参照番号＝99　　ｐ＝９
  13. 次の記号ｃを読み込み、それを最長一致系列に追加した「ｃｃ」という記号列を辞書から探す。

    この場合「ｃｃ」は260番にあるので、それを新しい最長一致系列とし、その参照番号260を記憶する。

    最長一致系列＝ｃｃ：参照番号＝260　　ｐ＝９
  14. 次の記号ｃを読み込み、それを最長一致系列に追加した「ｃｃｃ」という記号列を辞書から探す。

    この場合「ｃｃｃ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｃｃｃ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261
    読み込んだ記号＝ｃ
    最長一致系列＝ｃｃ：参照番号＝260　　ｐ＝９
    出力データ：260
    登録語句＝ｃｃｃ：参照番号＝261
  15. 今読み込んだｃをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｃ：参照番号＝99　　ｐ＝９
  16. 次の記号ｄを読み込み、それを最長一致系列に追加した「ｃｄ」という記号列を辞書から探す。

    この場合「ｃｄ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｃｄ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262
    読み込んだ記号＝ｄ
    最長一致系列＝ｃ：参照番号＝99　　ｐ＝９
    出力データ：99
    登録語句＝ｃｄ：参照番号＝262
  17. 今読み込んだｄをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｄ：参照番号＝100　　ｐ＝９
  18. 次の記号ｄを読み込み、それを最長一致系列に追加した「ｄｄ」という記号列を辞書から探す。

    この場合「ｄｄ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｄｄ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    読み込んだ記号＝ｄ
    最長一致系列＝ｄ：参照番号＝100　　ｐ＝９
    出力データ：100
    登録語句＝ｄｄ：参照番号＝263
  19. 今読み込んだｄをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｄ：参照番号＝100　　ｐ＝９
  20. 次の記号ｄを読み込み、それを最長一致系列に追加した「ｄｄ」という記号列を辞書から探す。

    この場合「ｄｄ」は263番にあるので、それを新しい最長一致系列とし、その参照番号263を記憶する。

    最長一致系列＝ｄｄ：参照番号＝263　　ｐ＝９
  21. 次の記号ｄを読み込み、それを最長一致系列に追加した「ｄｄｄ」という記号列を辞書から探す。

    この場合「ｄｄｄ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｄｄｄ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号
    ｄｄｄ264
    読み込んだ記号＝ｄ
    最長一致系列＝ｄｄ：参照番号＝263　　ｐ＝９
    出力データ：263
    登録語句＝ｄｄｄ：参照番号＝264
  22. 今読み込んだｄをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｄ：参照番号＝100　　ｐ＝９
  23. 次の記号ｅを読み込み、それを最長一致系列に追加した「ｄｅ」という記号列を辞書から探す。

    この場合「ｄｅ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｄｅ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号
    ｄｄｄ264ｄｅ265
    読み込んだ記号＝ｅ
    最長一致系列＝ｄ：参照番号＝100　　ｐ＝９
    出力データ：100
    登録語句＝ｄｅ：参照番号＝265
  24. 今読み込んだｅをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｅ：参照番号＝101　　ｐ＝９
  25. 次の記号ｅを読み込み、それを最長一致系列に追加した「ｅｅ」という記号列を辞書から探す。

    この場合「ｅｅ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｅｅ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266
    読み込んだ記号＝ｅ
    最長一致系列＝ｅ：参照番号＝101　　ｐ＝９
    出力データ：101
    登録語句＝ｅｅ：参照番号＝266
  26. 今読み込んだｅをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｅ：参照番号＝101　　ｐ＝９
  27. 次の記号ｅを読み込み、それを最長一致系列に追加した「ｅｅ」という記号列を辞書から探す。

    この場合「ｅｅ」は266番にあるので、それを新しい最長一致系列とし、その参照番号266を記憶する。

    最長一致系列＝ｅｅ：参照番号＝266　　ｐ＝９
  28. 次の記号ｅを読み込み、それを最長一致系列に追加した「ｅｅｅ」という記号列を辞書から探す。

    この場合「ｅｅｅ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｅｅｅ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266ｅｅｅ267
    読み込んだ記号＝ｅ
    最長一致系列＝ｅｅ：参照番号＝266　　ｐ＝９
    出力データ：266
    登録語句＝ｅｅｅ：参照番号＝267
  29. 今読み込んだｅをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｅ：参照番号＝101　　ｐ＝９
  30. 次の記号ｅを読み込み、それを最長一致系列に追加した「ｅｅ」という記号列を辞書から探す。

    この場合「ｅｅ」は266番にあるので、それを新しい最長一致系列とし、その参照番号266を記憶する。

    最長一致系列＝ｅｅ：参照番号＝266　　ｐ＝９
  31. 次の記号ｅを読み込み、それを最長一致系列に追加した「ｅｅｅ」という記号列を辞書から探す。

    この場合「ｅｅｅ」は267番にあるので、それを新しい最長一致系列とし、その参照番号267を記憶する。

    最長一致系列＝ｅｅｅ：参照番号＝267　　ｐ＝９
  32. 次の記号ｅを読み込み、それを最長一致系列に追加した「ｅｅｅｅ」という記号列を辞書から探す。

    この場合「ｅｅｅｅ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｅｅｅｅ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266ｅｅｅ267ｅｅｅｅ268
    読み込んだ記号＝ｅ
    最長一致系列＝ｅｅｅ：参照番号＝267　　ｐ＝９
    出力データ：267
    登録語句＝ｅｅｅｅ：参照番号＝268
  33. 今読み込んだｅをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｅ：参照番号＝101　　ｐ＝９
  34. 次の記号ｅを読み込み、それを最長一致系列に追加した「ｅｅ」という記号列を辞書から探す。

    この場合「ｅｅ」は266番にあるので、それを新しい最長一致系列とし、その参照番号266を記憶する。

    最長一致系列＝ｅｅ：参照番号＝266　　ｐ＝９
  35. 次の記号ｆを読み込み、それを最長一致系列に追加した「ｅｅｆ」という記号列を辞書から探す。

    この場合「ｅｅｆ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｅｅｆ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266ｅｅｅ267ｅｅｅｅ268ｅｅｆ269
    読み込んだ記号＝ｆ
    最長一致系列＝ｅｅ：参照番号＝266　　ｐ＝９
    出力データ：266
    登録語句＝ｅｅｆ：参照番号＝269
  36. 今読み込んだｆをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｆ：参照番号＝102　　ｐ＝９
  37. 次の記号ｆを読み込み、それを最長一致系列に追加した「ｆｆ」という記号列を辞書から探す。

    この場合「ｆｆ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｆｆ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266ｅｅｅ267ｅｅｅｅ268ｅｅｆ269ｆｆ270
    読み込んだ記号＝ｆ
    最長一致系列＝ｆ：参照番号＝102　　ｐ＝９
    出力データ：102
    登録語句＝ｆｆ：参照番号＝270
  38. 今読み込んだｆをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｆ：参照番号＝102　　ｐ＝９
  39. 次の記号ｆを読み込み、それを最長一致系列に追加した「ｆｆ」という記号列を辞書から探す。

    この場合「ｆｆ」は270番にあるので、それを新しい最長一致系列とし、その参照番号270を記憶する。

    最長一致系列＝ｆｆ：参照番号＝270　　ｐ＝９
  40. 次の記号ｆを読み込み、それを最長一致系列に追加した「ｆｆｆ」という記号列を辞書から探す。

    この場合「ｆｆｆ」は辞書にないので、現在の最長一致系列の参照番号を９ビットで符号化して出力し、「ｆｆｆ」を新しい語句として辞書に登録する。

    語句番号語句番号…語句番号
    (0)0(1)1…(255)255
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ａａ256ａｂ257ｂｂ258ｂｃ259ｃｃ260ｃｃｃ261ｃｄ262ｄｄ263
    語句番号語句番号語句番号語句番号語句番号語句番号語句番号語句番号
    ｄｄｄ264ｄｅ265ｅｅ266ｅｅｅ267ｅｅｅｅ268ｅｅｆ269ｆｆ270ｆｆｆ271
    読み込んだ記号＝ｆ
    最長一致系列＝ｆｆ：参照番号＝270　　ｐ＝９
    出力データ：270
    登録語句＝ｆｆｆ：参照番号＝271
  41. 今読み込んだｆをあらためて最長一致系列とし、その参照番号を記憶する。
    最長一致系列＝ｆ：参照番号＝102　　ｐ＝９
  42. これで元データが終了したので、最長一致系系列として残っているｆの参照番号を９ビットで符号化して出力する。
    最長一致系列＝ｆ：参照番号＝102　　ｐ＝９
    出力データ：102

以上の結果、最終的な符号化データは次のようになります。

符号化データ：(97)(97)(98)(98)(99)(260)(99)(100)(263)(100)(101)(266)(267)(266)(102)(270)(102)

これらの符号は全て９ビットで符号化されていますから、全体のビット数は、

17×９＝153ビット

となり、この時の圧縮率と平均符号長は次のようになります。

圧縮率＝153
───
24×8		＝153
──
192		＝0.796875(79.6875％)
平均符号長＝153
──
24		＝6.375ビット

ちなみに同じデータをオリジナルのLZ78符号で符号化しますと、最終的に作成される辞書と符号化データ、そしてその時の圧縮率と平均符号長は以下のようになります。

語句番号語句番号語句番号語句番号語句番号語句番号語句番号
ａ1ａｂ2ｂ3ｃ4ｃｃ5ｃｄ6ｄ7
語句番号語句番号語句番号語句番号語句番号語句番号語句番号
ｄｄ8ｅ9ｅｅ10ｅｅｅ11ｅｅｆ12ｆ13ｆｆ14

符号化データ：ａ1ｂ0ｂ0ｃ4ｃ4ｄ0ｄ7ｄ0ｅ9ｅ10ｅ10ｆ0ｆ13ｆ
全体のビット数：1＋2×2＋4×3＋6×4＋14×8＝153ビット

圧縮率＝153
───
24×8		＝153
──
192		＝0.796875(79.6875％)
平均符号長＝153
──
24		＝6.375ビット

以上のように、このデータ場合、LZW符号とオリジナルのLZ78符号とは全く同じ圧縮率になります。 この圧縮率はLZ77符号よりも悪い値ですが、LZ78符号は元データが多いと圧縮効率が落ちる可能性のあるLZ77の問題点を解決するために考案された手法ですから、このデータのように元データが少ない場合は、LZ77符号よりも圧縮効率が悪くなる傾向があります。

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