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

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

4.1 算術符号の原理

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

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

ピョコピョコ:0 カエル:10 ミ:1100 アワセテ:1101 ム:1110

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

カエルピョコピョコピョコピョコアワセテピョコピョコピョコピョコ
100110001101011100

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

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

a:0.4 b:0.3 c:0.2 d:0.1

この時、0から1までの区間をこれらの出現率で分割し、0以上0.4未満をaに対応する区間、0.4以上0.7未満をbに対応する区間、0.7以上0.9未満をcに対応する区間、0.9以上1未満をdに対応する区間とします。

算術符号化の原理1

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

算術符号化の原理2

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

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

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

  1. 最初の記号aを実数化。
    a=aの直前の記号までの区間幅を累積した値=aに対応する半開区間の下限=0
    区間幅:1×0.4=0.4 半開区間:[0,0.4)
  2. 次の記号bよりabを実数化。
    ab=aの値+aの区間幅×bの直前の記号までの区間幅を累積した値=0+0.4×0.4=0.16
    区間幅:0.4×0.3=0.12 半開区間:[0.16,0.28)
  3. 次の記号cよりabcを実数化。
    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. 最後の記号dよりabcdを実数化。
    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という符号値はaに対応する半開区間[0,0.4)に含まれますので、最初の記号はaのはずです。 そこでまずaを復元します。
    復元データ:「a」
  2. 次にaの影響を符号値から除去します。 符号化する時はaに対応する半開区間[0,0.4)をaからdまでの出現率で再分割して、次の記号に対応する半開区間を求めました。 したがってaの影響を符号値から除去するためには、その逆演算を行えばいいことになります。
    aの影響を除去した符号値=符号値−(aに対応する点の値)
    ──────────────
    aに対応する半開区間の区間幅
      =0.2656−0
    ─────
    0.4
    =0.664
  3. 新しい符号値0.664は今度はbに対応する半開区間[0.4,0.7)に含まれますので、次の記号はbのはずです。 そこでbを復元します。
    復元データ:「ab」
  4. 同様に今度はbの影響を符号値から除去します。
    bの影響を除去した符号値=符号値−(bに対応する点の値)
    ──────────────
    bに対応する半開区間の区間幅
      =0.664−0.4
    ─────
    0.3
    =0.88
  5. 新しい符号値0.88は今度はcに対応する半開区間[0.7,0.9)に含まれますので、次の記号cを復元します。
    復元データ:「abc」
  6. 次にcの影響を符号値から除去します。
    cの影響を除去した符号値=符号値−(cに対応する点の値)
    ──────────────
    cに対応する半開区間の区間幅
      =0.88−0.7
    ─────
    0.2
    =0.9
  7. 新しい符号値0.9は今度はdに対応する半開区間[0.9,1)に含まれますので、次の記号dを復元します。
    復元データ:「abcd」
  8. 次にdの影響を符号値から除去しますと、
    dの影響を除去した符号値=符号値−(dに対応する点の値)
    ──────────────
    dに対応する半開区間の区間幅
      =0.9−0.9
    ─────
    0.1
    =0
    となり、ここで復号が終了します。

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

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

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

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

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

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

    aの影響を除去した符号値=符号値−(aに対応する点の値)
    ──────────────
    aに対応する半開区間の区間幅
      =0−0
    ───
    0.4
    =0

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

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

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

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

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