算術符号化

算術符号化( AC ) は、ロスレス データ圧縮で使用されるエントロピー符号化の一種です。通常、文字列はASCIIコードのように、1 文字あたり固定ビット数を使用して表現されます。文字列を算術符号化に変換すると、頻繁に使用される文字はより少ないビット数で格納され、それほど頻繁には使用されない文字はより多くのビット数で格納されるため、合計で使用されるビット数が少なくなります。算術符号化は、入力をコンポーネント シンボルに分割してそれぞれをコードに置き換えるのではなく、メッセージ全体を 1 つの数値、つまり任意精度の分数q (0.0 ≤ q < 1.0) に符号化する点で、ハフマン符号化などの他の形式のエントロピー符号化とは異なります。これは、現在の情報を 2 つの数値で定義される範囲として表します。^[1]非対称数値システムと呼ばれる最近のエントロピー符号化器ファミリでは、現在の情報を表す単一の自然数を直接操作することで、より高速な実装が可能になります。^[2]

最も単純なケースでは、各シンボルの発生確率は等しくなります。たとえば、それぞれ発生確率が等しい 3 つのシンボル A、B、C のセットを考えてみましょう。シンボルを 1 つずつエンコードすると、シンボルごとに 2 ビット必要になりますが、これは無駄です。ビットのバリエーションの 1 つは決して使用されないからです。つまり、シンボル A、B、C はそれぞれ 00、01、10 としてエンコードされ、11 は使用されない可能性があります。

より効率的な解決策は、これらの 3 つのシンボルのシーケンスを、各桁がシンボルを表す基数 3 の有理数として表すことです。たとえば、シーケンス「ABBCAB」は、算術符号化では [0, 1) の区間の値として 0.011201 _{3になります。次の手順では、この}3 進数を、0.0010110001 ₂などの復元できる十分な精度の固定小数点 2 進数を使用してエンコードします。これは 10 ビットのみです。単純なブロック エンコードと比較して 2 ビット節約されます。任意の精度の数値の基数を変換するための効率的なインプレース アルゴリズムがあるため、長いシーケンスでも実行可能です。

値をデコードするには、元の文字列の長さが 6 であることがわかっているので、単純に 3 進数に変換し、6 桁に丸めて文字列を復元するだけです。

一般に、算術符号化器は、任意のシンボルと確率のセットに対して、ほぼ最適な出力を生成できます。(最適値は、確率Pの各シンボルに対して −log ₂ Pビットです。情報源符号化定理を参照してください。)算術符号化を使用する圧縮アルゴリズムは、データのモデルを決定することから始まります。基本的には、メッセージのシンボルにどのようなパターンが見つかるかを予測します。この予測が正確であればあるほど、出力は最適に近づきます。

例: 特定の監視機器の出力を時間の経過に沿って記述する単純な静的モデルは次のようになります。

• シンボルNEUTRALの確率は60%
• シンボルが正になる確率は20%
• シンボルNEGATIVEの確率10%
• シンボル END-OF-DATA の確率は 10% です。(このシンボルが存在するということは、データ圧縮ではよくあることですが、ストリームが「内部的に終了」することを意味します。このシンボルがデータ ストリームに現れると、デコーダーはストリーム全体がデコードされたことを認識します。)

モデルは、この例で選択された単純な 4 つの記号セット以外のアルファベットも処理できます。より高度なモデルも可能です。高次のモデリングでは、記号の現在の確率の推定を、その記号に先行する記号 (コンテキスト)に基づいて変更します。そのため、たとえば英語のテキストのモデルでは、"u" が "Q" または "q" の後に続く場合、その確率ははるかに高くなります。モデルは適応型にすることもでき、ストリームに実際に含まれているものに基づいて、データの予測を継続的に変更します。デコーダーは、エンコーダーと同じモデルを持っている必要があります。

一般に、エンコード プロセスの各ステップは、最後のステップを除いて同じです。エンコーダーが考慮するデータは基本的に 3 つだけです。

