算術符号化

算術符号化( AC ) は、ロスレスデータ圧縮で使用されるエントロピー符号化の一種です。通常、ASCIIコードのように、文字列は文字ごとに固定ビット数を使用して表現されます。文字列を算術符号化に変換すると、頻繁に使用される文字はより少ないビットで格納され、あまり頻繁には出現しない文字はより多くのビットで格納されるため、合計でより少ないビットが使用されます。算術符号化は、ハフマン符号化などの他のエントロピー符号化とは異なり、入力を構成要素のシンボルに分割してそれぞれをコードに置き換えるのではなく、メッセージ全体を単一の数値、任意精度の分数q (0.0 ≤ q < 1.0 )にエンコードします。^[¹^]

エントロピーとの関係

算術符号化は、区間 [0, 1) をシンボル確率に比例した小区間に分割することで圧縮を実現します。シンボル確率が等しくない場合、確率の高いシンボルにはより大きな小区間が割り当てられ、その区間内の点を指定するのに必要なビット数が少なくなります。この圧縮の理論的な限界は、ソースのエントロピーによって与えられ、シャノンのソース符号化定理は、任意のロスレス方式で達成できるシンボルあたりの最小平均ビット数としてエントロピーを確立します。^{[ 2 ]}^{[ 3 ]}算術符号化は、特に長いメッセージの場合に、この限界に非常に近い値になります。^{[ 1 ]}^{[ 4 ]}

