この記事は、クリエイティブ・コモンズ・表示・継承ライセンス3.0のもとで公表されたウィキペディアの項目「Asymmetric_numeral_systems」を素材として二次利用しています。
- [前回] introduction
- [前回] Entropy coding
- [前回] Basic concepts of ANS
- [前回] Uniform binary variant(uABS)
- [前回]Range variants(rANS) and streaming
- Tabled variant(tANS)
- Remark
tANS
tANS variant は、x\in [L,2L-1]$に対して、乗算を必要としない有限状態マシンに基づいたtableを用いる（renormalizationを含む）全体の振る舞いである。
最終的には、decoding loopのステップは以下のように表現できる。
t = decodingTable(x);
x = t.newX + readBits(t.nbBits); //state transition
writeSymbol(t.symbol); //decoded symbol
encoding loopのステップは以下のように表現される。
s = ReadSymbol();
nbBits = (x + ns[s]) >> r; // # of bits for renormalization
writeBits(x, nbBits); // send the least significant bits to bitstream
x = encodingTable[start[s] + (x >> nbBits)];
特定のtANS codingは、それぞれ synbolが$[L,2L-1]$の位置に配置されることが決定される、ｓｐれらの実装の数値は、与えられた頻度の割合に応じる。例えば、"abcacdac"を、Pr(a)=3/8, Pr(b)=1/8, Pr(c)=2/8, Pr(d)=2/8 の密度分布でアサインする場合を考える。もしシンボルが2のべき乗の範囲にアサインされるならば、それはハフマン符号と同じものが得られる。例えば、a->0,b->100,c->101,d->11 prefix codeが、"aaaabcdd" symbol assignmentのtANSでもまた与えられる。
訳者コメント
つまり、こちらはテーブルを利用することによって、乗算とかfloor演算とかを省けるようにしたバージョンですね。
Remark
ハフマン符号化では、tANSの密度分布を変化させる事が比較的コストとなっており、そのために静的な状況で主に使われていた、一般的には例えばいくつかのLempel-Ziv schemeと共に（ZSTD,LZFSE)。この場合、ファイルはいくつかのブロックに分割され、それぞれのsymbol 出現は独立してカウントされ、ブロックヘッダーに、tANSの密度分布で静的に使うために、概算値（量子化した値）が書き込まれていた。
対照的に、rANSはrange codingのより高速な置き換えになりうる（CRAM,LZNA,Draco,AV1)。掛け算を必要とするが、メモリ効率が良く、動的に適切な密度分布の推定を行う事ができる。
ANSの符号化、復号化は、それぞれ反対方向の処理となる、それはsymbolsのstackを作る。これによる不便性は一般的に、復号化を順番に処理しようとしたときには符号化する際に逆方向に処理されることにある。マルコフモデルのように文脈が独立しているならば、符号化器は復号よりも遅い見通しのコンテキストを必要としている。適応性の観点でいえば、符号化器は、でこーたが利用しバッファに保存する推定される確率を発見する前方向で処理するべきである。それによて、バッファに保持された確率を逆方向に用いる事ができる。
符号化の最終ステージは、でコードの開始に必要とされる、それは、圧縮されたファイルに保持するために必要になるためである。このコストはencoderの初期状態に関する情報を保持するために必要とされる。例えば、最初が"10000"で開始する代わりに、"1****"状態から開始した場合、""は更なる状態のbitを保持しており、最終的にでコードしたときにそれと関連付けられるはずである。言い換えるならば、この状態は正しい状態で符号化が開始された場合のチェックサムとして利用する事でき、でコード処理の最終状態が正しくなったかどうかを判断することができる。