• 次にエンコードする必要があるシンボル
• 現在の間隔（エンコード処理の開始時には間隔は[0,1]に設定されますが、変更される可能性があります）
• この段階で考えられるさまざまなシンボルのそれぞれにモデルが割り当てる確率 (前述のように、高次モデルまたは適応型モデルでは、これらの確率は各ステップで必ずしも同じではありません)。

エンコーダーは現在の間隔をサブ間隔に分割します。各サブ間隔は、現在のコンテキストにおけるそのシンボルの確率に比例した現在の間隔の一部を表します。次にエンコードされる実際のシンボルに対応する間隔が、次のステップで使用される間隔になります。

例: 上記の 4 つのシンボル モデルの場合:

• NEUTRALの区間は[0, 0.6)
• POSITIVEの区間は[0.6, 0.8)
• NEGATIVEの区間は[0.8, 0.9)
• END-OF-DATAの間隔は[0.9, 1)になります。

すべてのシンボルがエンコードされると、結果の間隔は、それを生成したシンボルのシーケンスを明確に識別します。使用されている同じ最終間隔とモデルを持っている人は誰でも、その最終間隔を生成するためにエンコーダーに入力されたはずのシンボル シーケンスを再構築できます。

ただし、最終間隔を送信する必要はなく、その間隔内にある1 つの分数を送信するだけで済みます。特に、分数の十分な桁数 (基数に関係なく) を送信して、それらの桁で始まるすべての分数が最終間隔に収まるようにするだけで済みます。これにより、結果のコードがプレフィックス コードになることが保証されます。

与えられた 4 シンボル モデルでエンコードされたメッセージをデコードするプロセスについて考えてみましょう。メッセージは分数 0.538 でエンコードされます (わかりやすくするために 2 進数ではなく 10 進数を使用します。また、メッセージをデコードするために必要な桁数だけあると仮定します)。

このプロセスは、エンコーダーが使用するのと同じ間隔 [0,1) から開始し、同じモデルを使用して、エンコーダーが持つ必要がある同じ 4 つのサブ間隔に分割します。分数 0.538 は NEUTRAL のサブ間隔 [0, 0.6) に該当します。これは、エンコーダーが読み取った最初のシンボルが NEUTRAL であったはずであることを示しており、これがメッセージの最初のシンボルになります。

次に区間[0, 0.6)をサブ区間に分割します。

• NEUTRALの区間は[0, 0.36)、つまり[0, 0.6)の60%になります。
• POSITIVEの区間は[0.36, 0.48)、つまり[0, 0.6)の20%になります。
• NEGATIVEの区間は[0.48, 0.54)、つまり[0, 0.6)の10%になります。
• END-OF-DATAの間隔は[0.54, 0.6)、つまり[0, 0.6)の10%になります。

0.538 は区間 [0.48, 0.54) 内にあるため、メッセージの 2 番目のシンボルは NEGATIVE であったに違いありません。

もう一度、現在の間隔をサブ間隔に分割します。

• NEUTRALの区間は[0.48, 0.516)となる。
• POSITIVEの区間は[0.516, 0.528)になります。
• NEGATIVEの区間は[0.528, 0.534)になります。
• END-OF-DATAの間隔は[0.534, 0.540)になります。

0.538 は END-OF-DATA シンボルの間隔内に収まるため、これが次のシンボルである必要があります。これは内部終了シンボルでもあるため、デコードが完了したことを意味します。ストリームが内部的に終了しない場合は、ストリームが停止する場所を示す別の方法が必要です。そうしないと、デコード プロセスが永久に継続し、実際にエンコードされたよりも多くのシンボルを誤って分数から読み取る可能性があります。

前の例のメッセージ 0.538 は、同様に短い分数 0.534、0.535、0.536、0.537、または 0.539 でエンコードできます。これは、2 進数ではなく 10 進数を使用すると効率が悪くなることを示しています。これは正しいです。3 桁の 10 進数の情報量はビットです。同じメッセージを 8 ビットのコストで 2 進数の分数 0.10001001 (10 進数では 0.53515625 に相当) でエンコードできます。 ${\displaystyle 3\times \log _{2}(10)\approx 9.966}$

