4.6 Jones符号の復号化手順

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

1. 元データに付加されている全ての記号の種類と出現頻度情報から、スケールファクターの値と区間の境界値となる累積頻度を求める。 符号化の例として用いたデータですと、次のようになります。
   
   
   a:40　b:30　c:20　d:10　　全記号数＝100
   全記号数と最低出現頻度とEOFを考慮してＮ＝101
2. スケールファクターＮから、Ｎ≦2^wを満足するＮに最も近い２の倍数2^wを求める。
   101≦2⁷＝128　より　w＝7
3. 符号化されたビット列を読み込む。
   ビット列＝010000110010111(＝8599)
4. ビット列の最後にビット１をｗ個追加したものを整数の符号値とする。
   符号値＝0100001100101111111111
5. 整数化した修正区間幅Ｈと修正半開区間の下限Ｌを次のように初期設定する。
   Ｌ＝0　　Ｈ＝2^w＝2⁷＝128
6. 符号値の上位ｗビットを整数値としてＬに代入する。
   Ｌ＝0100001＝33
7. この値から最初の記号の整数符号値Ｆを逆算する。

   Ｆ＝INT{

   Ｎ×(2Ｌ＋1)−1 ─────── 2Ｈ

   }＝INT{

   101×(2×33＋1)−1 ───────── 2×128

   }＝26

8. 元データの区間境界値(累積頻度)より対応する記号を出力する。
   Ｆ＝26　より復元データ：ａ
9. その記号に対応する修正区間の下限Ｆ'_lと上限Ｆ'_u、さらに修正区間幅Ｖを元データの境界値から求める。

   Ｆ'l＝INT(

   Ｆl ── Ｎ

   ×Ｈ＋0.5)＝INT(

   0 ── 101

   ×128＋0.5)＝0

   Ｆ'u＝INT(

   Ｆu ── Ｎ

   ×Ｈ＋0.5)＝INT(

   40 ── 101

   ×128＋0.5)＝51

   Ｖ＝Ｆ'_u−Ｆ'_l＝51−0＝51
10. Ｖを再分割するために、次の条件を満足する２の倍数で置き換える。
    2^w≦Ｖ×2^m＜2^w+1
    2⁷＝128≦51×2²＝204＜2⁸＝256　　m＝2
11. この値からＨ、Ｌを次のように更新する。
    Ｈ←Ｖ×2^m＝51×2²＝204
    Ｌ←(Ｌ−Ｆ'_l)×2^m＝(26−0)×2²＝104
12. 符号値の次の上位ｍビットを整数値としてＬに加算する。
    Ｌ←Ｌ＋10＝104＋2＝106
13. EOFを復号するまで7.から12.を繰り返す。

4.7 Jones符号の復号化実例

例として、符号化の例で用いた「abcd」の符号値「010000110010111」を復号してみましょう。

1. 全記号の種類と出現頻度情報から、スケールファクターの値と区間の境界値となる累積頻度を求める。
   
   
   a:40　b:30　c:20　d:10　　全記号数＝100
   全記号数と最低出現頻度とEOFを考慮してＮ＝101
2. スケールファクターＮ＝101から、101≦2^wを満足する101に最も近い２の倍数2^wを求める。
   101≦2⁷＝128　より　w＝7
3. 符号化されたビット列を読み込む。
   ビット列＝010000110010111(＝8599)
4. ビット列の最後にビット１を７個追加したものを整数の符号値とする。
   符号値＝0100001100101111111111
5. 整数化した修正区間幅Ｈと修正半開区間の下限Ｌを初期設定する。
   Ｌ＝0　　Ｈ＝2^w＝2⁷＝128
6. 符号値の上位７ビットを整数値としてＬに代入する。
   Ｌ＝0100001＝33
7. この値から最初の記号の整数符号値Ｆを逆算する。

   Ｆ＝INT{

   Ｎ×(2Ｌ＋1)−1 ─────── 2Ｈ

   }＝INT{

   101×(2×33＋1)−1 ───────── 2×128

   }

   　　＝26(本来の実数符号値＝0.2614176)
8. 元データの区間境界値より対応する記号ａを出力する。
   復元データ：ａ
9. ａに対応する修正区間の下限Ｆ'_lと上限Ｆ'_u、さらに修正区間幅Ｖを元データの境界値から求める。

   Ｆ'l＝INT(

   Ｆl ── Ｎ

   ×Ｈ＋0.5)＝INT(

   0 ── 101

   ×128＋0.5)＝0

   Ｆ'u＝INT(

   Ｆu ── Ｎ

   ×Ｈ＋0.5)＝INT(

   40 ── 101

   ×128＋0.5)＝51

   Ｖ＝Ｆ'_u−Ｆ'_l＝51−0＝51
10. Ｖを再分割するために、次の条件を満足する２の倍数で置き換える。
    2^w≦Ｖ×2^m＜2^w+1
    2⁷＝128≦51×2²＝204＜2⁸＝256　　m＝2
