【第4章　算術符号化(arithmetic coding)】

4.1 算術符号の原理

ハフマン符号では頻繁に出てくる記号は短いビット列で符号化し、あまり出てこない記号は長いビット列で符号化することにより、全体としてデータを圧縮していました。 しかしデータによっては記号が頻繁に出てくるだけでなく、ある特定の記号の組み合わせ、つまり特定の語句が頻繁に出てくることがあります。 その場合、その語句全体を１つの可変長符号で符号化すれば、データをより効率的に圧縮することができるはずです。

例えば前章の「カエルピョコピョコミピョコピョコアワセテピョコピョコムピョコピョコ」について、

と、頻繁に出てくる語句は短いビット列で、たまにしか出てこない語句は長いビット列で符号化すれば、以下のように符号化後のデータのビット長は18ビットとなり、記号ごとに符号化した場合の122ビットよりもかなり短くなります。

この考えをもっと推し進め、元データ全体を１つの語句と考え、１つの可変長符号にしてしまおうという手法が1960年頃にMITのP. Eliasによって提案されました。 その手法は符号化と復号化の過程で算術演算を利用しますので、「算術符号」と呼ばれています。 算術符号では、語句を０から１までの実数区間の１つの点として表すというアイデアを用います。

例えば、元データに含まれる記号とその出現率が以下のようになっていたとします。

この時、０から１までの区間をこれらの出現率で分割し、０以上0.4未満をａに対応する区間、0.4以上0.7未満をｂに対応する区間、0.7以上0.9未満をｃに対応する区間、0.9以上１未満をｄに対応する区間とします。

数学的にはｘ以上ｙ未満の区間を「半開区間」または「一方に閉じた区間」といい、「[x,y)」と書きます。 この時、各記号に対応する区間の下限ｘはその記号の前の記号までの累積出現率となり、上限ｙは下限ｘにその記号の出現率を足したものになっています。 「ａに対応する区間」という意味は、ａから始る語句は全てこの半開区間[0,0.4)上の点として表そうという意味です。 そのための手順として、次はこのａに対応する半開区間[0,0.4)をａからｄまでの出現率で再分割します。

そうしますと、今度は[0,0.16)がａａに対応する半開区間、[0.16,0.28)がａｂに対応する半開区間、[0.28,0.36)がａｃに対応する半開区間、[0.36,0.4)がａｄに対応する半開区間になります。 この時、語句「ａａ」に対応する点は０、「ａｂ」に対応する点は0.16、「ａｃ」に対応する点は0.28、「ａｄ」に対応する点は0.36となります。

このようにして半開区間を次々と分割していきますと、ａ、ｂ、ｃ、ｄの組み合わせでできるあらゆる語句を半開区間[0,1)上の点として表すことが可能になります。 つまり元データを１つの語句と考えますと、それをただ１つの実数で表すことができるわけです。

例として「abcd」というデータを実数化しますと以下のようになります。

1. 最初の記号ａを実数化。
   a＝aの直前の記号までの区間幅を累積した値＝aに対応する半開区間の下限＝0
   区間幅：1×0.4＝0.4　半開区間：[0,0.4)
2. 次の記号ｂよりａｂを実数化。
   ab＝aの値＋aの区間幅×bの直前の記号までの区間幅を累積した値＝0＋0.4×0.4＝0.16
   区間幅：0.4×0.3＝0.12　半開区間：[0.16,0.28)
3. 次の記号ｃよりａｂｃを実数化。
   abc＝abの値＋abの区間幅×cの直前の記号までの区間幅を累積した値＝0.16＋0.12×(0.4＋0.3)＝0.244
   区間幅：0.12×0.2＝0.024　半開区間：[0.244,0.268)
4. 最後の記号ｄよりａｂｃｄを実数化。
   abcd＝abcの値＋abの区間幅×dの直前の記号までの区間幅を累積した値＝0.244＋0.024×(0.4＋0.3＋0.2)＝0.2656
   区間幅：0.024×0.1＝0.0024　半開区間：[0.2656,0.268)

この結果、「abcd」は「0.2656」という値で実数化されます。

こうして符号化された実数値から元の記号を復元するには次のようにします。

1. 0.2656という符号値はａに対応する半開区間[0,0.4)に含まれますので、最初の記号はａのはずです。 そこでまずａを復元します。
   復元データ：「ａ」
2. 次にａの影響を符号値から除去します。 符号化する時はａに対応する半開区間[0,0.4)をａからｄまでの出現率で再分割して、次の記号に対応する半開区間を求めました。 したがってａの影響を符号値から除去するためには、その逆演算を行えばいいことになります。

   ａの影響を除去した符号値＝

   符号値−(ａに対応する点の値) ────────────── ａに対応する半開区間の区間幅

   ＝

   0.2656−0 ───── 0.4

   ＝0.664