この8ビットの出力は、メッセージの 情報量、つまりエントロピーよりも大きい。

∑ − log 2 ⁡ ( p i ) = − log 2 ⁡ ( 0.6 ) − log 2 ⁡ ( 0.1 ) − log 2 ⁡ ( 0.1 ) = 7.381 ビット。{\displaystyle \sum -\log _{2}(p_{i})=-\log _{2}(0.6)-\log _{2}(0.1)-\log _{2}(0.1)=7.381{\text{ ビット}}.}

しかし、バイナリ エンコーディングでは整数ビットを使用する必要があるため、このメッセージのエンコーダーは少なくとも 8 ビットを使用し、結果としてメッセージはエントロピー コンテンツより 8.4% 大きくなります。最大 1 ビットのこの非効率性により、メッセージ サイズが大きくなるにつれてオーバーヘッドが比較的少なくなります。

さらに、主張されているシンボル確率は [0.6、0.2、0.1、0.1) でしたが、この例の実際の頻度は [0.33、0、0.33、0.33) です。間隔がこれらの頻度に合わせて再調整されると、メッセージのエントロピーは 4.755 ビットになり、同じ NEUTRAL NEGATIVE END-OF-DATA メッセージは間隔 [0、1/3)、 [1/9、2/9)、 [5/27、6/27)、およびバイナリ間隔 [0.00101111011、 0.00111000111) としてエンコードできます。これは、特に確率モデルがオフの場合に、算術符号化などの統計符号化方法が入力メッセージよりも大きい出力メッセージを生成する例でもあります。

算術符号化が他の同様のデータ圧縮方法より優れている点の 1 つは、適応の容易さです。適応とは、データの処理中に頻度 (または確率) テーブルを変更することです。デコード時の頻度テーブルがエンコード時と同じ方法と手順で置き換えられる限り、デコードされたデータは元のデータと一致します。同期は通常、エンコードとデコードの処理中に発生するシンボルの組み合わせに基づいて行われます。

上記の算術符号化の説明には、いくつかの簡略化が含まれています。特に、エンコーダが最初に無限精度を使用して区間の端点を表す分数を完全に計算し、エンコードの最後にのみ分数を最終形式に変換するかのように書かれています。ほとんどの算術符号化器は、無限精度をシミュレートするのではなく、デコーダが一致できることがわかっている固定の精度限界で動作し、計算された分数をその精度で最も近い値に丸めます。モデルが区間[0,1)を 3 分の 1 に分割することを要求し、これが 8 ビット精度で近似された場合に、これがどのように機能するかを例で示します。精度がわかっているため、使用できるバイナリ範囲もわかっていることに注意してください。

再正規化と呼ばれるプロセスにより、有限の精度がエンコード可能なシンボルの総数の制限にならないようにしています。範囲が縮小され、範囲内のすべての値が特定の先頭桁を共有するようになった場合は、その桁が出力に送られます。コンピューターが処理できる精度の桁数にかかわらず、処理できる桁数はそれよりも少なくなるため、既存の桁は左にシフトされ、右側に新しい桁が追加されて、範囲を可能な限り広く拡張します。この結果は、前の例の 3 つのケースのうち 2 つで発生することに注意してください。

シンボルの確率が等しい場合、算術符号化は単純に基数または基数を変更することで実装できることを思い出してください。一般に、算術符号化 (および範囲符号化) は基数の一般化された変更として解釈できます。たとえば、次のようなシンボルのシーケンスを見てみましょう。

${\displaystyle \mathrm {DABDDB} }$

関係する記号が順序付けられた集合を形成し、順序付けられた集合内の各記号が連続した整数 A = 0、B = 1、C = 2、D = 3 などを表すと仮定して、特定の基数で数値として表します。これにより、次の頻度と累積頻度が得られます。

項目の累積頻度は、その項目に先行するすべての頻度の合計です。言い換えると、累積頻度は頻度の累計です。

