非対称数字システム

非対称数字システム （ ANS ）は、Jagiellonian UniversityのJarosław（Jarek）Dudaによって導入されたエントロピーエンコード方式のファミリーであり、以前に使用された方式と比較してパフォーマンスが向上し、最大30倍高速であるため2014年からデータ圧縮に使用されています。 ANSは、算術符号化（ほぼ正確な確率分布を使用）の圧縮率と、ハフマン符号化と同様の処理コストを組み合わせます。テーブル化されたANS（tANS）バリアントでは、これは、乗算を使用せずに大きなアルファベットを操作する有限状態マシンを構築することにより実現されます。

特に、ANSはFacebook Zstandardコンプレッサー（Linuxカーネル、Androidオペレーティングシステムなどで使用され、MIMEおよびHTTPのRFC 8478として公開されています）、Apple LZFSEコンプレッサー、Google Draco 3Dコンプレッサー、PIK画像コンプレッサーで使用されていますSAMtoolsユーティリティ、Dropbox DivANSコンプレッサー、およびJPEG XL次世代画像圧縮標準のCRAM DNAコンプレッサー。

基本的な考え方は、情報を単一の自然数x {\ displaystyle x}にエンコードすることです。標準の2進数システムでは、s {\ displaystyle s}を追加することにより、ビットs∈{0,1} {\ displaystyle s \ in \ {0,1 \}}の情報をx {\ displaystyle x}に追加できます。 x {\ displaystyle x}の最後で、x ′= 2x + s {\ displaystyle x' = 2x + s}が得られます。エントロピーコーダーの場合、これはPr（0）= Pr（1）= 1/2 {\ displaystyle \ Pr（0）= \ Pr（1）= 1/2}の場合に最適です。 ANSは、確率分布（ps）s∈S{\ displaystyle（p_ {s}）_ {s \ in S}}を伴うシンボルs∈S{\ displaystyle s \ in S}の任意のセットに対してこのプロセスを一般化します。 ANSでは、x '{\ displaystyle x'}がs {\ displaystyle s}からx {\ displaystyle x}に情報を追加した結果である場合、x'≈x⋅ps-1{\ displaystyle x '\ approx x \ cdot p_ {s} ^ {-1}}。同様に、log2⁡（x ′）≈log2⁡（x）+log2⁡（1 / ps）{\ displaystyle \ log _ {2}（x'）\ approx \ log _ {2}（x）+ \ log _ {2}（1 / p_ {s}）}、ここでlog2⁡（x）{\ displaystyle \ log _ {2}（x）}は、数値x {\ displaystyle x}に格納されている情報のビット数です。 log2⁡（1 / ps）{\ displaystyle \ log _ {2}（1 / p_ {s}）}は、シンボルs {\ displaystyle s}に含まれるビット数です。

エンコードルールの場合、自然数のセットは、偶数と奇数のように異なるシンボルに対応する互いに素なサブセットに分割されますが、エンコードするシンボルの確率分布に対応する密度を持ちます。次に、シンボルs {\ displaystyle s}の情報を現在の番号x {\ displaystyle x}に既に保存されている情報に追加するには、番号x '= C（x、s）≈x/ p {\ displaystyle x'に移動します= C（x、s）\ approx x / p}は、s {\ displaystyle s}番目のサブセットからのx {\ displaystyle x}番目の外観の位置です。

それを実際に適用する別の方法があります-エンコードおよびデコード手順の直接的な数式（uABSおよびrANSバリアント）、または動作全体をテーブルに入れることができます（tANSバリアント）。再正規化は、x {\ displaystyle x}が無限になり、蓄積されたビットがビットストリームとの間で転送されるのを防ぐために使用されます。

エントロピーコーディング

1,000個のゼロと1のシーケンスをエンコードしたいと想像してください。直接保存するには1000ビットかかります。ただし、1つのゼロと999の1つだけが含まれていることが何らかの理由でわかっている場合は、ゼロの位置をエンコードするだけで十分です。これには、⌈log2⁡（1000）⌉= 10 {\ displaystyle \ lceil \ log _ {2}のみが必要です元の1000ビットではなく（1000）\ rceil = 10}ビットです。

一般に、pn {\ displaystyle pn}ゼロと（1-p）n {\ displaystyle（1-p）n}を含むそのような長さn {\ displaystyle n}シーケンスは、確率p∈（0,1）{\ displaystyle p \ in（0,1）}は、組み合わせと呼ばれます。スターリングの近似を使用して、漸近数を取得します

（npn）≈2nh（p）大きいnおよびh（p）= −plog2⁡（p）−（1−p）log2⁡（1−p）、{\ displaystyle {n \ choose pn} \ approx 2 ^ {nh（p）} {\ text {for large}} n {\ text {and}} h（p）=-p \ log _ {2}（p）-（1-p）\ log _ {2} （1-p）、}

シャノンエントロピーと呼ばれます。

したがって、そのようなシーケンスを1つ選択するには、約nh（p）{\ displaystyle nh（p）}ビットが必要です。 p = 1/2 {\ displaystyle p = 1/2}の場合は、n {\ displaystyle n}ビットのままですが、もっと小さくすることもできます。たとえば、p = 0.11 {\ displaystyle p = 0.11}に対して≈n/ 2 {\ displaystyle \ approx n / 2}ビットのみが必要です。

エントロピーコーダーを使用すると、シンボルあたりのシャノンエントロピービットをほぼ使用して、一連のシンボルをエンコードできます。たとえば、ANSを直接使用して組み合わせを列挙することができます。固定された比率を持つシンボルのすべてのシーケンスに異なる自然数をほぼ最適な方法で割り当てます。

エンコードの組み合わせとは対照的に、この確率分布は通常、データコンプレッサーによって異なります。この目的のために、シャノンエントロピーは加重平均として見ることができます。確率p {\ displaystyle p}のシンボルには、log2⁡（1 / p）{\ displaystyle \ log _ {2}（1 / p）}ビットの情報が含まれます。 ANSは、情報を単一の自然数x {\ displaystyle x}にエンコードし、log2⁡（x）{\ displaystyle \ log _ {2}（x）}ビットの情報を含むと解釈します。確率p {\ displaystyle p}のシンボルから情報を追加すると、この情報コンテンツがlog2⁡（x）+log2⁡（1 / p）=log2⁡（x / p）{\ displaystyle \ log _ {2}（x ）+ \ log _ {2}（1 / p）= \ log _ {2}（x / p）}。したがって、両方の情報を含む新しい数値は、x′≈x / p {\ displaystyle x '\ approx x / p}になります。

ANSの基本概念

たとえば、バイナリ展開のビットシーケンスとして、自然数x {\ displaystyle x}に格納されている情報があることを想像してください。バイナリ変数s {\ displaystyle s}から情報を追加するには、コーディング関数x ′= C（x、s）= 2x + s {\ displaystyle x' = C（x、s）= 2x + s}を使用できます。これは、すべてのビットを1桁上にシフトし、新しいビットを最下位位置に配置します。デコード関数D（x ′）=（⌊x′ /2⌋、mod（x ′、2））{\ displaystyle D（x'）=（\ lfloor x '/ 2 \ rfloor、\ mathrm {mod}（ x '、2））}により、前のx {\ displaystyle x}とこの追加ビットを取得できます：D（C（x、s））=（x、s）、C（D（x′））= x ′{\ displaystyle D（C（x、s））=（x、s）、\ C（D（x'））= x '}。 x = 1 {\ displaystyle x = 1}の初期状態から開始し、有限ビットシーケンスの連続ビットでC {\ displaystyle C}関数を使用して、この全体を格納する最終x {\ displaystyle x}番号を取得できます。シーケンス。次に、x = 1 {\ displaystyle x = 1}がビットシーケンスを逆順で取得できるようになるまで、D {\ displaystyle D}関数を複数回使用します。

上記の手順は、シンボルの均一（対称）確率分布Pr（0）= Pr（1）= 1/2 {\ displaystyle \ Pr（0）= \ Pr（1）= 1/2}に最適です。 ANSは、シンボルの任意の（非対称）確率分布に対して最適化するためにそれを一般化します：Pr（s）= ps {\ displaystyle \ Pr（s）= p_ {s}}。上記の例のs {\ displaystyle s}は偶数と奇数のC（x、s）{\ displaystyle C（x、s）}を選択していましたが、ANSではこの自然数の偶数/奇数除算はサブセットへの除算に置き換えられます想定される確率分布{ps} s {\ displaystyle \ {p_ {s} \} _ {s}}に対応する密度を持つ：位置x {\ displaystyle x}まで、およそxps {\ displaystyle xp_ {s}があります}シンボルs {\ displaystyle s}の出現。

コーディング関数C（x、s）{\ displaystyle C（x、s）}は、シンボルs {\ displaystyle s}に対応するサブセットからx {\ displaystyle x}番目の外観を返します。密度の仮定は、条件x ′= C（x、s）≈x/ ps {\ displaystyle x' = C（x、s）\ approx x / p_ {s}}と同等です。自然数x {\ displaystyle x}がlog2⁡（x）{\ displaystyle \ log _ {2}（x）}ビット情報を含むと仮定すると、log2⁡（C（x、s））≈log2⁡（x）+ log2⁡（1 / ps）{\ displaystyle \ log _ {2}（C（x、s））\ approx \ log _ {2}（x）+ \ log _ {2}（1 / p_ {s}） }。したがって、確率ps {\ displaystyle p_ {s}}のシンボルは、≈log2⁡（1 / ps）{\ displaystyle \ approx \ log _ {2}（1 / p_ {s}）}ビットの情報を含むものとしてエンコードされます。エントロピーコーダーに必要です。

ユニフォームバイナリバリアント（uABS）

バイナリアルファベットと確率分布Pr（1）= p {\ displaystyle \ Pr（1）= p}、Pr（0）= 1-p {\ displaystyle \ Pr（0）= 1-p}から始めましょう。位置x {\ displaystyle x}までは、奇数の約p⋅x{\ displaystyle p \ cdot x}の類似体が必要です（s = 1 {\ displaystyle s = 1}の場合）。この出現回数を⌈x⋅p⌉{\ displaystyle \ lceil x \ cdot p \ rceil}として選択し、s =⌈（x + 1）⋅p⌉−⌈x⋅p⌉ {\ displaystyle s = \を取得できます。 lceil（x + 1）\ cdot p \ rceil-\ lceil x \ cdot p \ rceil}。これはuABSバリアントと呼ばれ、次のデコードおよびエンコード機能につながります。

デコード：

s = ceil（（x + 1）* p）-ceil（x * p）// fract（x * p）1-pの場合は0、s = 0の場合は1、new_x = x-ceil（x * p ）// D（x）=（new_x、0）s = 1の場合new_x = ceil（x * p）// D（x）=（new_x、1）

エンコーディング：

if s = 0 then new_x = ceil（（x + 1）/（1-p））-1 // C（x、0）= new_x if s = 1 then new_x = floor（x / p）// C（ x、1）= new_x

p = 1/2 {\ displaystyle p = 1/2}の場合、標準バイナリシステム（0と1を反転）になります。異なるp {\ displaystyle p}の場合、この確率分布に対して最適になります。たとえば、p = 0.3 {\ displaystyle p = 0.3}の場合、これらの式はx {\ displaystyle x}の小さな値のテーブルになります。

C（x、s）{\ displaystyle C（x、s）}	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
s = 0 {\ displaystyle s = 0}		0	1		2	3		4	5	6		7	8		9	10		11	12	13
s = 1 {\ displaystyle s = 1}	0			1			2				3			4			5				6

シンボルs = 1 {\ displaystyle s = 1}は、密度p = 0.3 {\ displaystyle p = 0.3}の自然数のサブセットに対応します。この場合、位置は{0,3,6,10,13,16,20です、23、26、…} {\ displaystyle \ {0,3,6,10,13,16,20,23,26、\ ldots \}}。 1/4 0.3 1/3 {\ displaystyle 1/4 0.3 1/3}であるため、これらの位置は3または4増加します。ここで、p = 3/10 {\ displaystyle p = 3/10}であるため、シンボルのパターンは10ポジションごとに繰り返されます。

C（x、s）{\ displaystyle C（x、s）}は、特定のシンボルs {\ displaystyle s}に対応する行を取得し、この行で特定のx {\ displaystyle x}を取得することで見つけることができます。次に、一番上の行はC（x、s）{\ displaystyle C（x、s）}を提供します。たとえば、C（7,0）= 11 {\ displaystyle C（7,0）= 11}から中央の行まで。

x = 1 {\ displaystyle x = 1}から始まるシーケンス '0100'をエンコードしたいと想像してください。最初にs = 0 {\ displaystyle s = 0}を使用するとx = 2 {\ displaystyle x = 2}になり、次にs = 1 {\ displaystyle s = 1}からx = 6 {\ displaystyle x = 6}になり、次にs = 0 {\ displaystyle s = 0}からx = 9 {\ displaystyle x = 9}、そしてs = 0 {\ displaystyle s = 0}からx = 14 {\ displaystyle x = 14}。この最後のx {\ displaystyle x}でデコード関数D（x '）{\ displaystyle D（x'）}を使用することにより、シンボルシーケンスを取得できます。この目的でテーブルを使用すると、最初の行のx {\ displaystyle x}が列を決定し、次に空でない行と書き込まれた値がs {\ displaystyle s}およびx {\ displaystyle x}を決定します。

範囲バリアント（rANS）とストリーミング

範囲バリアントも算術式を使用しますが、大きなアルファベットを操作できます。直観的には、自然数のセットをサイズ2n {\ displaystyle 2 ^ {n}}の範囲に分割し、それぞれを仮定された確率分布によって与えられた割合の部分範囲に同一の方法で分割します。

確率分布を2n {\ displaystyle 2 ^ {n}}分母に量子化することから始めます。n{\ displaystyle n}が選択されます（通常8〜12ビット）：ps≈f/ 2n {\ displaystyle p_ {s} \一部の自然なf {\ displaystyle f}数（部分範囲のサイズ）の場合、約f / 2 ^ {n}}。

mask = 2n−1 {\ displaystyle {\ text {mask}} = 2 ^ {n} -1}、累積分布関数を示します。

CDF⁡= ∑i sf = f +⋯+ f。{\ displaystyle \ operatorname {CDF} = \ sum _ {i s} f = f + \ cdots + f。}

y∈{\ displaystyle y \ in}は関数を示します（通常はテーブル化されています）

symbol（y）= s（CDF = y CDF）

コーディング機能は次のとおりです。

C（x、s）=（floor（x / f） n）+（x％f）+ CDF

デコード：s = symbol（x＆mask）

D（x）=（f *（x >> n）+（x＆mask）-CDF、s）

このようにして、一連のシンボルを大きな自然数x {\ displaystyle x}にエンコードできます。多数の算術の使用を避けるため、実際にはストリームのバリアントが使用されます。これは、再正規化によりx∈{\ displaystyle x \ in}を強制します。x{\ displaystyle x}の最下位ビットをビットストリーム（通常L {\ displaystyle L}およびb {\ displaystyle b}は2のべき乗です。

rANSバリアントx {\ displaystyle x}では、たとえば32ビットです。 16ビットの正規化、x∈{\ displaystyle x \ in}の場合、デコーダは必要に応じてビットストリームから最下位ビットを補充します。

if（x （1 16））x =（x 16）+ read16bits（）

テーブルバリアント（tANS）

tANSバリアントは、x∈{\ displaystyle x \ in}の動作全体（繰り込みを含む）をテーブルに入れて、乗算を必要としない有限状態マシンを生成します。

最後に、デコードループのステップは次のように記述できます。

t = decodeTable（x）; x = t.newX + readBits（t.nbBits）; //状態遷移writeSymbol（t.symbol）; //デコードされたシンボル

エンコードループのステップ：

s = ReadSymbol（）; nbBits =（x + ns）>> r; //繰り込みのビット数writeBits（x、nbBits）; //最下位ビットをビットストリームx = encodingTablestarts {\ displaystyle}の位置に送信します。その出現回数は、想定される確率に比例する必要があります。たとえば、Pr（a）= 3/8、Pr（b）= 1/8、Pr（c）= 2/8、Pr（d）= 2/8確率分布の「abdacdac」割り当てを選択できます。シンボルが2の累乗の長さの範囲で割り当てられている場合、ハフマンコーディングが行われます。たとえば、a-> 0、b-> 100、c-> 101、d-> 11のプレフィックスコードは、「aaaabcdd」シンボル割り当てのtANSに対して取得されます。

m = 3のサイズのアルファベットとL = 16の状態のtANSテーブルを生成し、それらをストリームのデコードに適用する例。最初に、分母が状態の数である分数を使用して確率を近似します。次に、これらのシンボルをほぼ均一に拡散します。オプションで、同時暗号化の詳細は暗号キーに依存する場合があります。次に、指定されたシンボルの値である値で始まる外観を列挙します。次に、ストリームの最も若いビットを補充して、xの想定範囲に戻します（再正規化）。

備考

ハフマンコーディングに関しては、tANSの確率分布の変更は比較的コストがかかるため、主に静的な状況で使用されます。通常、Lempel-Zivスキーム（ZSTD、LZFSEなど）で使用されます。この場合、ファイルはブロックに分割されます。それぞれについて、シンボル頻度が独立してカウントされ、ブロックヘッダーに書き込まれた近似（量子化）後にtANSの静的確率分布として使用されます。

対照的に、rANSは通常、範囲コーディング（CRAM、LZNA、Draco、AV1など）の高速な代替として使用されます。乗算が必要ですが、メモリ効率が高く、確率分布を動的に適応させるのに適しています。

ANSのエンコードとデコードは反対方向に実行され、シンボルのスタックになります。この不便さは通常、逆方向にエンコードすることで解決され、その後デコードを順方向に行うことができます。マルコフモデルのようなコンテキスト依存の場合、エンコーダは後のデコードの観点からコンテキストを使用する必要があります。適応性を確保するために、エンコーダーはまず先に進み、デコーダーが使用（予測）する確率を見つけてバッファーに保存し、次にバッファーされた確率を使用して逆方向にエンコードする必要があります。

デコードの開始にはエンコードの最終状態が必要であるため、圧縮ファイルに保存する必要があります。このコストは、エンコーダーの初期状態に情報を保存することで補償できます。たとえば、「10000」状態で開始する代わりに、「1 ****」状態で開始します。「*」は、デコードの最後に取得できる追加の保存ビットです。または、この状態は、固定状態でエンコードを開始し、デコードの最終状態が予想される状態であるかどうかをテストすることにより、チェックサムとして使用できます。