すべてのシンボルが等しい確率で出現する場合、各サブインターバルは同じサイズになり、どのシンボルも他のシンボルより少ないビット数で表現することはできません。この場合、エントロピーは最大値に達します。 $\log _{2}n$ ビット/シンボル ( $n$ はアルファベットのサイズです）であり、圧縮は不可能です。たとえば、独立した公平なコイン投げのストリームは、シンボルあたりちょうど 1 ビットのエントロピーを持ち、これはストレージの全コストであるため、算術符号化はメリットを提供しません。同様に、等しい確率を持つ独立した 3 進シンボルは、シンボルあたり約 1.585 ビットのエントロピーを持ち、これは 3 シンボルのアルファベットの最大値であり、同様に圧縮不可能です。^{[ 3 ]}^{[ 2 ]}

確率が不均等な場合、部分区間のサイズが不均等になるため、圧縮が可能になります。たとえば、確率が 0.9 と 0.1 のバイナリソースは、シンボルあたり約 0.469 ビットのエントロピーを持ちます。確率 0.9 のシンボルは各区間の 90% を受け取るため、ほとんどのエンコード手順では区間がほとんど縮小されず、最終値を識別するために必要なビット数が少なくなります。これにより、算術符号化で約 2.1:1 の圧縮率を達成できます。^{[ 3 ]}^{[ 1 ]}

実装の詳細と例

等しい確率

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

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

値を解読するには、元の文字列の長さが 6であることがわかっているので、単純に3進数に変換し、6桁に丸めて文字列を復元すればよい。

モデルの定義

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

例：特定の監視機器の出力を時間経過とともに記述する単純な静的モデルは次のようになる。

シンボルが「中立」となる確率は60%
シンボルがポジティブになる確率は20%
シンボルがマイナスになる確率は10%
END-OF-DATAシンボルが発生する確率は10%です。（このシンボルが存在するということは、データ圧縮ではよくあることですが、ストリームが「内部的に終了」していることを意味します。データストリームにこのシンボルが現れると、デコーダはストリーム全体が復号されたことを認識します。）

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

エンコードとデコード：概要

一般的に、エンコード処理の各ステップは、最後のステップを除いて同じです。エンコーダーは基本的に3つのデータのみを考慮する必要があります。^{[ 1 ]}

次にエンコードする必要のあるシンボル
現在の間隔（エンコード処理の開始時には間隔は[0,1]に設定されますが、これは変更されます）
この段階で起こりうる様々なシンボルそれぞれにモデルが割り当てる確率（前述の通り、高次モデルや適応型モデルでは、これらの確率は各ステップで必ずしも同じとは限らない）。

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

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

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

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

ただし、最終区間を送信する必要はなく、その区間内に含まれる1つの分数のみを送信すれば十分です。具体的には、その分数の十分な桁数（どの基数でも）を送信すれば、その桁数で始まるすべての分数が最終区間内に収まります。これにより、結果として得られるコードがプレフィックスコードであることが保証されます。^{[ 7 ]}

エンコードとデコード：例

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

このプロセスはエンコーダーが使用するのと同じ区間[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 シンボルの範囲内にあるため、これが次のシンボルになります。これは内部終了シンボルでもあるため、デコードが完了したことを意味します。ストリームが内部的に終了しない場合は、ストリームがどこで停止するかを示す別の方法が必要です。そうしないと、デコード処理が永遠に続き、実際にエンコードされた数よりも多くのシンボルを誤って読み取ってしまう可能性があります。^{[ 1 ]}

非効率性の原因

前の例のメッセージ0.538は、0.534、0.535、0.536、0.537、または0.539という同じ長さの小数でエンコードできたはずです。これは、2進数の代わりに10進数を使用することで、何らかの非効率性が生じることを示唆しています。これは正しいです。3桁の10進数の情報量は $3\times \log _{2}(10)\approx 9.966$ ビット。同じメッセージは、わずか 8 ビットのコストでバイナリ小数 0.10001001 (10 進数で 0.53515625 に相当) にエンコードできたはずです。^{[ 7 ]}

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

\sum -\log _{2}(p_{i})=-\log _{2}(0.6)-\log _{2}(0.1)-\log _{2}(0.1)=7.381{\text{ ビット}}.

しかし、バイナリ符号化では整数ビット数を使用する必要があるため、このメッセージのエンコーダは少なくとも8ビットを使用し、結果としてメッセージはエントロピーの内容よりも8.4%大きくなります。最大1ビットのこの非効率性により、メッセージサイズが大きくなるにつれてオーバーヘッドは相対的に少なくなります。^{[ 7 ]}

さらに、主張されたシンボル確率は[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 ]}

適応型算術符号化

算術符号化が他の類似のデータ圧縮方式に比べて優れている点の1つは、適応が容易であることです。適応とは、データ処理中に頻度（または確率）テーブルを変更することです。復号時の頻度テーブルが符号化時と同じ方法、同じステップで置き換えられる限り、復号されたデータは元のデータと一致します。同期は通常、符号化および復号処理中に発生するシンボルの組み合わせに基づいています。^{[ 1 ]}^{[ 6 ]}

精度と再正規化

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

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

基数変換の一般化としての算術符号化

記号の出現確率が等しい場合、算術符号化は基数、つまり基数の単純な変更によって実現できることを思い出してください。一般に、算術（および範囲）符号化は、基数の一般化された変更として解釈できます。^[⁵^]例えば、任意の記号列を見てみましょう。

\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にマッピングされ、次に多項式によって整数にマッピングされます。

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ビットにはあまり近くない。 ^{[ 3 ]}

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

{\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は次のように計算できます。

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

どこ $\scriptstyle C_{i}$ 累積頻度と $\scriptstyle f_{k}$ は出現頻度です。インデックスはメッセージ内のシンボルの位置を示します。すべての頻度が $\scriptstyle f_{k}$ 1 の場合、これは基数変換式です。^{[ 5 ]}

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

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 に等しい場合、古典的な基数変換の特殊なケースになります。^{[ 5 ]}

圧縮メッセージの理論的限界

下限L はn ^{n を}超えることはなく、ここでnはメッセージのサイズであり、したがって次のように表すことができます。 $\log _{2}(n^{n})=n\log _{2}(n)$ ビット。上限Uを計算し、区間 [ L , U )から最も長いゼロの列を持つ数を選択することによってメッセージを削減した後、この長さは次のように削減できると推測できます。 $\textstyle \log _{2}\left(\prod _{k=1}^{n}f_{k}\right)$ ビット。各周波数は、その周波数の値と全く同じ回数出現するため、アルファベットAのサイズを積の計算に使用できます。

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

メッセージの推定ビット数にlog ₂を適用すると、最終的なメッセージ (メッセージの長さと頻度テーブルの対数オーバーヘッドは除く) は、エントロピーによって与えられるビット数と一致し、長いメッセージの場合は最適値に非常に近くなります。^{[ 3 ]}^{[ 2 ]}

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

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

漸近等分配

これは直感的に理解できます。ソースがエルゴード的であると仮定すると、漸近等分配特性（AEP）を持ちます。AEPにより、長いストリームの後、 $n$ 記号、間隔 $(0,1)$ ほぼ等しい大きさの区間に分割されている。^{[ 3 ]}

技術的には、どんな小さなものでも $\epsilon >0$ 十分に大きいすべての $n$ 存在する $2^{nH(X)(1+O(\epsilon ))}$ 弦 $x_{1:n}$ それぞれの文字列がほぼ等しい確率を持つように $Pr(x_{1:n})=2^{-nH(X)(1+O(\epsilon ))}$ 、そしてそれらの合計確率は $1-O(\epsilon )$ 。

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

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

他の圧縮方式との連携

ハフマン符号化

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

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

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

ハフマン符号化の最適性の欠如に対処する簡単な方法の1つは、シンボルを連結（「ブロッキング」）して新しいアルファベットを形成することです。この新しいアルファベットでは、各新しいシンボルは、元のアルファベットからの元のシンボルのシーケンス（この場合はビット）を表します。上記の例では、エンコード前に3つのシンボルのシーケンスをグループ化すると、次の頻度の新しい「スーパーシンボル」が生成されます。^{[ 6 ]}

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

このグループ化により、ハフマン符号化は、シンボルごとに平均 1.3 ビット、つまりシンボルあたり 0.433 ビットとなり、元の符号化のシンボルあたり 1 ビットと比較されます。 $56.7\%$ 圧縮。任意の長さのシーケンスを許容すると、算術符号化と同様にエントロピーに任意に近づくが、そのためには巨大なコードが必要となるため、この目的においては算術符号化ほど実用的ではない。^{[ 6 ]}

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

歴史と特許

算術符号化の基本アルゴリズムは、IBM リサーチのJorma J. Rissanenとスタンフォード大学の博士課程学生 Richard C. Pasco によってそれぞれ独立して開発され、両方とも 1976 年 5 月に発表されました。^[⁵^]^[⁹^] Pasco は Rissanen の論文の出版前の草稿を引用し、彼らの研究の関係についてコメントしています。^[⁹^]

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

発表から1年も経たないうちに、IBMはリッサネンの研究成果について米国特許を出願した。一方、パスコの研究成果は特許化されなかった。

算術符号化のためのさまざまな具体的な技術は、歴史的に米国特許で保護されてきましたが、特許の失効に伴い、多くの周知の手法がパブリックドメインに移行しています。特許で保護されている技術は、一部の正式な国際標準で規定されている算術符号化アルゴリズムを実装するために不可欠な場合があります。このような場合、これらの特許は一般的に、「合理的かつ非差別的」（RAND）ライセンス条件（少なくとも標準化委員会のポリシーとして）に基づいてライセンス供与されます。いくつかの有名な事例（すでに失効したIBMの特許を含む）では、このようなライセンスは無料で提供されていましたが、他の事例ではライセンス料が必要でした。RAND条件でのライセンスの提供は、必ずしもその技術を利用したいすべての人を満足させるものではありません。なぜなら、独自の商用ソフトウェア製品を開発する企業にとって「合理的」に見えるものが、フリーソフトウェアやオープンソースプロジェクトにとってはそれほど合理的ではないように見える場合があるからです。

少なくとも1つの重要な圧縮ソフトウェアプログラムであるbzip2は、当時の特許状況を考慮して、算術符号化の使用を意図的に中止し、ハフマン符号化を採用しました。また、ハフマン符号化と算術符号化の両方のオプションがあるJPEGファイル形式のエンコーダとデコーダは、特許上の懸念から、通常はハフマン符号化オプションのみをサポートしています。その結果、現在使用されているほぼすべてのJPEG画像はハフマン符号化を使用しています^{[ 10 ]。}ただし、JPEGの算術符号化特許^{[ 11 ]}は、JPEG規格の古さ（設計は1990年頃にほぼ完了）のために期限切れとなっています^{[ 12 ]} 。JPEG XL、およびPackJPG、Brunsli、Leptonなどのアーカイバは、ハフマン符号化されたファイルを算術符号化（またはJPEG XLの場合は非対称数値システム）のファイルにロスレスで変換でき、最大25%のサイズ削減を実現しています。

JPEG画像圧縮フォーマットの算術符号化アルゴリズムは、以下の引用特許（既に失効）に基づいています。^{[ 13 ]}

米国特許 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日特許付与 – グレン・ジョージ・ラングドン、ジョーン・L・ミッチェル、ウィリアム・B・ペネベーカー、ヨルマ・ヨハネス・リッサネン – 算術符号化エンコーダおよびデコーダシステム
米国特許第4,935,882号– (IBM) 1988年7月20日出願、1990年6月19日特許付与 – ウィリアム・B・ペネベーカー、ジョーン・L・ミッチェル – 算術コーダーのための確率適応
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日特許付与 – グレン・ジョージ・ラングドン、ヨルマ・ヨハネス・リッサネン – 算術文字列符号化の方法および手段
米国特許第4,286,256号– (IBM) 1979年11月28日出願、1981年8月25日特許付与 – グレン・ジョージ・ラングドン、ヨルマ・ヨハネス・リッサネン – 演算回数を削減した算術符号化の方法および手段
米国特許4,467,317 – (IBM) 1981年3月30日出願、1984年8月21日特許付与 – グレン・ジョージ・ラングドン、ヨルマ・ヨハネス・リッサネン – 同時値更新を用いた高速算術圧縮符号化
米国特許4,891,643 – (IBM) 1986年9月15日出願、1990年1月2日特許付与 – ジョーン・L・ミッチェル、ウィリアム・B・ペネベーカー – 選択的に使用される多様な算術符号化エンコーダおよびデコーダによる算術符号化データの圧縮/解凍
日本特許第11782787号– ( NEC ) 1987年5月13日出願、1988年11月18日特許付与 – 島田道夫 – データ圧縮算術符号化装置
日本特許第15015487号（KDDI）1987年6月18日出願、1988年12月22日特許付与 – 松本修一、齋藤正博 – 算術符号化における桁上がり伝播防止システム
米国特許第4,933,883号– (IBM) 1988年5月3日出願、1990年6月12日特許付与 – ウィリアム・B・ペネベーカー、ジョーン・L・ミッチェル – 算術コーダーのための確率適応
米国特許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日特許付与 – ウィリアム・B・ペネベーカー、ジョーン・L・ミッチェル – 算術コーダーのための確率適応
米国特許第5,272,478号– (リコー) 1992年8月17日出願、1993年12月21日特許付与 – ジェームズ・D・アレン – エントロピー符号化の方法および装置

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

算術符号化に関する特許は、他の法域にも存在する可能性があります。世界各国におけるソフトウェアの特許性については、ソフトウェア特許の項を参照してください。

ベンチマークおよびその他の技術的特性

算術符号化のプログラムによる実装はそれぞれ圧縮率とパフォーマンスが異なります。圧縮率はわずかにしか変化しませんが（通常 1% 未満）、^{[ 7 ]}コードの実行時間は 10 倍も変化する可能性があります。パフォーマンスと圧縮率はデータの種類、特にアルファベットのサイズ（異なる記号の数）にも依存するため、公開されているエンコーダのリストから適切なエンコーダを選択するのは簡単な作業ではありません。2 つのエンコーダのうち一方は小さなアルファベットに対してより優れたパフォーマンスを発揮し、もう一方は大きなアルファベットに対してより優れたパフォーマンスを発揮する可能性があります。ほとんどのエンコーダはアルファベットのサイズに制限があり、その多くは正確に 2 つの記号 (0 と 1) のアルファベットに特化しています。

注記

1 2 3 4 5 6 7 8 9 10 11 12 13 Witten, Ian H.; Neal, Radford M.; Cleary, John G. (1987 年 6 月). "データ圧縮のための算術符号化". Communications of the ACM . 30 (6): 520– 540. doi : 10.1145/214762.214771 . S2CID 3343393 .
1 2 3 4シャノン、クロード E. (1948). "通信の数学理論".ベルシステムテクニカルジャーナル.27 (3): 379–423.doi : 10.1002 / j.1538-7305.1948.tb01338.x .
1 2 3 4 5 6 7 8カバー、トーマス M.、トーマス、ジョイ A. (2006).情報理論の基礎(第 2版). ジョンワイリー & サンズ. ISBN 978-0-471-24195-9。
↑ Rissanen, JJ; Langdon, GG, Jr (1979 年 3 月). "算術符号化". IBM Journal of Research and Development . 23 (2): 149–162 . doi : 10.1147/rd.232.0149 . S2CID 39909636 . {{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)
1 2 3 4 5 6 Rissanen, Jorma (1976 年 5 月). 「一般化された Kraft 不等式と算術符号化」. IBM Journal of Research and Development . 20 (3): 198–203 . doi : 10.1147/rd.203.0198 .
1 2 3 4 5 Sayood, Khalid (2017). Introduction to Data Compression (5th ed.). Morgan Kaufmann. ISBN 978-0-12-809474-7。
1 2 3 4 5 6 7 Howard, Paul G.; Vitter, Jeffrey S. (1994), "データ圧縮のための算術符号化", Proceedings of the IEEE , 82 (6): 857– 865, doi : 10.1109/5.286189 , hdl : 1808/7229
↑ Huffman, David (1952). "最小冗長符号の構築方法". Proceedings of the IRE . 40 (9). Institute of Electrical and Electronics Engineers (IEEE): 1098–1101 . doi : 10.1109/jrproc.1952.273898 . ISSN 0096-8390 .
1 2パスコ、リチャード・クラーク（1976年5月）。高速データ圧縮のためのソース符号化アルゴリズム（博士論文）。スタンフォード大学。CiteSeerX 10.1.1.121.3377。
↑ 「JPEGとは何ですか？」 .圧縮に関するよくある質問（パート1/3） .
↑ 「勧告T.81（1992）訂正1（01/04）」。勧告T.81（1992）。国際電気通信連合。2004年11月9日。 2011年2月3日取得。
↑ Pennebaker, WB; Mitchell, JL (1992). JPEG 静止画像データ圧縮規格. Kluwer Academic Press. ISBN 0442012721。
↑ 「T.81 – 連続階調静止画像のデジタル圧縮および符号化 – 要件およびガイドライン」(PDF) . CCITT . 1992年9月. 2019年7月12日取得.
↑ 「よくある質問」 . comp.compression .
↑ 「Diracビデオコーデック1.0がリリースされました[ LWN.net ]」。lwn.net。

参考文献

MacKay, David JC ( 2003年9月) 「第6章：ストリーム符号」『情報理論、推論、学習アルゴリズム』ケンブリッジ大学出版局。ISBN 0-521-64298-12007年12月22日にオリジナル（PDF/ PostScript / DjVu / LaTeX）からアーカイブされました。2007年12月30日に取得。
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). 「第22.6節算術符号化」 . Numerical Recipes: The Art of Scientific Computing (第3 版). ニューヨーク: Cambridge University Press. ISBN 978-0-521-88068-82011年8月11日にオリジナルからアーカイブされました。 2011年8月18日に取得。
Rissanen, Jorma (1976 年 5 月). 「一般化された Kraft 不等式と算術符号化」 . 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日取得.

Rodionov Anatoly、Volkov Sergey (2010)「p進算術符号化」Contemporary Mathematics Volume 508、2010 Contemporary Mathematics
Rodionov Anatoly、Volkov Sergey (2007)「p進算術符号化」、P進算術符号化
言語モデリングは圧縮であるhttps://arxiv.org/pdf/2309.10668

外部リンク

この記事は、ポール・E・ブラック著「算術符号化」、『アルゴリズムとデータ構造の辞典』、NIST のパブリックドメイン資料を組み込んでいます。
算術符号化（整数のみ）の簡単な例をまとめたニュースグループへの投稿。
PlanetMathの算術符号化に関する記事
レンジエンコーダの構造この記事では、レンジ符号化と算術符号化の両方について解説しています。また、3種類の算術エンコーダのコードサンプルと性能比較も掲載しています。
算術符号化入門（ 2020年11月9日、 Wayback Machineにアーカイブ済み）。60ページ。
エリック・ボッデン、マルテ・クラセン、ヨアヒム・クネイス：算術符号化の解明。技術報告書2007-5、セーブル研究グループ、マギル大学。
算術符号化＋統計モデリング＝データ圧縮（マーク・ネルソン著）
マーク・ネルソン著『算術符号化によるデータ圧縮』（2014年）
ジェームズ・K・ボンフィールドによるレンジコーディングとrANSの迅速な実装

[Witten1987-1] 1 2 3 4 5 6 7 8 9 10 11 12 13 Witten, Ian H.; Neal, Radford M.; Cleary, John G. (1987 年 6 月). "データ圧縮のための算術符号化". Communications of the ACM . 30 (6): 520– 540. doi : 10.1145/214762.214771 . S2CID 3343393 .

[Shannon1948-2] 1 2 3 4シャノン、クロード E. (1948). "通信の数学理論".ベルシステムテクニカルジャーナル.27 (3): 379–423.doi : 10.1002 / j.1538-7305.1948.tb01338.x .

[CoverThomas-3] 1 2 3 4 5 6 7 8カバー、トーマス M.、トーマス、ジョイ A. (2006).情報理論の基礎(第 2版). ジョンワイリー & サンズ. ISBN 978-0-471-24195-9。

[Rissanen1979-4] Rissanen, JJ; Langdon, GG, Jr (1979 年 3 月). "算術符号化". IBM Journal of Research and Development . 23 (2): 149–162 . doi : 10.1147/rd.232.0149 . S2CID 39909636 . {{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)

[Rissanen1976-5] 1 2 3 4 5 6 Rissanen, Jorma (1976 年 5 月). 「一般化された Kraft 不等式と算術符号化」. IBM Journal of Research and Development . 20 (3): 198–203 . doi : 10.1147/rd.203.0198 .

[Sayood2017-6] 1 2 3 4 5 Sayood, Khalid (2017). Introduction to Data Compression (5th ed.). Morgan Kaufmann. ISBN 978-0-12-809474-7。

[Howard1994-7] 1 2 3 4 5 6 7 Howard, Paul G.; Vitter, Jeffrey S. (1994), "データ圧縮のための算術符号化", Proceedings of the IEEE , 82 (6): 857– 865, doi : 10.1109/5.286189 , hdl : 1808/7229

[Huffman1952-8] Huffman, David (1952). "最小冗長符号の構築方法". Proceedings of the IRE . 40 (9). Institute of Electrical and Electronics Engineers (IEEE): 1098–1101 . doi : 10.1109/jrproc.1952.273898 . ISSN 0096-8390 .

[Pasco1976-9] 1 2パスコ、リチャード・クラーク（1976年5月）。高速データ圧縮のためのソース符号化アルゴリズム（博士論文）。スタンフォード大学。CiteSeerX 10.1.1.121.3377。

[10] 「JPEGとは何ですか？」 .圧縮に関するよくある質問（パート1/3） .

[11] 「勧告T.81（1992）訂正1（01/04）」。勧告T.81（1992）。国際電気通信連合。2004年11月9日。 2011年2月3日取得。

[12] Pennebaker, WB; Mitchell, JL (1992). JPEG 静止画像データ圧縮規格. Kluwer Academic Press. ISBN 0442012721。

[t81-13] 「T.81 – 連続階調静止画像のデジタル圧縮および符号化 – 要件およびガイドライン」(PDF) . CCITT . 1992年9月. 2019年7月12日取得.

[14] 「よくある質問」 . comp.compression .

[15] 「Diracビデオコーデック1.0がリリースされました[ LWN.net ]」。lwn.net。

[

[ 2 ]

[ 3 ]

[ 4 ]

[

[ 6 ]

[ 7 ]

[ 8 ]

[

[ 10 ]。

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]