位取り記数法では、基数、つまり底は、数字を表すために使用されるさまざまな記号の数と数値的に等しくなります。たとえば、10 進法では記号の数は 10 で、つまり 0、1、2、3、4、5、6、7、8、9 です。基数は、多項式形式の想定乗数で任意の有限整数を表すために使用されます。たとえば、457 という数字は、実際には 4×10 ²  + 5× 10 ¹  + 7×10 ⁰であり、底は 10 であると想定されていますが、明示的には示されていません。

まず、文字列の長さが 6 なので、DABDDB を 6 進数に変換します。文字列は最初に数字の文字列 301331 にマッピングされ、次に多項式によって整数にマッピングされます。

${\displaystyle 6^{5}\times 3+6^{4}\times 0+6^{3}\times 1+6^{2}\times 3+6^{1}\times 3+6^{0}\times 1=23671}$

結果 23671 の長さは 15 ビットですが、これは理論上の限界 (メッセージの エントロピー) である約 9 ビットにあまり近くありません。

情報理論によって課せられた理論上の限界に近い長さのメッセージをエンコードするには、基数を変更するための従来の公式を少し一般化する必要があります。下限と上限のLとUを計算し、それらの間の数値を選択します。Lを計算するには、上記の式の各項に、以前に発生したすべてのシンボルの頻度の積を掛けます。

${\displaystyle {\begin{aligned}L={}&(6^{5}\times 3)+{}\\&3\times (6^{4}\times 0)+{}\\&(3\times 1)\times (6^{3}\times 1)+{}\\&(3\times 1\times 2)\times (6^{2}\times 3)+{}\\&(3\times 1\times 2\times 3)\times (6^{1}\times 3)+{}\\&(3\times 1\times 2\times 3\times 3)\times (6^{0}\times 1){}\\={}&25002\end{aligned}}}$

この多項式と上記の多項式の違いは、各項に、それ以前に発生したすべてのシンボルの頻度の積が掛けられていることです。より一般的には、L は次のように計算されます。

${\displaystyle L=\sum _{i=1}^{n}n^{ni}C_{i}{\prod _{k=1}^{i-1}f_{k}}}$

ここで、は累積頻度、 は出現頻度です。インデックスはメッセージ内のシンボルの位置を示します。すべての頻度が 1 である特殊なケースでは、これは基数変換式です。 ${\displaystyle \scriptstyle C_{i}}$${\displaystyle \scriptstyle f_{k}}$${\displaystyle \scriptstyle f_{k}}$

上限U はLとすべての周波数の積を足したものになります。この場合、U = L + (3 × 1 × 2 × 3 × 3 × 2) = 25002 + 108 = 25110 となります。一般に、U は次のように求められます。

${\displaystyle U=L+\prod _{k=1}^{n}f_{k}}$

ここで、区間 [ L、U ) から任意の数字を選択してメッセージを表すことができます。便利な選択肢の 1 つは、可能な限り最長のゼロの列を持つ値 25100 です。これにより、結果を 251×10 ²として表すことで圧縮を実現できます。メッセージの長さを別々に保存する場合は、ゼロを切り捨てて 251 にすることもできます。メッセージが長くなると、ゼロの列も長くなる傾向があります。

整数 25100 をデコードするには、次の表に示すように、多項式の計算を逆にすることができます。各段階で現在のシンボルが識別され、対応する項が結果から減算されます。

デコード中は、対応する 6 の累乗で割った後の切り捨て値を取ります。次に、結果を累積間隔と照合し、ルックアップ テーブルから適切なシンボルを選択します。シンボルが識別されると、結果が修正されます。このプロセスは、メッセージの既知の長さの間、または残りの結果が正である間、続行されます。従来の基数変更との唯一の違いは、各シンボルに関連付けられた値の範囲が存在する可能性があることです。この例では、A は常に 0、B は 1 または 2、D は 3、4、5 のいずれかです。これは、頻度によって決定される間隔と正確に一致しています。すべての間隔が 1 に等しい場合、従来の基数変更の特別なケースになります。

