算術符号

算術符号：効率的なデータ圧縮技術とその歴史

算術符号は、データの出現確率に基づいて符号を割り当てるエントロピー[[符号]]化方式です。1960年代にその原型が提案され、1970年代後半にはIBMの研究者らによって完成しました。データ圧縮において高い効率性を誇る一方、特許問題という複雑な歴史も持ち合わせています。

符号化の仕組み

算術符号は、データの各要素に、その出現確率に応じて連続した区間を割り当てます。例えば、3つのデータA、B、Cの出現確率がそれぞれ0.5、0.3、0.2だとすると、[0, 0.5)、[0.5, 0.8)、[0.8, 1)という区間が割り当てられます。複数のデータからなる系列を符号化する場合には、これらの区間を順次分割することで、系列全体に対応する区間を決定し、その区間内の数値を符号として用います。

この手法は、各データの出現確率を事前に把握する必要がある点が特徴です。しかし、出現確率が未知の場合でも適用できる適応型算術符号も存在します。算術符号はJPEG 2000など、様々なデータ圧縮技術に利用され、その効率性を実証しています。JPEG 2000では、MQ-coderという改良型の算術符号が採用されています。

特許問題：普及を阻む壁

データ圧縮技術を取り巻く特許問題は深刻であり、算術符号もその例外ではありません。 かつては、「抜け道がないほど特許が取得されている」と言われるほど、多くの特許に覆われていました。このため、bzipのような圧縮ソフトウェアでは算術符号の採用を断念し、代わりにハフマン[[符号]]が使用されたり、特許を回避したRange Coderが開発されたりと、技術開発に大きな影響を与えました。 多くの開発者にとって、算術符号は「特許の壁」として認識されていたのです。

しかし、算術符号が必ずしも特許に抵触するわけではないという意見もあります。ある画像フォーマット開発者は、算術符号の実装における処理速度、無限復号の問題、有限桁数のコンピュータでの演算打ち切りといった課題への解決策が特許申請の対象であり、これらの課題を独自の方法で解決していれば特許に抵触しない、という立場をとっています。実際、同氏は自身の開発した画像圧縮技術で算術符号を用いており、特許回避に成功していることを示しています。

算術符号の種類

算術符号は、実装アルゴリズムによって様々な種類が存在します。主なものとしては、L-R型算術符号、Q-coder、MQ-coder、Jones符号（Range Coderの原型）、i.i.d算術符号などがあります。これらは、それぞれ異なる特徴を持ち、用途に応じて使い分けられています。

関連技術

算術符号は、符号理論というより広い分野に属し、シャノン[[符号化]]、ハフマン[[符号]]、数え上げ符号といった他の符号化方式と関連しています。また、Range Coderや、当初算術符号を採用予定だったが特許問題によりハフマン[[符号]]に切り替えられたbzip2、特定の符号化方法の場合に算術符号を用いるH.264なども、算術符号と関連性の深い技術です。

まとめ

算術符号は、高い圧縮効率を持つデータ圧縮技術ですが、特許問題という大きな課題がありました。近年では、特許の回避方法や特許状況の変化もあり、その利用は広がりつつあります。 様々な種類が存在し、用途に応じて最適なアルゴリズムを選択することが重要です。

もう一度検索