算術符号

Eliasによって原型が提案され、1970年代後半にIBMのRissanenや、Pascoによって完成された符号。エントロピー符号の一つ。コンパクト符号とは限らない。

たとえば、データA, B, Cがそれぞれ0.5, 0.3, 0.2の確率で出現するとき、それぞれ半開区間 [0, 0.5), [0.5, 0.8), [0.8, 1) に割り当てる。次に、AA, AB, ACについては、半開区間 [0, 0.25), [0.25, 0.4), [0.4, 0.5) に割り当てる。この手順を繰り返して、符号化したいデータの系列について、対応する半開区間を求める。そして、その半開区間内の値で符号化する。

符号化の原理上、全てのデータの出現確率をあらかじめ知っておく必要があるが、出現確率がわからなくても符号化できる適応化算術符号も知られている。

この符号化は、データ圧縮向きで、JPEG 2000にも、別のアルゴリズムで実装されたQ-coderの改良型、MQ-coderとして採用されている。

インターネットで爆発的に普及した、GIF画像ファイルフォーマットの圧縮アルゴリズムがLZW符号の特許料の支払を命じられた（2004年時点で期限切れ）など、データ圧縮の分野においても特許問題は尽きない。算術符号もそのひとつである。

特に算術符号においては「抜け道がないくらいに特許が取られている」などといわれ、bzipでは公開を断念、JPEG 2000が使用を開始するまではハフマン符号で代用したり、あげくは「特許に抵触しない算術符号」としてRange Coderが普及する有り様である。無論まったく使われなかったわけではないが、圧縮技術に興味を持ったり圧縮／復号ツールを開発する者の間では「特許のせいで使うことはできない」と言われ続けているのが現状である。

そのような中、ERI画像フォーマット開発者は異を唱える。氏の文献を引用すると、算術符号はどうしても処理が遅くなってしまう点と復号時に無限に復号を続けてしまう点、コンピュータが有限桁で動いている一方で算術符号は無限桁であり、どこかで演算を打ち切らなければならない点の3点の何れかを解決する手法が特許申請の範囲であり、これらに抵触しなければ問題ないという。実際に同氏の画像圧縮処理には算術符号が用いられており、それは独自の手法により問題点を解決することで特許に抵触していないという考えを明らかにしている。

算術符号には実装アルゴリズムによっていくつもの種類が存在している。

• L-R型算術符号
  • Q-coder
    • MQ-coder
• Jones符号 - Range Coderの原型となった。
• i.i.d算術符号

• 符号理論
• シャノン符号化
• ハフマン符号
• 数え上げ符号
• Range Coder
• bzip2 - 当初算術符号を用いる「bzip」として開発されたが、特許のために断念された。bzip2は代わりにハフマン符号を用いている。
• H.264 - CABACでの符号化を行った場合のみ。