初めに

本資料は、Jarek Duda 氏の Asymmetric numeral systems の論文紹介をしようとしていたのですが、脳みそが砕け散ってしまいました。

この記事は、クリエイティブ・コモンズ・表示・継承ライセンス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

Introduction

非対称符号系(ANS)は、Jagiellonlan 大学のJaroslaw(Jarek) Dudaによって提案された、エントロピー符号化手段の１ファミリーである。ANSは、2014年からデータ圧縮に用いられ、従来手法と比べて30倍も高いパフォーマンスをもたらした。ANSは、（同様に密度分布に基づく）算術符号化の圧縮率も備え、処理コストもハフマン符号化と同程度である。Tabled ANS(tANS)では、乗算を使わず、大きなalphabetを処理する事のできる有限状態機械を構築している。

その中で、ANSはFacebook Zstandard compressorで使われてきた（更に、linux kernelの中で使われたり、MIMEやHTTPのためにRFC8478として公開もされた）。また、Apple LZFSE compressorや、Google Draco 3D compressor、PIK Image compressor でも使われてきた。更に、SAMtools utilities内のCRAM DNA compressor や、Dropbox DivANS compressor。更に、Open Media AllianceのAV2 open video codingでも利用も検討されている。

基本的な考え方は、情報を１つの自然数$x$にエンコードすることである。
standard binary number systemでは、
情報としてあるbit $s \in \{ 0,1 \} $ を$x$に加える、すなわち、$x$の後ろに$s$を付け加える場合に、$x' = 2x + s$ という式が与えられる。エントロピー符号器の場合、$Pr(0) = Pr(1) = 1/2$ が与えられた場合に最適となる。ANSは、確率分布 $(p_s) _ {s \in S}$を伴う、シンボルの任意の集合 $ s \in S $に対して一般化する。ANSでは、$x'$は$x$に対して$s$からの情報を追加した結果であるならば、その結果 $x' \approx x \cdot p_s^{-1}$ となる。

同等に、$log_2(x') \approx log_2(x) + log_2(1/p_s ) $ となる。 $log_2(x)$ とは、現在の数$x$に保持された情報のbit数であり、$log_2(1/p_s )$とは、シンボル $s$に含まれるbitの数である。

符号化のルールに基づけば、自然数の集合は、異なるシンボルと関連付けられる分離した部分集合に分割される（奇数と偶数のように、ただし、符号化されるシンボルの確率分布における）。その結果、現在の数$x$に保持されている情報に対して、シンボルsを付け加える場合には、$s$番目の部分集合から$x$番目の状況を表現する、$x' \approx C(x,s) \approx x/p $が得られる。

更に、学習において、別の適用する手段もある。符号化、復号化ステップに対する直接的な数式を扱う(uABSやtANS variants)、あるいは、tableに基づいて振る舞いを決定する(tANS variant)。

繰り込み(renormalization)は、bitstreamから（またはbitstreamへの）、変換処理をする際に、$x$が無限に発散することを防ぐために用いられる。

覚えておくべきこと（訳者メモ）

現在の状態は、$x$ で表現される自然数である。
$x$の末尾に、シンボル$s$を加えたときに得られる次の状態は、$x'$で表現される。
$x' \approx C(x,s) , D(x') = (x,s) $

Entropy coding

1000個の、0と1で構成されるシーケンスを想定する。これには直接保持するためには1000bitを要する。しかし、もし、たった1個の0と999個の1しか含まれていないのであれば、0の位置を表現できれば十分である。つまり、この時には $ \lceil log_2(1000) \rceil
= 10 $ bits の情報がもともとの1000 bitの代替になりうる。

一般的に、長さ $n$ のシーケンスが、ある確率 $ p \in (0,1)$ に基づき、$pn$ 個の0と、$ (1-p)n $ 個の1を含んでいるような場合、組み合わせ(combinations)と呼ばれる。スターリングの近似を利用すると、シャノンのエントロピーと呼ばれる漸近的な値が得られる。

\begin{pmatrix}
n \\
pn 
\end{pmatrix} \approx 2^{nh(p)} \text{for large}\ n\ \text{and}\ h(p) = -p log_2(p) - (1-p)log_2(1-p)

ここで、そのようなシーケンスから１つを選ぶために、$nh(p)$ bits を必要とする。$p=1/2$ であるならば、それは $n$ bits となるが、しかしそれはもっと小さくもなる。例えば、$p=0.11$ であるならば、おおよそ $n/2$ になる。

エントロピー符号は、シンボルのシーケンスを、1シンボルあたりのシャノンのエントロピーのbit数の概算に基づいて、符号化する。例えば、ANSでは組み合わせの計算において直接用いる。ほぼ最適な方法で、固定比率を持つシンボルのすべてのシーケンスに異なる自然数を割り当てる。

組み合わせの符号化と対照的に、データ圧縮においては、確率分布が異なる。この目的のためには、シャノンエントロピーを加重付平均とみなすことができる。確率$p$のシンボルには、情報の$log_2(1/p)$ bitsが含まれている。ANSでは自然数$x$へ情報を符号化するときに、情報の$log_2(x)$ bitsを解釈する。確率$p$のシンボルを情報に付け加えるとき、この情報はコンテンツは、$log_2(x) + log_2(1/p) = log_2(x/p)$ となる。すなわち、二つの情報を含む新しい数値は、$x' \approx x/p$となる。

Basic concepts of ANS

自然数$x$に保持されている情報があり、binary表現によるビットシーケンスを考える。

binary変数$s$から情報を付与する場合に、符号化関数 $x' = C(x,s) = 2x + s $ を用いる事ができる。これは、すべてのbitを左シフトし、最後の位置に新しいbitを配置する。復号関数 $D(x') = ( \lfloor x' / 2 \rfloor, mod(x', 2) ) $は先のxと追加されたbitの関連性から導き出せる。: $D(C(x,s )) = (x,s),\ C(D(x')) = x'$.

初期状態としてx=1から始め、有限bitシーケンスの有効なbitに対して、与えられたシーケンスを含む最終的なxの値を導くためにC関数を用いる。D関数をx=1まで繰り返し実行することで、bitシーケンスを逆順に導き出すことができる。

前述の処理は、uniform(symmetric)な密度分布 $Pr(0)=Pr(1)=1/2$ に適している。ANSでは、any chosen(asymmtric) なシンボルの密度分布 $ Pr(s) = p_s $ に対して一般化をしている。

前述の例における$s$が奇数か偶数かの間で選択されている間、ANSではこの自然数の偶奇分割が、与えられた密度分布 $\{p_s\} $s と関連付けられた分布の部分集合の分割に置き換わる。位置x の値に基づきシンボル$s$の発生が概算値 $xp_s$ を導く。

符号関数 $C(x,s)$ は、シンボル$s$と関連付けられた部分集合を、$x$-thの状況を返す。

分布の仮定は、$ x'=C(x,s) \approx x/p_{s}$ である状態と同じである。自然数xが$log_{2}(x)$ bits informationを含んでいると仮定すると、 $log_{2}(C(x,s)) \approx \log_{2}(x) + log_{2}(1/p_{s}) $　となる。

したがって、符号化器が求めているように、確率のシンボル $ p_{s} $ は、$ \approx log_{2}(1/p_{s}) $ bits の情報を含んで符号化されている。

（後半に続く…）