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

4.4 Jones符号化の手順

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

  1. 元データをスキャンして、全ての記号の種類と出現頻度と全記号数を求める。 例えば、
    a:40　b:30　c:20　d:10　　全記号数＝100
  2. 全記号数と最低出現頻度の値を考慮してスケールファクターＮを決める。
    上記の例では、全記号数が多くないのでそのままスケールファクターの値としてＮ＝100、ただしEOF記号を頻度１として追加するのでＮ＝101とする。
  3. スケールファクターＮ当たりの区間の境界値となる累積頻度を求める。
    Jones符号化
  4. スケールファクターＮからＮ≦2wを満足するＮに最も近い２の倍数2wを求め、これを修正スケールファクターＮ'とする。
    Ｎ＝101≦27＝128＝Ｎ'　より　w＝7
  5. 整数化した修正区間幅Ｈと修正半開区間の下限Ｌ、さらにビットシフト値累積用ｓを次のように初期設定する。
    Ｌ＝0　　Ｈ＝Ｎ'＝2w＝27＝128　　ｓ＝0
  6. 元データから記号を１つ読み込む。
  7. 読み込んだ記号に対応する修正区間の下限Ｆ'lと上限Ｆ'u、さらに修正区間幅Ｖを累積出現頻度Ｆから求める。 例えば入力記号をｂとすると、
    Ｆ'l＝INT(Ｆl
    ──
    Ｎ    		×Ｈ＋0.5)＝INT(40
    ──
    101    		×128＋0.5)＝51
    Ｆ'u＝INT(Ｆu
    ──
    Ｎ    		×Ｈ＋0.5)＝INT(70
    ──
    101    		×128＋0.5)＝89
    Ｖ＝Ｆ'u−Ｆ'l＝89−51＝38
  8. Ｖを再分割するために、次の条件を満足する２の倍数で置き換える。
    Ｈ＝2w≦Ｖ×2m＜2w+1
    27＝128≦38×22＝152＜28＝256　　m＝2
  9. この値からＨ、Ｌ、ｓを次のように更新する。
    Ｈ←Ｖ×2m＝38×22＝152
    Ｌ←(Ｌ＋Ｆ'l)×2m＝(0＋51)×22＝204
    ｓ←ｓ＋ｍ＝0＋2＝2
    修正区間幅Ｈと修正半開区間の下限Ｌから元の実数の値を計算するには、これらを2w+sで割ります。
    区間幅＝Ｈ
    ───
    2w+s    		＝152
    ──
    29    		＝0.296875
    下限＝Ｌ
    ───
    2w+s    		＝204
    ──
    29    		＝0.3984375
    上限＝Ｌ＋Ｈ
    ───
    2w+s    		＝204＋152
    ────
    29    		＝356
    ──
    512    		＝0.6953125
  10. 元のデータが終了するまで手順6.から繰り返す。
  11. 元データの終了を表すEOF記号を同じ手順で符号化する。
  12. 符号値として、ＬをＮ'＝2wで割って整数化した値をｓビットの整数値にして出力する。
    符号値：INT(Ｌ
    ──
    Ｎ'    		)＝INT(Ｌ
    ──
    2w    		)
    この値は、本来の実数の符号値Ｌ／2w+sの小数点以下ｓビットに相当します。 例えばｂの例では次のようになります。
    符号値：INT(Ｌ
    ──
    Ｎ'    		)＝INT(204
    ──
    27    		)＝INT(11001100
    ─────
    10000000    		)＝01
    Ｌ
    ───
    2w+s    		＝204
    ──
    29    		＝0.1100110000×28
    ─────────
    29    		＝0.0110011000

こうして符号化されたデータを復号するためには、元データに含まれる全ての記号の種類と出現頻度、さらにEOFの頻度とスケールファクターＮの値が必要です。 しかしEOF記号の頻度とスケールファクターの値の決定法を統一しておけば、圧縮後のデータに追加するのは元データに含まれる全ての記号の種類と出現頻度だけでよいことになります。 したがって、Jones符号化ではそのぶんが圧縮後のデータのオーバーヘッドとなります。

4.5 Jones符号化の実例

例として、4.1節の例と同じ「abcd」というデータを符号化してみましょう。

  1. 元データをスキャンして、全ての記号の種類と出現頻度と全記号数を求める。 この結果が以下のようになったとします。
    a:40　b:30　c:20　d:10　　全記号数＝100
  2. 最低出現頻度の値からスケールファクターＮを決める。
    全記号数と最低出現頻度とEOFを考慮してＮ＝101
  3. スケールファクターＮ当たりの区間の境界値となる累積頻度を求める。
    Jones符号化
  4. スケールファクターＮ＝101から、101≦2wを満足する101に最も近い２の倍数2wを求め、これを修正スケールファクターＮ'とする。
    Ｎ＝101≦27＝128＝Ｎ'　より　w＝7
  5. 整数化した修正区間幅Ｈと修正半開区間の下限Ｌ、ビットシフト値累積用ｓを初期設定する。
    Ｌ＝0　　Ｈ＝Ｎ'＝2w＝27＝128　　ｓ＝0
  6. 元データから記号ａを読み込む。
  7. 読み込んだ記号ａに対応する修正区間の下限Ｆ'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
  8. Ｖを再分割するために、次の条件を満足する２の倍数で置き換える。
    2w≦Ｖ×2m＜2w+1
    27＝128≦51×22＝204＜28＝256　　m＝2
  9. この値からＨ、Ｌ、ｓを更新する。
    Ｈ←Ｖ×2m＝51×22＝204
    Ｌ←(Ｌ＋Ｆ'l)×2m＝(0＋0)×22＝0
    ｓ←ｓ＋ｍ＝0＋2＝2
    この時の実数の符号値＝0(本来の値＝0)
  10. 元データから次の記号ｂを読み込む。
  11. 記号ｂについて7.〜9.の手順を繰り返す。
    Ｆ'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
    27＝128≦60×22＝240＜28＝256　　m＝2
    Ｈ←Ｖ×2m＝60×22＝240
    Ｌ←(Ｌ＋Ｆ'l)×2m＝(0＋81)×22＝324＝101000100
    ｓ←ｓ＋ｍ＝2＋2＝4
    この時の実数の符号値＝324
    ──
    211    		＝0.1582031(本来の値＝0.1568473)
  12. 元データから次の記号ｃを読み込む。
  13. 記号ｃについて7.〜9.の手順を繰り返す。
    Ｆ'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
    27＝128≦48×22＝192＜28＝256　　m＝2
    Ｈ←Ｖ×2m＝48×22＝192
    Ｌ←(Ｌ＋Ｆ'l)×2m＝(324＋166)×22＝1960＝11110101000
    ｓ←ｓ＋ｍ＝4＋2＝6
    この時の実数の符号値＝1960
    ──
    213    		＝0.2392578(本来の値＝0.2383769)
  14. 元データから次の記号ｄを読み込む。
  15. 記号ｄについて7.〜9.の手順を繰り返す。
    Ｆ'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
    27＝128≦19×23＝152＜28＝256　　m＝3
    Ｈ←Ｖ×2m＝19×23＝152
    Ｌ←(Ｌ＋Ｆ'l)×2m＝(1960＋171)×23＝1960＝100001010011000
    ｓ←ｓ＋ｍ＝6＋3＝9
    この時の実数の符号値＝17048
    ───
    216    		＝0.2601318(本来の値＝0.2591341)
  16. 元データ終了、EOFを符号化するために7.〜9.の手順を繰り返す。
    Ｆ'l＝INT(Ｆl
    ──
    Ｎ    		×Ｈ＋0.5)＝INT(100
    ──
    101    		×152＋0.5)＝150
    Ｆ'u＝INT(Ｆu
    ──
    Ｎ    		×Ｈ＋0.5)＝INT(101
    ──
    101    		×152＋0.5)＝152
    Ｖ＝Ｆ'u−Ｆ'l＝152−150＝2
    27＝128≦2×26＝128＜28＝256　　m＝6
    Ｈ←Ｖ×2m＝19×26＝128
    Ｌ←(Ｌ＋Ｆ'l)×2m＝(17048＋150)×26＝1100672＝100001100101110000000
    ｓ←ｓ＋ｍ＝9＋6＝15
    この時の実数の符号値＝1100672
    ────
    222    		＝0.2624206(本来の値＝0.2614176)
  17. 符号値として、Ｌの値を27で割って整数化した値を15ビットの整数値として出力する。
    符号値：INT(Ｌ
    ──
    2w    		)＝INT(1100672
    ────
    27    		)
    　　＝INT(100001100101110000000
    ────────────
    27    		)＝010000110010111＝8599

同じ記号をハフマン符号化しますと、３章の４節で説明しましたように、

abcd
010110111

と９ビットとなり、EOFの分だけ算術符号の方が長くなります。

３章の５節のハフマン符号の例と同じ「aabbccccddddeeeeeeeeffff」を算術符号化しますと、記号だけで60ビット、EOF記号を含めますと65ビットとなり、やはりEOFの分だけ算術符号の方が長くなります。 これは記号数が少なく語句が短いため、算術符号の利点が生かされないので致し方ないことです。

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