非対称の数字体系

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

ANSは、Facebook Zstandardコンプレッサー^{[6] [7]}（Linuxカーネル^{[8] 、} Google Chromeブラウザ^{[9] 、} Android ^[10]オペレーティングシステムなどでも使用され、MIME ^[11]およびHTTP ^[12]についてはRFC 8478として公開されました）、Apple LZFSEコンプレッサー^{[13] 、} Google Draco 3D コンプレッサー^{[14] （} Pixar Universal Scene Description形式^[15]などで使用）、PIKイメージコンプレッサー^{[16] 、} SAMtoolsユーティリティのCRAM DNA コンプレッサー^[17]、NVIDIA nvCOMP高速圧縮ライブラリ^{[ 18] 、} Dropbox DivANS コンプレッサー^{[20] 、} Microsoft DirectStorage BCPackテクスチャコンプレッサー^[21]、JPEG XL ^[22]画像コンプレッサーなどで使用されています。

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

エンコード規則では、自然数の集合は、異なるシンボルに対応する互いに素なサブセットに分割されます。たとえば、偶数と奇数に分割されますが、密度はエンコードするシンボルの確率分布に対応します。次に、シンボル からの情報を現在の数値 にすでに格納されている情報に追加するには、数値 を、数値サブセットの 番目に出現する位置に移動します。 ${\displaystyle s}$${\displaystyle x}$${\displaystyle x'=C(x,s)\approx x/p}$${\displaystyle x}$${\displaystyle s}$

実際にそれを適用するには、別の方法があります。エンコードとデコードの手順を直接数式で表す方法 (uABS と rANS のバリアント) や、動作全体をテーブルにまとめる方法 (tANS のバリアント) です。再正規化は、蓄積されたビットをビットストリームとの間で転送して無限大にならないようにするために使用されます。 ${\displaystyle x}$

1,000 個の 0 と 1 のシーケンスをエンコードするとします。これを直接保存するには 1,000 ビットが必要です。ただし、ゼロが 1 個と 1 が 999 個だけ含まれていることが何らかの方法でわかっている場合は、ゼロの位置をエンコードするだけで十分であり、元の 1,000 ビットではなく、ここでは ビットのみが必要です。 ${\displaystyle \lceil \log _{2}(1000)\rceil \approx 10}$

一般に、ある確率で0と1を含む長さのシーケンスは組み合わせと呼ばれます。スターリングの近似を使用すると、それらの漸近数は次のように得られます。 ${\displaystyle n}$${\displaystyle pn}$${\displaystyle (1-p)n}$${\displaystyle p\in (0,1)}$

${\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 つ選択するには、約 ビットが必要です。の場合でも ビットですが、これよりずっと小さくなることもあります。たとえば、 の場合、ビットのみ必要です。 ${\displaystyle nh(p)}$${\displaystyle n}$${\displaystyle p=1/2}$${\displaystyle \approx n/2}$${\displaystyle p=0.11}$

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

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

3 つの文字 A、B、C が 1/2、1/4、1/4 の確率で含まれるソースを考えます。バイナリで最適なプレフィックス コードを構築するのは簡単です。A = 0、B = 10、C = 11。すると、メッセージは ABC -> 01011 としてエンコードされます。

エンコードを実行する同等の方法は次のとおりです。

• 数字 1 から始めて、入力文字ごとに数字に対して演算を実行します。
• A = 2 を掛ける、B = 4 を掛けて 2 を足す、C = 4 を掛けて 3 を足す。
• 数値を 2 進数で表し、最初の数字 1 を削除します。

より一般的な k 文字のソースを有理確率で考えてみましょう。ソースに対して 算術符号化を実行するには、整数を使用した正確な算術演算のみが必要です。${\displaystyle n_{1}/N,...,n_{k}/N}$

一般に、ANS は、実確率を分母が小さい有理数で近似する算術符号化の近似です。 ${\displaystyle r_{1},...,r_{k}}$${\displaystyle n_{1}/N,...,n_{k}/N}$${\displaystyle N}$

自然数 に、たとえばその 2 進展開のビット シーケンスとして何らかの情報が格納されているとします。2 進変数 から情報を追加するには、コーディング関数 を使用できます。この関数は、すべてのビットを 1 つ上にシフトし、新しいビットを最下位の位置に配置します。デコード関数 を使用すると、前のビットとこの追加ビットを取得できます。初期状態から始めて、有限ビット シーケンスの連続ビットに 関数を使用して、このシーケンス全体を格納する最終的な数値を取得します。その後、になるまで 関数 を複数回使用すると、ビット シーケンスを逆の順序で取得できます。 ${\displaystyle x}$${\displaystyle s}$${\displaystyle x'=C(x,s)=2x+s}$${\displaystyle D(x')=(\lfloor x'/2\rfloor ,\mathrm {mod} (x',2))}$${\displaystyle x}$${\displaystyle D(C(x,s))=(x,s),\ C(D(x'))=x'}$${\displaystyle x=1}$${\displaystyle C}$${\displaystyle x}$${\displaystyle D}$${\displaystyle x=1}$

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

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

2進アルファベットと確率分布 から始めましょう。位置 まで、奇数（ の場合）の近似値を求めます。この出現回数を として選択すると、 が得られます。この変形はuABSと呼ばれ、次のデコードおよびエンコード関数につながります。^[23]${\displaystyle \Pr(1)=p}$${\displaystyle \Pr(0)=1-p}$${\displaystyle x}$${\displaystyle p\cdot x}$${\displaystyle s=1}$${\displaystyle \lceil x\cdot p\rceil }$${\displaystyle s=\lceil (x+1)\cdot p\rceil -\lceil x\cdot p\rceil }$

デコード:

s = ceil (( x + 1 ) * p ) - ceil ( x * p ) // fract(x*p) < 1-p の場合は 0、それ以外の場合は 1 s = 0の場合はnew_x = x - ceil ( x * p ) // D(x) = (new_x, 0)、これは new_x = floor(x*(1-p)) と同じです。s = 1の場合はnew_x = ceil ( x * p ) // D(x) = (new_x, 1)      
            
         

エンコーディング：

s = 0の場合、new_x = ceil (( x + 1 ) / ( 1 - p )) - 1 // C(x,0) = new_x s = 1の場合、new_x = floor ( x / p ) // C(x,1) = new_x          
         

の場合、これは標準的なバイナリ システム (0 と 1 が反転したもの) に相当し、異なる の場合、これはこの特定の確率分布に最適になります。たとえば、 の場合、これらの式は の小さな値に対する表になります。 ${\displaystyle p=1/2}$${\displaystyle p}$${\displaystyle p=0.3}$${\displaystyle x}$

記号は、密度 の自然数のサブセットに対応しており、この場合は位置 です。 として、これらの位置は 3 または 4 ずつ増加します。ここでは、記号のパターンが 10 位置ごとに繰り返されるからです。 ${\displaystyle s=1}$${\displaystyle p=0.3}$${\displaystyle \{0,3,6,10,13,16,20,23,26,\ldots \}}$${\displaystyle 1/4<0.3<1/3}$${\displaystyle p=3/10}$

コーディングは、与えられた記号 に対応する行を取得し、この行で与えられた を選択することで見つけることができます。すると、一番上の行は を提供します。たとえば、中央の行から一番上の行までです。 ${\displaystyle C(x,s)}$${\displaystyle s}$${\displaystyle x}$${\displaystyle C(x,s)}$${\displaystyle C(7,0)=11}$

から始まるシーケンス '0100' をエンコードするとします。まず に移動し、次にに移動し、次にに移動し、最後に に移動します。この最後の に対してデコード関数を使用すると、シンボル シーケンスを取得できます。この目的のためにテーブルを使用すると、最初の行で列が決定され、次に空でない行と書き込まれた値によって対応すると が決定されます。 ${\displaystyle x=1}$${\displaystyle s=0}$${\displaystyle x=2}$${\displaystyle s=1}$${\displaystyle x=6}$${\displaystyle s=0}$${\displaystyle x=9}$${\displaystyle s=0}$${\displaystyle x=14}$${\displaystyle D(x')}$${\displaystyle x}$${\displaystyle x}$${\displaystyle s}$${\displaystyle x}$

範囲バリアントも算術式を使用しますが、大きなアルファベットでの演算が可能です。直感的に言えば、自然数の集合をサイズの範囲に分割し、それぞれを同じ方法で、想定される確率分布によって与えられた割合のサブ範囲に分割します。 ${\displaystyle 2^{n}}$

まず、確率分布を分母に量子化します。ここで、nはいくつかの自然数 (サブ範囲のサイズ) に対して選択されます (通常 8 ～ 12 ビット) 。${\displaystyle 2^{n}}$${\displaystyle p_{s}\approx f[s]/2^{n}}$${\displaystyle f[s]}$

と累積分布関数 を表します。${\displaystyle {\text{mask}}=2^{n}-1}$

${\displaystyle \operatorname {CDF} [s]=\sum _{i<s}f[i]=f[0]+\cdots +f[s-1].}$

ここで、 関数は、現在のシンボルの確率が式の値に含まれていないという点で、真のCDFではないことに注意してください。代わりに、 はすべての前のシンボルの合計確率を表します。例: の通常の定義の代わりに、前のシンボルがないため、 として評価されます。CDF[s]CDF[s]CDF[0] = f[0]CDF[0] = 0

機能を表す（通常は表形式） ${\displaystyle y\in [0,2^{n}-1]}$

シンボル( y ) = sであり、CDF [ s ] <= y < CDF [ s + 1 ]となる。           

現在のコーディング関数は次のとおりです。

C ( x , s ) = ( floor ( x / f [ s ]) << n ) + ( x % f [ s ]) + CDF [ s ]            

デコード:s = symbol(x & mask)

D ( x ) = ( f [ s ] * ( x >> n ) + ( x &マスク) - CDF [ s ], s )              

この方法では、シンボルのシーケンスを大きな自然数xにエンコードできます。大きな数の演算を使用しないようにするために、実際にはストリームバリアントが使用されます。これは、再正規化によって、 xの最下位ビットをビットストリームに送信したり、ビットストリームから送信したりします (通常、Lとb は2 の累乗です)。 ${\displaystyle x\in [L,b\cdot L-1]}$

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

( x < ( 1 << 16 ))の場合、 x = ( x << 16 ) + read16bits ()           

tANS バリアントは、 の全体的な動作 (再正規化を含む) をテーブルに格納し、乗算の必要性を回避する有限状態マシンを生成します。 ${\displaystyle x\in [L,2L-1]}$

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

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

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

s = ReadSymbol (); nbBits = ( x + ns [ s ]) >> r ; // 再正規化のビット数writeBits ( x , nbBits ); // 最下位ビットをビットストリームに送信x = encodingTable [ start [ s ] + ( x >> nbBits )];  
        
   
      

特定の tANS コーディングは、各位置にシンボルを割り当てることによって決定されます。シンボルの出現回数は、想定される確率に比例する必要があります。たとえば、Pr(a)=3/8、Pr(b)=1/8、Pr(c)=2/8、Pr(d)=2/8 の確率分布に対して、「abdacdac」割り当てを選択できます。シンボルが 2 の累乗の長さの範囲で割り当てられると、ハフマン コーディングが得られます。たとえば、tANS に対して「aaaabcdd」シンボル割り当てで、a->0、b->100、c->101、d->11 プレフィックス コードが得られます。 ${\displaystyle [L,2L-1]}$

ハフマン符号化に関しては、tANS の確率分布を変更するのに比較的コストがかかるため、主に静的な状況で使用され、通常はLempel-Ziv方式 (ZSTD、LZFSE など) が使用されます。この場合、ファイルはブロックに分割され、各ブロックのシンボル頻度が個別にカウントされ、近似 (量子化) 後にブロック ヘッダーに書き込まれ、tANS の静的確率分布として使用されます。

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

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

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

斬新なANSアルゴリズムとその変種であるtANSとrANSの作者は、利他的な理由から、自分の研究成果をパブリックドメインで自由に利用できるようにすることを特に意図していました。彼はそれらから利益を得ようとはせず、それらが「法的な地雷原」になったり、他者によって制限されたり、利益を得たりしないようにするための措置を講じました。2015年に、Googleは「混合ブールトークンANS係数コーディング」の米国特許、その後世界中で特許を公開しました。^[24]当時、ドゥダ教授はGoogleからビデオ圧縮の支援を依頼されていたため、この分野に精通しており、元の作者の支援を受けていました。

ドゥダ氏は、グーグルの特許意図を（偶然に）知ったことに不満だった。なぜなら、彼は特許をパブリックドメインにしたいと明確に考えており、特にその点に関してグーグルを支援していたからだ。その後、ドゥダ氏は米国特許庁に第三者申請^[25]を提出し、拒絶を求めた。USPTOは2018年にその申請を拒絶し、グーグルはその後特許を放棄した^{[26] 。}

2019年6月、マイクロソフトは「範囲非対称数体系の符号化および復号化の機能」という特許出願を提出した。^[27] USPTOは2020年10月27日にこの出願の最終拒絶を発表した。しかし、2021年3月2日、マイクロソフトは「出願人は拒絶に敬意を表して異議を唱えます」と記載したUSPTOへの説明文書を提出し、^[28]「最終検討後パイロット2.0」プログラムの下で最終拒絶を覆そうとした。^[29]再検討後、USPTOは2022年1月25日にこの出願を認可した。^[30]

• エントロピー符号化
• ハフマン符号化
• 算術符号化
• 範囲エンコーディング
• Zstandard Facebook コンプレッサー
• LZFSE Apple コンプレッサー

• 非対称数値システムエントロピー符号化のための高スループットハードウェアアーキテクチャ SM Najmabadi、Z. Wang、Y. Baroud、S. Simon、ISPA 2015
• 新世代エントロピー コーダ Yann Collet による tANS の有限状態エントロピー (FSE) 実装
• rygorous/ryg_rans Fabian Giesen による rANS の実装
• jkbonfield/rans_static James K. Bonfield による rANS と算術コーディングの高速実装
• facebook/zstd Facebook Zstandardコンプレッサー (Yann Collet 著、 LZ4の作者)
• LZFSE Apple Inc.のLZFSEコンプレッサー (LZ+FSE)
• CRAM 3.0 DNA コンプレッサー (1 rANS オーダー) ( SAMtoolsの一部) 、European Bioinformatics Institute製
• [1] Google VP10の実装
• [2] Google WebPの実装
• [3] Google Draco 3D圧縮ライブラリ
• aom_dsp - aom - Google の Git によるAlliance for Open Mediaの実装
• 非対称数値システムを使用したデータ圧縮 - Wolfram デモンストレーション プロジェクト Wolfram デモンストレーション プロジェクト
• GST: GPU デコード可能な超圧縮テクスチャ GST: GPU デコード可能な超圧縮テクスチャ
• A. Haecky、C. McAnlis 著『圧縮を理解する』