算術符号のアイデアを用いた符号は色々あり、中にはアルゴリズムが公開されていないものもあります。 それらのうち、比較的簡単でかつ洗練されたものにJones符号があります。 Jones符号はオーストラリアの情報科学研究者C.B.Jonesによって、1981年に開発された算術符号です。 この符号では浮動小数点演算による丸めの誤差を避けるために、符号値を整数化し、符号化と復号化における演算処理を全て整数演算で行います。 符号値を整数化するために、まず元データに含まれる記号の出現率を出現頻度に置き換えます。
例えば4.1節の例で、元データに含まれる記号の出現頻度が、
となっていたとしますと、それぞれの記号に対応する半開区間は下図のように整数化されます。
この時、各記号に対応する半開区間の下限は、その記号の前の記号までの累積頻度となり、上限は下限にその記号の出現頻度を足したものになっています。 そしてこの整数化された半開区間を全記号数100で割りますと、本来の実数の半開区間になります。
次にａに対応する半開区間[0,40)をａからｄまでの出現率で再分割するわけですが、まともに再分割しますと、当然、整数ではなくなってしまいます。 そこで、半開区間[0,40)をまた[0,100)と置き直して再分割します。 この時、ａａ〜ａｄに対応する半開区間に変換率40/100をかけ、さらに全記号数100で割りますと本来の実数の半開区間になります。
このように、再分割を行うたびに分割する半開区間を全体の半開区間に置きなおし、その時の変換率を求めることにしておけば、理論的には全ての符号値を整数で表し、その値に変換率をかけて全記号数で割ることによって、本来の実数の符号値を計算することができるはずです。 しかしこの直接的な方法では、元データの記号数が多いと、変換率の計算や符号値の計算の時、数字の桁数が非常に大きくなってしまい効率的ではありません。
そこで全記号数の代わりに「スケールファクター」と呼ばれる仮の母数Ｎを導入し、各記号の出現頻度を全記号数がＮ個だった時の出現頻度に変換します。 スケールファクターＮは最低出現頻度の変換後の出現頻度が１以上になるだけの大きさがあれば、つまり(全記号数／最低出現頻度)以上の大きさがあれば符号値の計算に利用することができます。 例えば前述の例では、Ｎ＝100／10＝10の時、最低出現頻度であるｄの変換後の出現頻度が１となり、符号値を計算することが可能になります。
通常、元データは８ビットの固定長符号ですから、各記号がランダムに出現するとすれば平均出現率は1／256、つまりスケールファクターＮ＝256程度で良いことになります。 しかし実際には各記号の出現頻度にバラツキがありますので、余裕をみてＮ＝1000〜10000程度が比較的よく用いられるようです。 ここでは全記号数が多くありませんので、全記号数をそのままスケールファクターの値にし、Ｎ＝100とすることにします。
ところがコンピュータ演算は普通は２進法で行いますので、スケールファクターの値によっては、本来の実数の符号値を計算する時に丸めの誤差が入ってしまうことがあります。 そこでスケールファクターの値Ｎから、
を満足するＮに最も近い２の倍数2wを求めて、この値を修正スケールファクターＮ'とし、それを用いて符号値を計算することにします。 例えばＮ＝100としますと、次のようになります。
この時、各記号の整数化した半開区間の境界値、つまりスケールファクターＮ当たりの各記号の累積頻度をＦとしますと、修正スケールファクターＮ'当たりの修正累積頻度Ｆ'は、
| Ｆ'＝INT( | Ｆ ── Ｎ | ＋0.5)＝INT( | Ｆ ── 100 | ×128＋0.5) |
となります。
頻度を四捨五入によって整数化しますと丸めの誤差が入りますが、この場合、修正頻度Ｆ'は必ず元の頻度よりも大きくなりますので、誤差は有効桁数以下の部分に入ることになり、復号化には差し支えありません。 この結果、各記号に対応する修正半開区間は下図のようになります。
この時、実数の符号値はＦ'／Ｎ'より、
| 51 ── 128 | ＝0.398475 | 90 ── 128 | ＝0.703125 | 115 ── 128 | ＝0.8984375 |
となり、本来の値とほんの少し異なることになりますが、その差異は有効桁数以下の部分で生じますので、やはり復号化には差し支えありません。
修正頻度Ｆ'をＮ'＝２wで割るということは、２進法を用いるコンピュータ演算においては、２進数表現されたＦ'をｗビットだけ右にシフトすることを意味します。 例えば、上記の51／128を２進法で計算しますと次のようになります。
| 51 ── 27 | ＝ | 110011 ──── 1000000 | ＝0.0110011 |
またＦ'を仮数部(w＋1)ビットの浮動小数点形式で表しますと、
| 51 ── 27 | ＝ | 0.11001100×26 ──────── 27 | ＝0.11001100×2-1＝0.01100110 |
となり、仮数部はそのままで指数部だけｗ減少します。 したがって２進法で計算した場合、Ｆ'をＮ'で割っても丸めの誤差は入らず、有効桁数は変わらないことになります。
次にａに対応する修正半開区間[0,51)を再分割する場合も、この区間幅をスケールファクターＮに最も近い２の倍数に置き換えて再分割します。 ただしその値は、区間幅を約数として含んでいないと丸めの誤差が入る可能性がありますし、2wよりも小さな値ですと、再分割した場合の符号値が桁落ちして有効桁数が少なくなってしまいます。 またあまり大きくしすぎますと、符号値のビット数が多くなり効率的ではありません。 そこで、次のような条件を満足する値を選びます。
今の例ですと、
となり、この値Ｈ'＝204が再分割の時の修正スケールファクター相当の値になります。
Ｈから実数の区間幅を求めるにはＨをＮで割りますが、Ｈ'はＨを2m倍した値ですから、Ｈ'から実数の区間幅を求めるにはＨ'をＮ'×2m＝2w×2m＝2w+m＝29で割ることになります。
この時、実数の符号値はＦ'／2w+mより次のようになります。
| 82 ── 512 | ＝0.1601562 | 143 ── 512 | ＝0.2792968 | 184 ── 512 | ＝0.359375 | 204 ── 512 | ＝0.3985375 |
この場合はＦ'を仮数部(w＋m＋1)桁の浮動小数点形式で表し、仮数部はそのままで、指数部だけ2w+m減少することに対応しますから、Ｆ'のビット長をｍ個増やせば、2w+mで割っても丸めの誤差は入らないことになります。
| 82 ── 512 | ＝ | 0.1010010000×27 ───────── 29 | ＝0.1010010000×2-2＝0.0010100100 |
つまりｗは符号値の基本ビット数を規定する値であり、再分割をするたびに符号値の符号長がｍビットだけ長くなります。 その際、
という条件より、区間幅Ｈが小さいほどｍが大きくなり、符号値の増加ビット数が多くなります。 区間幅は対応する記号または語句の出現率に比例しますから、このことは出現率の大きな語句は短いビット列で符号化し、出現率の小さな語句は長いビット列で符号化することを意味します。 これは一種の正規化演算になっており、この方法を用いている限り、いくら演算を繰り返しても丸めの誤差が入らず、再分割を行うのに十分な精度が保証されることがJonesによって証明されています。 これがJonesによる前節の問題点2.の解決策です。
第4節へ
webmaster@snap-tck.com
Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)