データ圧縮の算術符号化を実装の詳細とともに説明してもらえますか? 私はインターネットをサーフィンして、マーク・ネルソンの投稿を見つけましたが、何時間も試した後、実装の手法は確かに不明です。
マーク・ネルソンの算術コーディングに関する説明は、次の場所にあります。
http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/
質問する
4578 次
3 に答える
15
算術圧縮の主なアイデアは、必要なデータ長の正確な量を使用して確率をコーディングする機能です。
この量のデータはわかっており、Shannon によって証明されており、次の式を使用して簡単に計算できます: -log2(p)
たとえば、p=50% の場合、1 ビットが必要です。p=25% の場合、2 ビットが必要です。
これは、確率が 2 のべき乗である場合には十分単純です (この特殊なケースでは、ハフマン コーディングで十分です)。しかし、確率が 63% の場合はどうなるでしょうか。次に、-log2(0.63) = 0.67 ビットが必要です。トリッキーに聞こえます...
このプロパティは、確率が高い場合に特に重要です。何かを 95% の精度で予測できる場合、適切な推測を表すのに 0.074 ビットしか必要ありません。つまり、多くの圧縮が行われます。
さて、それを行う方法は？
まあ、それは思ったより簡単です。確率に応じて範囲を分割します。たとえば、100 の範囲、2 つの可能なイベント、および最初のイベントの確率が 95% の場合、最初の 95 の値は「イベント 1」と表示され、残りの最後の 5 つの値は「イベント 2」と表示されます。 .
わかりましたが、コンピューターでは 2 のべき乗を使用することに慣れています。たとえば、16 ビットの場合、可能な値の範囲は 65536 です。同じことをしてください: 範囲の最初の 95% (62259) を「イベント 1」とし、残りを「イベント 2」とします。明らかに「丸め」(精度) の問題がありますが、分配するのに十分な値がある限り、それほど問題ではありません。さらに、2 つのイベントに制約されず、無数のイベントを持つことができます。重要なのは、各イベントの確率に応じて値が割り当てられることだけです。
わかりましたが、「イベント 1」を表す 62259 個の値と、「イベント 2」を表す値が 3277 個あります。どちらを選ぶべきですか？まあ、どれでもいいでしょう。1、30、5500、62256 のいずれであっても、「イベント 1」を意味します。
実際、選択する値の決定は、現在の推測ではなく、次の推測に依存します。
「イベント1」があるとします。したがって、0 から 62256 までの任意の値を選択する必要があります。次の推測では、分布は同じです (イベント 1 が 95%、イベント 2 が 5%)。これらの確率で分布図を単純に割り当てます。今回を除いて、62256 個の値に分散されています。そして、このように続けて、各推測で値の範囲を減らします。
したがって、実際には、推測ごとに狭まる「範囲」を定義しています。ただし、ある時点で精度の問題が発生します。これは、値がほとんど残っていないためです。
アイデアは、範囲を単純に「膨らませる」ことです。たとえば、範囲が 32768 (2^15) を下回るたびに、最上位ビットを出力し、残りを 2 で乗算します (実質的に値を 1 ビット左にシフトします)。このように連続して行うことで、一連の推測で確定しながらビットを1つずつ出力していきます。
ここで、圧縮との関係が明らかになります。範囲が急速に狭められると (例: 5%)、多くのビットを出力して範囲を制限より上に戻します。一方、確率が非常に高い場合、範囲は非常にゆっくりと狭くなります。最初のビットを出力する前に、多くの推測をすることさえできます。これが、イベントを「ほんのわずか」に圧縮できる方法です。
この記事を一般的なものにするために、意図的に「確率」、「推測」、「イベント」という用語を使用しました。ただし、データ圧縮の場合は、データをモデル化する方法に置き換えるだけです。たとえば、次のイベントを次のバイトにすることができます。この場合、256 個あります。
于 2012-04-16T17:17:28.810 に答える
2
おそらく、このスクリプトは、算術コーダーのより優れたメンタル モデルを構築するのに役立つ可能性があります: gen_map.py。もともとは、算術コーダー ライブラリのデバッグを容易にし、単体テストの生成を簡素化するために作成されました。ただし、算術コーディングを理解するのにも役立つ素敵な ASCII ビジュアライゼーションが作成されます。
小さな例です。03 つの記号のアルファベットがある1と想像し2てください。そして、 sequence をエンコードしたいと思います。スクリプトは次の出力を提供します (ここではオプションを無視します)。1/102/107/10[1, 2]-b N
$ ./gen_map.py -b 6 -m "1,2,7" -e "1,2"
000000111111|1111|111222222222222222222222222222222222222222222222
------011222|2222|222000011111111122222222222222222222222222222222
---------011|2222|222-------------00011111122222222222222222222222
------------|----|-------------------------00111122222222222222222
------------|----|-------------------------------01111222222222222
------------|----|------------------------------------011222222222
==================================================================
000000000000|0000|000000000000000011111111111111111111111111111111
000000000000|0000|111111111111111100000000000000001111111111111111
000000001111|1111|000000001111111100000000111111110000000011111111
000011110000|1111|000011110000111100001111000011110000111100001111
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
001100110011|0011|001100110011001100110011001100110011001100110011
010101010101|0101|010101010101010101010101010101010101010101010101
最初の 6 行 (行の前====) は、0.0 から 1.0 までの範囲を表し、シンボルの確率に比例する間隔で再帰的に分割されます。注釈付きの最初の行:
[1/10][ 2/10 ][ 7/10 ]
000000111111|1111|111222222222222222222222222222222222222222222222
次に、各区間を再度分割します。
[ 0.1][ 0.2 ][ 0.7 ]
000000111111|1111|111222222222222222222222222222222222222222222222
[ 0.7 ][.1][ 0.2 ][ 0.7 ]
------011222|2222|222000011111111122222222222222222222222222222222
[.1][ .2][ 0.7 ]
---------011|2222|222-------------00011111122222222222222222222222
一部の区間は細分化されていないことに注意してください。これは、指定された精度 (-bオプションで指定) 内のすべてのサブインターバルを表すのに十分なスペースがない場合に発生します。
各行は、入力からのシンボルに対応します (この場合は - sequence [1, 2])。各入力シンボルのサブインターバルをたどることにより、最小量のビットでエンコードしたい最終的なインターバルが得られます。私たちの場合、それ2は 2 行目の最初のサブインターバルです。
[ This one ]
------011222|2222|222000011111111122222222222222222222222222222222
次の 7 行 ( の後====) は、同じ間隔 0.0 から 1.0 を表しますが、2 進表記に従って細分化されています。各行は出力のビットであり、0 と 1 の間で選択することにより、左または右の半サブインターバルを選択します。たとえば、bitsは 2 行目の01サブインターバルに対応します。[0.25, 05)
[ This one ]
000000000000|0000|111111111111111100000000000000001111111111111111
算術コーダーの考え方は、対応する間隔が入力シーケンスによって決定される間隔内に完全に収まる (または等しくなる) まで、ビット (0 または 1) を出力することです。私たちの場合、それは0011です。この~~~~線は、必要な間隔を明確に識別するのに十分なビットがある場所を示しています。
シンボルによって形成される垂直線|は、入力シーケンスのエンコードに使用できるビット シーケンス (行) の範囲を示します。
于 2015-10-12T01:22:49.450 に答える
1
まず、算術圧縮の概念を紹介してくれてありがとう!
この方法には次の手順があることがわかります。
- マッピングの作成: 各アルファベットの範囲サイズを与える各文字の出現率を計算します。次に、それらを並べ替えて、0 から 1 までの実際の範囲を割り当てます
- メッセージが与えられた場合、範囲を計算します（かなり簡単なIMHO）
- 最適なコードを見つける
3番目の部分は少しトリッキーです。次のアルゴリズムを使用します。
b を最適な表現とします。空の文字列 ('') に初期化します。x を最小値、y を最大値とします。
- x と y の倍数: x=2*x, y=2*y
- 両方とも 1 より大きい場合は、b に 1 を追加します。手順 1 に進みます。
- 両方とも 1 未満の場合は、b に 0 を追加します。手順 1 に進みます。
- x<1 で y>1 の場合、b に 1 を追加して終了
b には、基本的に、送信する数値の小数部分が含まれます。例えば。b=011 の場合、分数は 2 進数で 0.011 に相当します。
実装のどの部分が理解できませんか?
于 2012-04-13T21:15:46.137 に答える