下限L はn ^{n を}超えることはない。ここでn はメッセージのサイズであり、ビットで表すことができる。上限Uを計算し、区間 [ L ,  U ) からゼロの連続が最も長い数を選択することによってメッセージを縮小した後、この長さをビット単位で縮小できると推定できる。積の各頻度は、この頻度の値とまったく同じ回数発生するため、アルファベットAのサイズを使用して積を計算すること ができる。${\displaystyle \log _{2}(n^{n})=n\log _{2}(n)}$${\displaystyle \textstyle \log _{2}\left(\prod _{k=1}^{n}f_{k}\right)}$

${\displaystyle \prod _{k=1}^{n}f_{k}=\prod _{k=1}^{A}f_{k}^{f_{k}}.}$

メッセージ内の推定ビット数にlog _{2を適用すると、最終メッセージ (メッセージ長と頻度テーブルの対数オーバーヘッドは考慮しない) は、}エントロピーによって指定されたビット数と一致します。これは、長いメッセージの場合、最適値に非常に近くなります。

${\displaystyle -\left[\sum _{i=1}^{A}f_{i}\log _{2}(f_{i})\right]n=nH}$

言い換えれば、メッセージの長さが無限大に近づくにつれて、算術符号化の効率はシンボルあたりのビットの理論上の限界に近づきます。 ${\displaystyle H}$

これは直感的に理解できます。ソースがエルゴードであると仮定すると、漸近等分割特性(AEP) が存在します。AEP により、長いシンボル ストリームの後、 の区間はほぼ均等なサイズの区間に分割されます。 ${\displaystyle n}$${\displaystyle (0,1)}$

技術的には、任意の小さい に対して、また十分に大きいすべての に対して、各文字列の確率がほぼ等しい文字列が存在し、それらの合計確率は です。 ${\displaystyle \epsilon >0}$${\displaystyle n}$${\displaystyle 2^{nH(X)(1+O(\epsilon ))}}$${\displaystyle x_{1:n}}$${\displaystyle Pr(x_{1:n})=2^{-nH(X)(1+O(\epsilon ))}}$${\displaystyle 1-O(\epsilon )}$

このような文字列はいずれも、長さ のバイナリ文字列によって算術的にエンコードされます。ここで、 は、の区間内に形式の分数が存在する最小の値です。 の区間のサイズは であるため、 のときは、 の区間に 形式の分数が 1 つ含まれると予想されます。 ${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle {\frac {?}{2^{k}}}}$${\displaystyle x_{1:n}}$${\displaystyle x_{1:n}}$${\displaystyle 2^{-nH(X)(1+O(\epsilon ))}}$${\displaystyle {\frac {?}{2^{k}}}}$${\displaystyle k=nH(X)(1+O(\epsilon ))}$

したがって、高い確率で、長さ のバイナリ文字列を使用して算術的にエンコードできます。 ${\displaystyle x_{1:n}}$${\displaystyle nH(X)(1+O(\epsilon ))}$

算術符号化では一度に 1 つのデータを圧縮しないため、IID文字列を圧縮するときにエントロピーに任意に近づくことができます。対照的に、ハフマン符号化の拡張(文字列への) を使用すると、アルファベット記号のすべての確率が 2 の累乗でない限りエントロピーに到達しません。この場合、ハフマン符号化と算術符号化の両方でエントロピーが達成されます。

バイナリ文字列を単純にハフマン符号化すると、たとえエントロピーが低い場合でも（例えば（{0, 1}）の確率が{0.95, 0.05}であるなど）、圧縮は不可能である。ハフマン符号化では、各値に1ビットを割り当て、入力と同じ長さのコードを生成する。対照的に、算術符号化ではビットをうまく圧縮し、最適な圧縮率である

${\displaystyle 1-[-0.95\log _{2}(0.95)+-0.05\log _{2}(0.05)]\approx 71.4\%.}$

ハフマン コーディングの非最適化に対処する簡単な方法の 1 つは、シンボルを連結して (「ブロッキング」)、新しいアルファベットを形成することです。この新しいアルファベットでは、各新しいシンボルが元のアルファベットの元のシンボルのシーケンス (この場合はビット) を表します。上記の例では、エンコード前に 3 つのシンボルのシーケンスをグループ化すると、次の頻度で新しい「スーパー シンボル」が生成されます。

