算術コーディングについて説明する前に、ハフマンアルゴリズムについて少し説明する必要があります。 この方法は、シンボル周波数が1/2 n （nは正の整数）に比例する場合に有効です。 この文は、各文字のハフマン符号が常に整数のビットで構成されていることを思い出すと明らかになります。 シンボルの出現頻度が0.2の場合、このシンボルをエンコードするための最適なコードの長さは–log 2 （0.2）= 2.3ビットである必要があります。 ハフマン接頭辞コードがそのような長さを持つことはできないことは明らかです。 これにより、最終的にデータの圧縮率が低下します。
算術コーディングは、この問題を解決することを目的としています。 主なアイデアは、コードを個々のキャラクターではなく、それらのシーケンスに割り当てることです。
最初に、アルゴリズムの背後にある考え方を検討し、次に小さな実用的な例を検討します。
すべてのエントロピーアルゴリズムと同様に、アルファベットの各シンボルの使用頻度に関する情報があります。 この情報は、検討中のメソッドのソースです。 次に、作業セグメントの概念を紹介します。 中間間隔[a; b）にポイントが配置されているものは、ワーカーと呼ばれます。 さらに、ポイントは、それらによって形成されるセグメントの長さが文字の使用頻度に等しくなるように配置されます。 アルゴリズムが初期化されると、a = 0 b = 1になります。
1つのコーディング手順は単純な操作で構成されます。エンコードされた文字が取得され、作業セグメントの対応するセクションが検索されます。 見つかったセクションは新しい作業セグメントになります（つまり、ドットを使用して分割する必要もあります）。
この操作は、ソースストリームの多くの文字に対して実行されます。 文字列のコーディングの結果は、最終作業セグメントからの任意の数（およびビットレコードの長さ）です（ほとんどの場合、セグメントの左境界が使用されます）。
それはかなり複雑に聞こえます。 小さな例を使って理解してみましょう。 説明した方法を使用して、メッセージ「THIS_METHOD_BETTER_HAFFMANA」をエンコードします。
文字の出現頻度の表を作成したら、コーディングを開始できます。 最初の段階では、作業セグメントを作成します。 次のようになります。
ストリームから最初のシンボルを取得します。これはシンボル「E」です。 対応するセグメントはセグメント[0.96; 1）です。 1つの文字をエンコードする場合、エンコード結果はこのセグメントの任意の数字になります。 しかし、1つのシンボルで停止するのではなく、別のシンボルを追加します。 記号「T」。 これを行うには、a = 0.96およびb = 1の新しい作業セグメントを作成します。 この行を元の行と同じ方法でドットで区切り、新しい「T」記号を読み取ります。 「T」記号は範囲[0.24; 0.36）に対応していますが、作業セグメントはすでにセグメント[0.96; 1）に縮小されています。 つまり 振り返る必要のある境界線。 これは、次の2つの式を使用して実行できます。High = Low old +（High old- Low old ）* Range High （x）、Low = Low old +（High old- Low old ）* Range Low （x）、ここでlow old -間隔の下限、High old-範囲Range HighおよびRange Lowの上限-エンコードされた文字の上限と下限。
これらの式を使用して、メッセージの最初の単語全体をエンコードします。
エンコード結果は、半区間[0.97218816; 0.97223424）。
半区間の左境界、つまり 番号0.97218816。
デコード処理を検討してください。 コードは半間隔[0.96; 1）にあります。 つまり メッセージ「E」の最初の文字。 2番目の文字（半分の間隔[0.96; 1）でエンコードされた）をデコードするには、半分の間隔を正規化する必要があります。 [0; 1）の形式にキャストします。 これは次の式を使用して行われます：code =（code-Range Low （x））/（Range High （x）-Range Low （x））、codeは現在のコード値です。
この式を適用すると、新しい値コード=（0.97218816-0.96）/（1-0.96）= 0.3004704が得られます。 つまり シーケンス「T」の2番目の文字。
再び式を適用します：code =（0.3004704-0.24）/（0.36-0.24）= 0.5392。 シーケンスの3番目の文字は「O」です。
説明されているスキームに従って、デコードを継続すると、ソーステキストを完全に復元できます。
T.O. すべてのエントロピーアルゴリズムの中で最も効率的なエンコードとデコードのアルゴリズムを検討しました。 この記事から何か新しいことを学び、算術符号化アルゴリズムにある基本的なアイデアを理解してください。