3. 新しい符号値0.664は今度はｂに対応する半開区間[0.4,0.7)に含まれますので、次の記号はｂのはずです。 そこでｂを復元します。
   復元データ：「ａｂ」
4. 同様に今度はｂの影響を符号値から除去します。

   ｂの影響を除去した符号値＝

   符号値−(ｂに対応する点の値) ────────────── ｂに対応する半開区間の区間幅

   ＝

   0.664−0.4 ───── 0.3

   ＝0.88

5. 新しい符号値0.88は今度はｃに対応する半開区間[0.7,0.9)に含まれますので、次の記号ｃを復元します。
   復元データ：「ａｂｃ」
6. 次にｃの影響を符号値から除去します。

   ｃの影響を除去した符号値＝

   符号値−(ｃに対応する点の値) ────────────── ｃに対応する半開区間の区間幅

   ＝

   0.88−0.7 ───── 0.2

   ＝0.9

7. 新しい符号値0.9は今度はｄに対応する半開区間[0.9,1)に含まれますので、次の記号ｄを復元します。
   復元データ：「ａｂｃｄ」
8. 次にｄの影響を符号値から除去しますと、

   ｄの影響を除去した符号値＝

   符号値−(ｄに対応する点の値) ────────────── ｄに対応する半開区間の区間幅

   ＝

   0.9−0.9 ───── 0.1

   ＝0

   となり、ここで復号が終了します。

4.2 算術符号の特徴と問題点

算術符号では、記号や語句に対応する半開区間の区間幅はその記号や語句の理論的な出現率に一致しますので、出現率の高い記号や語句の区間幅は広く、出現率の低い記号や語句の区間幅は狭いという特徴があります。

例えば比較的出現率が高いと予想されるａａの区間幅が0.16(半開区間[0,0.16))であるのに対して、出現率が低いと予想されるｄｄの区間幅は0.01(半開区間[0.9.0.91))です。 このことからａａは符号値が０〜0.16の間に入っていれば正確に識別されるのに対して、ｄｄは符号値が0.9〜0.91の間に入っていなければ正確に識別されない、つまりａａを表す符号値は0.08±0.08の誤差が許されるのに対して、ｄｄを表す符号値は0.905±0.005の誤差しか許されないことになります。 したがってａａを表す符号値は比較的精度が低くてもよい、つまりあまり多くの有効桁数が要求されず、少ないビット数で表すことができますが、ｄｄを表す符号値は高い精度が要求され、多くのビット数が必要になります。

その結果、頻繁に出てくる記号や語句は短いビット列で符号化し、あまり出てこない記号や語句は長いビット列で符号化することになり、ハフマン符号の圧縮原理を自然な形で語句にまで拡張していることがわかります。 このため、算術符号はハフマン符号よりも効率的に圧縮することが可能となるはずです。 しかしこの算術符号のアイデアを実際のコンピュータで実現するには、以下のような大きな問題点があります。

1. 復号処理の終了点が判別できない。

   例えば前節の「ａｂｃｄ」の復号過程8.では、ｄの影響を符号値から除去した値が０となりここで復号を終了しました。 しかしこの値はａに対応する半開区間[0,0.4)に含まれますので、次の記号としてａを復元することもできます。 そうしますと、

   ａの影響を除去した符号値＝

   符号値−(ａに対応する点の値) ────────────── ａに対応する半開区間の区間幅

   ＝

   0−0 ─── 0.4

   ＝0

   となり、永遠にａを復号し続けることになってしまいます。

2. 符号値を適当な有効桁数にとどめる方法と、浮動小数点演算を行う時の丸め誤差の影響を取り除く方法を考案する必要がある。

   無限の有効桁数を考えられる数学理論と違い、実際のコンピュータではソフト的にひとつの実数値として扱うことのできるメモリのビット数は有限ですので、有効桁数も有限となります。 このため語句を適当な長さで分割して、符号値を適当な有効桁数にとどめるような工夫が必要です。 その時、実数値を有効桁数に丸める過程でどうしても丸めの誤差が生じますので、その誤差が符号値の判別に影響しないように工夫する必要もあります。

1.の問題点については、

• 元データの最後にデータの終わりを表す特殊な記号「EOF(End-Of-File)」を付加し、このEOF記号が復号されたところで復号処理を終了する。
• 圧縮後のデータに元データの全記号数を保存しておき、その数まで復号したところで復号処理を終了する。

などの簡単な解決法があります。 しかし2.の問題点は厄介で、これがP.C.Pasco、J.Rissanen、C.B.Jonesらによって解決されたのは、算術符号のアイデアが発表されてから実に10年以上たってからでした。

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

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