• 000: 85.7%
• 001、010、100: それぞれ4.5%
• 011、101、110: それぞれ0.24%
• 111: 0.0125%

このグループ化により、ハフマン符号化では、元の符号化、つまり圧縮では 1 シンボルあたり 1 ビットであったのに対し、平均して 3 シンボルあたり 1.3 ビット、つまり 1 シンボルあたり 0.433 ビットになります。任意の大きなシーケンスを許可すると、算術符号化と同様にエントロピーに任意の程度近くなりますが、それには膨大なコードが必要になるため、この目的には算術符号化ほど実用的ではありません。 ${\displaystyle 56.7\%}$

代替案としては、ハフマンベースのゴロム・ライス符号 を介してランレングスをエンコードする方法があります。このアプローチでは、算術符号化やハフマン符号化よりも簡単で高速なエンコード/デコードが可能です。ハフマン符号化ではテーブル参照が必要なためです。{0.95, 0.05} の例では、4 ビットの剰余を持つゴロム・ライス符号は の圧縮率を達成し、3 ビットのブロックを使用する場合よりもはるかに最適値に近くなります。ただし、ゴロム・ライス符号はこの例のようなベルヌーイ入力にのみ適用されるため、すべてのケースでブロッキングの代わりになるわけではありません。 ${\displaystyle 71.1\%}$

算術符号化の基本アルゴリズムは、IBMリサーチのヨルマ・J・リッサネンとスタンフォード大学の博士課程の学生リチャード・C・パスコによって独立して開発され、どちらも1976年5月に出版された。パスコはリッサネンの論文の出版前の草稿を引用し、彼らの研究の関係についてコメントしている。^[3]

このアルゴリズム群の 1 つは、Rissanen [1976] によって独自に開発されました。このアルゴリズムは、加算と累乗によって得られたポインタを使用して、コード要素をアキュムレータの最上位端にシフトします。ここで、3 つの選択肢を比較し、アキュムレータではなくコード要素をシフトし、コード要素をアキュムレータの最下位端に追加する方が望ましいことがわかります。

発表から1年も経たないうちに、IBMはリッサネン氏の研究について米国特許を申請した。パスコ氏の研究は特許を取得できなかった。

算術符号化のさまざまな特定の技術は、歴史的に米国特許で保護されてきましたが、特許の有効期限が切れると、さまざまなよく知られた方法がパブリック ドメインになりました。特許で保護されている技術は、一部の正式な国際標準で指定されている算術符号化のアルゴリズムを実装するために不可欠な場合があります。この場合、そのような特許は一般に、「合理的かつ非差別的」( RAND ) ライセンス条件 (少なくとも標準委員会のポリシーでは) の下でライセンス供与されます。よく知られているいくつかの例 (期限切れになった IBM 特許を含む) では、そのようなライセンスは無料で利用できましたが、他の例ではライセンス料が必要でした。RAND 条件の下でライセンスが利用可能であることは、その技術を使用したいすべての人を必ずしも満足させるものではありません。なぜなら、プロプライエタリな商用ソフトウェア製品を用意している企業にとって「合理的」と思われるものが、フリー ソフトウェアまたはオープン ソースプロジェクトにとってはあまり合理的ではないと思われる場合があるからです。

少なくとも 1 つの重要な圧縮ソフトウェア プログラムであるbzip2 は、当時の特許状況を理由に、算術符号化の使用を意図的に中止し、ハフマン符号化を採用しました。また、ハフマン符号化と算術符号化の両方のオプションがあるJPEGファイル形式のエンコーダとデコーダは、もともと特許上の懸念から、通常ハフマン符号化オプションのみをサポートしています。その結果、現在使用されているほぼすべての JPEG 画像はハフマン符号化を使用しています^[4]が、JPEG の算術符号化の特許^[5]は JPEG 標準の古さ (設計は 1990 年までにほぼ完了) により失効しています。^[6] JPEG XLや PackJPG、Brunsli、Lepton などのアーカイバは、ハフマン符号化されたファイルを算術符号化 (JPEG XL の場合は非対称数値システム) のファイルに可逆変換し、最大 25% のサイズを節約できます。