11. この値からＨ、Ｌを更新する。
    Ｈ←Ｖ×2^m＝51×2²＝204
    Ｌ←(Ｌ−Ｆ'_l)×2^m＝(33−0)×2²＝132
12. 符号値の次の上位２ビットを整数値としてＬに加算する。
    Ｌ←Ｌ＋10＝132＋2＝134
13. Ｌの値から次の記号の整数符号値Ｆを逆算する。

    Ｆ＝INT{

    Ｎ×(2Ｌ＋1)−1 ─────── 2Ｈ

    }＝INT{

    101×(2×134＋1)−1 ────────── 2×204

    }

    　　＝66(本来の実数符号値＝0.6600795)
14. 元データの区間境界値より対応する記号ｂを出力する。
    復元データ：ａｂ
15. 整数符号値からｂの影響を取り除くために9.〜11.の手順を繰り返す。

    Ｆ'l＝INT(

    Ｆl ── Ｎ

    ×Ｈ＋0.5)＝INT(

    40 ── 101

    ×204＋0.5)＝81

    Ｆ'u＝INT(

    Ｆu ── Ｎ

    ×Ｈ＋0.5)＝INT(

    70 ── 101

    ×204＋0.5)＝141

    Ｖ＝Ｆ'_u−Ｆ'_l＝141−81＝60
    2⁷＝128≦60×2²＝240＜2⁸＝256　　m＝2
    Ｈ←Ｖ×2^m＝60×2²＝240
    Ｌ←(Ｌ−Ｆ'_l)×2^m＝(134−81)×2²＝212
16. 符号値の次の上位２ビットを整数値としてＬに加算する。
    Ｌ←Ｌ＋01＝212＋1＝213
17. Ｌの値から次の記号の整数符号値Ｆを逆算する。

    Ｆ＝INT{

    Ｎ×(2Ｌ＋1)−1 ─────── 2Ｈ

    }＝INT{

    101×(2×213＋1)−1 ────────── 2×240

    }

    　　＝89(本来の実数符号値＝0.8889344)
18. 元データの区間境界値より対応する記号ｃを出力する。
    復元データ：ａｂｃ
19. 整数符号値からｃの影響を取り除くために9.〜11.の手順を繰り返す。

    Ｆ'l＝INT(

    Ｆl ── Ｎ

    ×Ｈ＋0.5)＝INT(

    70 ── 101

    ×240＋0.5)＝166

    Ｆ'u＝INT(

    Ｆu ── Ｎ

    ×Ｈ＋0.5)＝INT(

    90 ── 101

    ×240＋0.5)＝214

    Ｖ＝Ｆ'_u−Ｆ'_l＝214−166＝48
    2⁷＝128≦48×2²＝192＜2⁸＝256　　m＝2
    Ｈ←Ｖ×2^m＝48×2²＝192
    Ｌ←(Ｌ−Ｆ'_l)×2^m＝(213−166)×2²＝188
20. 符号値の次の上位２ビットを整数値としてＬに加算する。
    Ｌ←Ｌ＋01＝188＋1＝189
21. Ｌの値から次の記号の整数符号値Ｆを逆算する。

    Ｆ＝INT{

    Ｎ×(2Ｌ＋1)−1 ─────── 2Ｈ

    }＝INT{

    101×(2×188＋1)−1 ────────── 2×192

    }

    　　＝99(本来の実数符号値＝0.9891187)
22. 元データの区間境界値より対応する記号ｄを出力する。
    復元データ：ａｂｃｄ
23. 整数符号値からｄの影響を取り除くために9.〜11.の手順を繰り返す。

    Ｆ'l＝INT(

    Ｆl ── Ｎ

    ×Ｈ＋0.5)＝INT(

    90 ── 101

    ×192＋0.5)＝171

    Ｆ'u＝INT(

    Ｆu ── Ｎ

    ×Ｈ＋0.5)＝INT(

    100 ── 101

    ×192＋0.5)＝190

    Ｖ＝Ｆ'_u−Ｆ'_l＝190−171＝19
    2⁷＝128≦19×2³＝152＜2⁸＝256　　m＝3
    Ｈ←Ｖ×2^m＝19×2³＝152
    Ｌ←(Ｌ−Ｆ'_l)×2^m＝(189−171)×2³＝144
24. 符号値の次の上位３ビットを整数値としてＬに加算する。
    Ｌ←Ｌ＋111＝144＋7＝151
25. Ｌの値から次の記号の整数符号値Ｆを逆算する。

    Ｆ＝INT{

    Ｎ×(2Ｌ＋1)−1 ─────── 2Ｈ

    }＝INT{

    101×(2×151＋1)−1 ────────── 2×152

    }

    　　＝100(本来の実数符号値＝0.9900991)
26. 元データの区間境界値より対応する記号はEOFなので、ここで復号を終了する。
    最終的な復元データ：ａｂｃｄ

4.8 算術符号化の特徴

• どんなデータにも適用可能で汎用性がある。
• 同じ記号がたくさん出てくるデータに特に向いている。
• ２パスで符号化するため圧縮過程が比較的低速。
• 圧縮率はハフマン符号化よりは優れているが、LZ符号化よりは劣る。
• 圧縮／展開方法が複雑なわりに圧縮率が良くないので、実用例はあまり多くない。
• 理論的には非常に優れた手法なので、将来的には高圧縮で実用的な手法を生み出す可能性を持っている。
• 圧縮／展開方法が複雑で理解しにくい……よね？(^^;)

最終更新日：2001年7月2日 　第5節へ 第5章へ

　webmaster@snap-tck.com 　Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)