算術符号

算術符号 (さんじゅつふごう) とは、1960年頃にマサチューセッツ工科大学のP. 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にも採用されている。ただし、基本的なアルゴリズムの特許はIBM等の企業がおさえており、RANDライセンス条件で提供されている。

関連項目

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