JPEG画像圧縮形式の算術符号化アルゴリズムは、以下の引用特許（期限切れ）に基づいています。^[7]

• 米国特許 4,652,856 – ( IBM ) 1986 年 2 月 4 日に出願、1987 年 3 月 24 日に付与 – Kottappuram MA Mohiuddin、Jorma Johannes Rissanen – 乗算のない複数アルファベットの算術コード
• 米国特許 4,905,297 – (IBM) 1988 年 11 月 18 日出願、1990 年 2 月 27 日付与 – Glen George Langdon、Joan L. Mitchell、William B. Pennebaker、Jorma Johannes Rissanen – 算術符号化エンコーダおよびデコーダ システム
• 米国特許 4,935,882 – (IBM) 1988 年 7 月 20 日出願、1990 年 6 月 19 日付与 – William B. Pennebaker、Joan L. Mitchell – 算術符号化器の確率適応
• JP 特許 1021672 – (三菱) 1989 年 1 月 21 日に出願、1990 年 8 月 10 日に付与 – 木村敏弘、木野重典、小野文隆、吉田正幸 – コーディングシステム
• JP 特許 2-46275 – (三菱) 1990 年 2 月 26 日に出願、1991 年 11 月 5 日に付与 – 小野文隆、木村知宏、吉田正幸、木野重典 – 符号化装置および符号化方法

算術符号化に関連するその他の特許（ほとんどが期限切れ）には、次のものがあります。

• 米国特許 4,122,440 – (IBM) 1977 年 3 月 4 日出願、1978 年 10 月 24 日付与 – Glen George Langdon、Jorma Johannes Rissanen – 算術文字列コーディングの方法と手段
• 米国特許 4,286,256 – (IBM) 1979年11月28日出願、1981年8月25日付与 – Glen George Langdon、Jorma Johannes Rissanen – 演算回数を減らした算術符号化の方法と手段
• 米国特許 4,467,317 – (IBM) 1981 年 3 月 30 日出願、1984 年 8 月 21 日付与 – Glen George Langdon、Jorma Johannes Rissanen – 同時値更新を使用した高速算術圧縮コーディング
• 米国特許 4,891,643 – (IBM) 1986 年 9 月 15 日出願、1990 年 1 月 2 日付与 – Joan L. Mitchell、William B. Pennebaker – 選択的に採用された多様な算術符号化エンコーダとデコーダによる算術符号化データ圧縮/解凍
• JP 特許 11782787 – ( NEC ) 1987 年 5 月 13 日出願、1988 年 11 月 18 日付与 – 島田 道雄 – データ圧縮算術符号化装置
• JP 特許 15015487 – ( KDDI ) 1987 年 6 月 18 日出願、1988 年 12 月 22 日付与 – 松本 修一、斉藤 正弘 – 算術符号化における桁上がり伝播を防止するシステム
• 米国特許 4,933,883 – (IBM) 1988 年 5 月 3 日出願、1990 年 6 月 12 日付与 – William B. Pennebaker、Joan L. Mitchell – 算術符号化器の確率適応
• 米国特許 4,989,000 – (IBM) 1989 年 6 月 19 日出願、1991 年 1 月 29 日付与 – Dan S. Chevion、Ehud D. Karnin、Eugeniusz Walach – 簡易確率部分区間推定による算術符号化を使用したデータ文字列圧縮
• 米国特許 5,099,440 – (IBM) 1990 年 1 月 5 日出願、1992 年 3 月 24 日付与 – William B. Pennebaker、Joan L. Mitchell – 算術符号化器の確率適応
• 米国特許 5,272,478 – (リコー) 1992 年 8 月 17 日出願、1993 年 12 月 21 日付与 – ジェームズ D. アレン – エントロピー符号化の方法および装置

注: このリストは網羅的なものではありません。その他の米国特許のリストについては、次のリンクを参照してください。^[8] Diracコーデックは算術符号化を使用しており、特許出願中ではありません。^[9]

