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

4.4 Jones符号化の手順

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

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

    ───
    2w+s
    204
    ──
    29
    0.1100110000×28
    ─────────
    29
    =0.0110011000

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

4.5 Jones符号化の実例

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

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

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

abcd
010110111

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

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