算術符号（さんじゅつふごう、Arithmetic coding）とは、1960年頃にマサチューセッツ工科大学のP. Eliasによって原型が提案され、1970年代後半にIBMのRissanenや、Pascoによって完成された符号。エントロピー符号の一つ。コンパクト符号とは限らない[1]。
符号化の原理

たとえば、データ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点の何れかを解決する手法が特許申請の範囲であり、これらに抵触しなければ問題ないという。実際に同氏の画像圧縮処理には算術符号が用いられており、それは独自の手法により問題点を解決することで特許に抵触していないという考えを明らかにしている[2]。
種類

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

L-R型算術符号

Q-coder

MQ-coder



Jones符号 - Range Coderの原型となった。

i.i.d算術符号

参考文献^ 今井秀樹『情報理論』昭晃堂、80頁
^ ⇒情報圧縮と特許 - ERI画像フォーマット開発者による、圧縮技術に対する特許についての考察

関連項目

符号理論

シャノン符号化

ハフマン符号

数え上げ符号

Range Coder

bzip2 - 当初算術符号を用いる「bzip」として開発されたが、特許のために断念された。bzip2は代わりにハフマン符号を用いている。

H.264 - CABACでの符号化を行った場合のみ。

表

話

編

歴
データ圧縮方式
可逆

エントロピー符号

一進法

算術

Asymmetric numeral systems（英語版）

ゴロム

ハフマン

適応型（英語版）

正準（英語版）

MH


レンジ

シャノン

シャノン・ファノ

シャノン・ファノ・イライアス（英語版）

タンストール（英語版）

ユニバーサル（英語版）

指数ゴロム（英語版）

フィボナッチ（英語版）

ガンマ

レーベンシュタイン（英語版）


辞書式（英語版）

BPE

Deflate

Lempel-Ziv

LZ77

LZ78

LZFSE

LZH

LZJB（英語版）

LZMA

LZO

LZRW（英語版）

LZS（英語版）

LZSS

LZW

LZWL（英語版）

LZX

LZ4

ROLZ（英語版）

統計型（英語版）

Brotli

Snappy

Zstandard


その他

BWT

CTW（英語版）

Delta

DMC（英語版）

MTF

PAQ

PPM