算術符号化に関する特許は他の管轄区域に存在する可能性があります。世界中のソフトウェアの特許性に関する議論については、 ソフトウェア特許を参照してください。

算術符号化のプログラム実装ごとに、圧縮率とパフォーマンスが異なります。圧縮率のばらつきはわずかですが (通常は 1% 未満)、^[10]コード実行時間は 10 倍も変わることがあります。公開されているエンコーダーのリストから適切なエンコーダーを選択するのは簡単なことではありません。パフォーマンスと圧縮率はデータのタイプ、特にアルファベットのサイズ (異なる記号の数) によっても左右されるからです。2 つのエンコーダーのうちの 1 つは小さいアルファベットでパフォーマンスが良く、もう 1 つは大きいアルファベットでパフォーマンスが良い場合があります。ほとんどのエンコーダーはアルファベットのサイズに制限があり、その多くは 2 つの記号 (0 と 1) のアルファベットに特化しています。

• 非対称の数字体系
• コンテキスト適応型バイナリ算術符号化(CABAC)
• データ圧縮
• エントロピー符号化
• ハフマン符号化
• 範囲エンコーディング
• ランレングス符号化

• MacKay, David JC (2003 年 9 月)。「第 6 章: ストリーム コード」。情報理論、推論、学習アルゴリズム。ケンブリッジ大学出版局。ISBN 0-521-64298-1. 2007年12月22日時点のオリジナル（PDF/ PostScript / DjVu / LaTeX）からアーカイブ。2007年12月30日閲覧。
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)。「セクション 22.6. 算術コーディング」。数値レシピ: 科学計算の技術(第 3 版)。ニューヨーク: Cambridge University Press。ISBN 978-0-521-88068-8. 2011年8月11日時点のオリジナルよりアーカイブ。2011年8月18日閲覧。
• Rissanen, Jorma ( 1976年5 月)。「一般化クラフト不等式と算術符号化」。IBM Journal of Research and Development。20 ( 3): 198–203。doi :10.1147/rd.203.0198。2007年9 月 21 日閲覧。
• Rissanen , JJ; Langdon GG, Jr (1979 年 3 月)。「算術コーディング」(PDF)。IBM Journal of Research and Development。23 ( 2): 149–162。doi :10.1147/rd.232.0149。S2CID 39909636。2007年 9 月 28 日の オリジナル(PDF)からアーカイブ。2007 年9月22 日閲覧。
• Witten, Ian H.; Neal, Radford M.; Cleary , John G. (1987 年 6 月)。「データ圧縮のための算術符号化」(PDF)。Communications of the ACM。30 ( 6): 520–540。doi : 10.1145 /214762.214771。S2CID 3343393。2007年 9 月 28 日のオリジナルから アーカイブ(PDF) 。2007年9 月 21 日に取得。

• ロディオノフ アナトリー、ボルコフ セルゲイ (2010)「p 進算術符号化」Contemporary Mathematics Volume 508、2010 Contemporary Mathematics
• ロディオノフ アナトリー、ボルコフ セルゲイ (2007)「p 進算術符号化」、P 進算術符号化

•  この記事には、 Paul E. Blackのパブリック ドメイン資料が組み込まれています。「算術コーディング」。アルゴリズムとデータ構造の辞書。NIST 。
• 算術エンコード (整数のみ) の簡単な実例を記載したニュースグループ投稿。
• 算術符号化に関する PlanetMath の記事
• 範囲エンコーダーの構造 この記事では、範囲コーディングと算術コーディングの両方について説明します。また、3 つの異なる算術エンコーダーのコード サンプルとパフォーマンス比較も掲載されています。
• 算術符号化入門 2020年11月9日にWayback Machineにアーカイブされました。60ページ。
• Eric Bodden、Malte Clasen、Joachim Kneis: 算術符号化の解明。技術レポート 2007-5、Sable Research Group、マギル大学。
• 算術コーディング + 統計モデリング = データ圧縮 (Mark Nelson 著)。
• 算術符号化によるデータ圧縮 (Mark Nelson 著、2014 年)
• James K. Bonfield による範囲コーディングと rANS の高速実装