算術符号のソースを表示

'''算術符号'''（さんじゅつふごう、{{Lang|en|Arithmetic coding}}）とは、1960年頃に[[マサチューセッツ工科大学]]のP. Eliasによって原型が提案され、1970年代後半に[[IBM]]のRissanenや、Pascoによって完成された[[符号]]。[[エントロピー符号]]の一つ。[[コンパクト符号]]とは限らない<ref>[[今井秀樹]]『情報理論』[[明晃社]]、80頁</ref>。

== 符号化の原理 ==
たとえば、[[データ]]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年時点で期限切れ）など、データ圧縮の分野においても特許問題は尽きない。算術符号もそのひとつである。

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

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

== 種類 ==
算術符号には実装アルゴリズムによっていくつもの種類が存在している。
* L-R型算術符号
** Q-coder
*** MQ-coder
* Jones符号 - [[Range Coder]]の原型となった。
* i.i.d算術符号

== 参考文献 ==
<references />

== 関連項目 ==
* [[符号理論]]
* [[シャノン符号化]]
* [[ハフマン符号]]
* [[数え上げ符号]]
* [[Range Coder]]
* [[bzip2]] - 当初算術符号を用いる「bzip」として開発されたが、特許のために断念された。bzip2は代わりにハフマン符号を用いている。

{{データ圧縮}}

{{DEFAULTSORT:さんしゆつふこう}}
[[Category:データ圧縮]]