こんにちは、Eukaryaの矢所です。

今回は3Dモデル圧縮技術に関する連載記事の第2回として、rANSについて取り上げます。

ranged Asymmetric Numerical System

、略してrANSは、エントロピー符号化と呼ばれる文字の確率分布を利用して文字列を圧縮する圧縮アルゴリズムの一種です。

他のエントロピー符号化と比較して、rANSはその速さと圧縮率の高さで知られています。具体的には、ハフマン符号化と同等の速度を実現しつつ、与えられた確率分布に対して最大の圧縮率を達成できることが保証されています。

rANSはポーランドの計算機科学者J. Dudaによって、Asymmetric Numerical Systems（ANS）と呼ばれる新しいエントロピー符号化族に関する一連の論文の一部として2013年に発表されました。rANSは、その計算効率のよさと数学的に保証された最適性から、またたく間に世界で最も広く使用される圧縮アルゴリズムの一つとなりました。

実際にrANSが使われている例としては、例えば以下のようなものがあります。

1. Draco（Googleによる3Dモデルコーデック）
2. JPEG XL、AV1（画像/動画コーデック）
3. Opus（音声コーデック）
4. ZstdおよびLZFSE（MetaおよびAppleによる汎用圧縮アルゴリズム）

また、いくつかのオペレーティングシステムやブラウザなどの基盤システムにも組み込まれていることでも知られており、その普及範囲はもはや計り知れません。まさに今、この記事を表示しているデバイス上でもrANSが動作しているかもしれないーーと言っても過言ではないほど、実はrANSはとても身近なアルゴリズムなのです。

rANSは「3Dモデル圧縮専用技術」というわけではなく、より汎用的な圧縮技術ですが、今回3Dモデル圧縮アルゴリズムの連載にこれを含めているのは、3D圧縮アルゴリズムがrANSコーデックを頻繁に活用しているからです。

例えば、連載の第1回では、メッシュの接続性を特殊な文字列に変換するアルゴリズムであるEdgebreakerアルゴリズムを見てきました。rANSは文字列を圧縮できるため、得られた文字列をrANSコーダーに入力することで、より高い圧縮率を実現できます。さらに、rANSは頂点座標圧縮やテクスチャ座標圧縮に至るまで、幅広く活用されています。

本記事では、rANSアルゴリズムの基礎を解説していきます。

💡 Eukaryaでは、GoogleのDraco 3Dモデル圧縮ライブラリをRustで書き直したdraco-oxideを開発しています。もし興味があればぜひチェックしてみてください!

rANSアルゴリズム

設定と記法

まず、有限な文字の集合$S$を考えて、$S$上に＜で示される順序を固定します（例えば、$S$が英語の小文字アルファベットであればa<b<…<zなど）。さらにこれらのアルファベットの確率分布$p: S \to [0,1]$が与えられているとしましょう。確率分布ですので、$\sum_{s \in S} p(s)=1$を満たします。

しかし、rANSが動作するは整数上ですので、固定された正の整数$M$

に対して、離散確率分布と呼ばれる関数

$P:S \to \N$を次の２つの条件を満たすものとして定義します。

1. $\sum_{s \in S} P(s) = M$。
2. 各$s \in S$について$P(s) \sim p(s)M$。

さらに、$C(s) = \sum_{t\in S:t < s} P(t)$と定義します。$C(s)$を$s$の範囲へのオフセットと呼ぶことにしましょう。これらの設定は、$0$から$M-1$までの整数を$|S|$個の範囲へと分けるという目的があります。

イメージで理解したい方には、図１が参考になると思います。

圧縮

それでは、実際に圧縮の方法について見ていきます。$S$中の文字でできた文字列$(s_1, s_2, \cdots, s_m)$（$m$は整数）を符号化したいとしましょう。まず、初期状態を$X_0=0$と置きます。rANSはこの状態を再帰的に更新することで$X_1, X_2, \cdots$と順に計算していき、最終的に$X_m$を計算します。その$X_m$こそがrANSの出力、つまり圧縮データになります。

各再帰ステップの動作は次の通りです。符号化ステップを表す関数を$E:\Z\times S \to \Z$とすると、符号化ステップは各時刻$i \in \{1,\cdots, m\}$について$X_i = E(X_{i-1},s_i)$と書くことができます（この記事の中では、$s\in S$が固定されている場合、便宜上$X_i = E_s(X_{i-1})$と書くこともあります）。

まず、$X_{i-1}$を$P(s_i)$でユークリッド除算した商$q$と余り$r$を計算します。つまり、次を満たす正の整数$q$と$r<P(s_i)$を求めます。

$$\begin{align} X_{i-1} = P(s_i) q + r. \end{align}$$

次に$X_i$を以下の式で計算します。

$$\begin{align} X_i = E(X_{i-1},s) = q M + C(s_i) + r \end{align}$$

圧縮のステップは以上です。とても単純ですが、何が起こっているかはわかりにくいので、少し解説をします。

値$q$は前の状態$X_{i-1}$の圧縮版を表しています。$q$に$M$をかけているのは、その後に足される数のためにスペースを作るためです。

このことは整数を$M$進法で表現するとわかりやすいです。$M$進法の数に$M$を掛けると各桁が1つずつ左にずれて、最下位の位置に0が挿入されるのがわかると思いますが、こうしてできた数に集合$\{0,…,M−1\}$の中からひとつ数を選んで足したところで、２桁目以上の数は変わりません。最後に足されている$C(s_i) + r$は0以上$M-1$以下なので、この条件を満たしているというわけです。

さて、次の$C(s_i)$ですが、これはどの範囲を使っているのかを覚えておくために記録されています。どの範囲を使っているかがわかれば、どの文字が符号化されたかも後で思い出すことができますね。$r$は(1)の式で使われている通り、解凍時に$q$から$X_{i-1}$を復元するために欠かせない情報ですので、記録されています。

解凍

さて、圧縮によって文字列から１つの巨大な整数$X_m$を作ることに成功しました。しかし、この巨大な整数から一体どのようにして文字列を解凍することができるのでしょうか？この節では解凍の方法を見ていきます。

rANSで符号化されたデータの復号化は、符号化プロセスを逆にたどっていくことによって実現します。これはつまり、最後に符号化された文字が最初に復号化されるということです。

さらに具体的に言えば、$i$個の文字を符号化した後の状態値$X_i$が与えられているとき、まず$s_i$を復元し、次に$X_{i-1}$を計算する、というのが各復号化ステップの概要になります。

ここでも必要な記法を導入します。符号化の場合と同様に、復号化関数を$D:\Z\to\Z\times S$で表します。すなわち、各時刻$i\in\{1,\cdots,m\}$について$D(X_i) = (X_{i-1},s_i)$と書くことができます。

まず$X_i$を$M$でユークリッド除算を行います。つまり、次を満たす正の整数$Q$と$R<M$を計算すします。

$$X_i = M Q + R$$

$R$は$M$より小さい正の整数であるため、$R$を含む範囲を持つ文字$s_i\in S$が存在することがいえます。すなわち、

$$s_{i} = \max \left\{s : C(s) \leq R \right \}$$

という計算をすることで$s_i$を復元することができます。

ちなみにこの計算は、$\{0,1,\cdots,M-1\}$の各値とそれを含む範囲を持つ文字の表を先に計算しておくことで効率的に実装できます。

$s_i$が特定できたら、残りは$X_{i-1}$を計算するのみです。まず、次の等式が成り立つことが解ると思います。

$$\begin{align} R &= C(s_i)+r \\ Q &= q \end{align}$$

ここで$q$と$r$は前の節の符号化関数$E$で定義された値です。等式(3)と(4)を使って等式(1)の変数$q$と$r$を書き換えると、最終的な復号化の式が得られますね。

$$X_{i-1} = P(s_i)Q + R - C(s_i).$$

以上が復号化の１ステップです。復号化のプロセスは、最終的に$X_i = 0$に到達するまで、繰り返し続けられます。そのたびに$s_i$を記録し、最終的に得られる文字列が完全に復号化された文字列になります。

ここで、復号化は符号化とは逆の順序で進むことに注意が必要です。つまり、$(s_1, s_2, ..., s_m)$をこの順序で符号化した場合、シンボルは$(s_m,s_{m-1},\cdots,s_1)$の順序で復号化されるということです。

例

では、簡単な例題を見ていきましょう。

ここでは、図1の設定をそのまま用います。現在までに$X_{5}=691$まで符号化されているとして、ここで6番目の文字として「c」を圧縮してみます。

上記の計算に従うと、$P(c) = 2$、$q = 345$、$r= 1$となることがわかると思います。つまり、$X_6=qM+C(c)+r=3458$が得られます。これだけで圧縮は完了です。

では、$X_6$から$X_5$と文字「c」をどのように復号化できるでしょうか？

$X_6$を$M$で割ると商$Q=q=345$と余り$R=8$を得ます。$R$から文字と余り$r$を復号化するには、図2を参照してください。$C(c) \leq R < C(d)$（具体的には$7\leq 8 < 9$）であるため、$R$は文字「$c$」の範囲内にあるので、ここで「$c$」を復号化できます。

また、$R$は「c」の範囲内で値$1$を持つことがわかる（図のオレンジの部分）ので、$r=1$であることがわかりますね。したがって、$X_{5}=P(c) q + r=691$が得られるというわけです。

ストリーミングrANSアルゴリズム

前の節では、文字列に関するすべての情報を含む巨大な整数を作成することを主なアイデアとするrANSコーデックを紹介しました。

rANSは与えられた確率分布に対して最適なエントロピー符号化を実現することで知られていますが、文字列のサイズが大きくなるにつれて急速に実用的でなくなってしまいます。

というのも、ますます大きくなる整数に対してユークリッド除算を実行する必要があり、ユークリッド除算は整数が何百桁、何千桁と大きくなれば計算がほぼ不可能になってしまうのです。

この問題を解決策として、各状態の値$X_i$を分解して、適度に小さく保つということが考えられます。これは、ストリーミングrANSとよばれる、rANSに少し変更を加えたアルゴリズムによって実現することができます。

この節ではストリーミングrANSについて解説していきます。

ストリーミング符号化

まず、正の整数$k$と$l$を選択します。この選択は完全に自由ですが、選択するにあたってはいくつかの指標があります。

まず$k$は、ストリームに送信する各転送のビット数を示しています。最も単純な実装では$k=1$に設定し、バイトストリームの場合は$k=8$に設定するのが良いでしょう。

$l$は$X_i$をどれだけ小さく保つかを示すアルゴリズムのパラメータであり、$l$の値が高いほどアルゴリズムは遅くなりますが、圧縮効率は向上します。

ここで解説するストリームrANSは、各ステップにおいて状態の値が$lM$と$2^klM-1$の間にあることを保証してくれるアルゴリズムです。つまり、

$$I=\{lM,\cdots,2^k l M-1\}$$

と定義した場合、常に$X_i \in I$となることを保証してくれます。例えば、64-bitの非負整数を用いる場合、$2^klM$が$2^{64}$を超えないようにrANSを設計することは実装においてひとつの重要なポイントであると言えます。

ストリーミングrANSの考え方自体は非常に単純で、各ステップ$i$において、$E(X_{i-1},s)$が範囲$I$から外れそうになるときは状態$X_{i-1}$を$2^k$で割り、余りの$k$数をストリームに出力してしまうことで、$X_i$を常に$I$の内部に保っています。

さて、状態の値が$I$の範囲から外れようとしていることをそもそもどのようにして知ることができるのでしょうか？言い換えれば、どの状態値$X$と文字$s \in S$のとき$E(X,s) \in I$となるのでしょうか？この問に答えるには、次のように定義される集合

$$I_s=E_s^{-1}(I)$$

について詳しく知る必要があります。

この集合を計算するのに役立つ事実として、関数$E_s$が単調増加であることがあげられます。つまり、入力が大きくなればなるほど、出力も大きくなるという性質を持っているのです（これは簡単に確かめることができます）。

この事実さえあれば、$L_s = \min \{L: E_s(L)\geq lM \}$および$H_s = \max\{H:E_s(H)\leq2^klM-1\}$の2つの数さえわかればもう上記の問は解決します。なぜなら、単調性により、$L_s \leq X \leq H_s$を持つ任意の数$X$も$I_s$に含まれることがわかるからです。

では、$L_s$と$H_s$の実際の値は何でしょうか？もしお時間があれば、とてもいい演習になると思いますので、ぜひご自身で計算してみてください！

… どうでしたでしょうか？それでは答え合わせをしていきます。結果は以下のようになります。

$$I_s=\{L_s,\cdots, H_s\} = \{lP(s),\cdots,2^k lP(s)-1\}.$$

$I_s$に対するこのすっきりとした式になるのは、実は$I$はそのように設計されているおかげなのです！

したがって、$s$を符号化しようとするときに状態値が上記の$I_s$の内部にあれば、結果として得られる状態値$X_i$は決してオーバーフローしないことがわかりましたね。

これでいよいよアルゴリズムを説明する準備が整いました。状態$X_{i-1}$が与えられたとき、シンボル$s_i$は次のように符号化することができます。

$$\begin{align} &\text{while } X_{i-1} \not \in I_{s_i} : \\ &\;\;\;\;\text{output } X_{i-1} \mod 2^k \\ &\;\;\;\;X_{i-1} \leftarrow \lfloor X_{i-1} / 2^k \rfloor \\ &X_i = E(s_i,X_{i-1}) \end{align}$$

残る疑問はただ一つです。whileループが有限のステップで終了することをどのように担保できるのでしょうか？$2^k$による除算が$I_{s_i}$を飛び越えてしまう場合は無限ループになってしまいますが、その心配はないのでしょうか？

実は、$2^k$による除算は区間$I_{s_i}$を飛び越ることは決してありません。これも、$I$の設計のおかげです。もし区間$I_{s_i}$を飛び越える状態値が存在するとするならば、$I_{s_i}\subsetneq\{X,\cdots,2^kX\}$を満たす整数$X$が存在しなければならなくなります。これは$lP(s_i)<X \leq lP(s_i)$または$lP(s_i) \leq X < lP(s_i)$を意味しますが、どちらの場合も決して起こり得ないというのは自明なことですよね。これは矛盾となりますから、区間$I_{s_i}$を飛び越えるかもしれないという前述の心配は杞憂であったというわけです。

ストリーミング復号化

普通のrANS同様、復号化は符号化の逆の操作によって行われます。各時刻$i\in\{1,\cdots,m\}$において、前の節で説明した普通のrANS復号化プロセスを使用して、$X_i$から文字$s_i$と$X_{i-1}$を復号化することから始めます。

文字を復号化した後、状態$X_{i-1}$が$I$の下限$kM$を下回る場合、符号化されたビットストリームから追加の$k$ビットを読み込んで$2^kX_{i-1}$に加え、それを新たに$X_{i-1}$とします。つまり、以下のようにアルゴリズムを定義できます。

$$\begin{align} &(X_{i-1},s) = D(X_i)\\ &\text{while } X_{i-1} < kM: \\ &\;\;\;\;X_{i-1} \leftarrow X_{i-1} \cdot 2^n + \text{next $k$ bits from bitstream} \end{align}$$

しかしここでも、符号化中に行われる$k$ビットの読み取りの回数が復号化中の回数と異なり、復号化が失敗するのことがあるのではないかと疑問に思うかもしれません。

特に、$X_i \in I$となったら$k$ビットの読み取りを停止しますが、これは早すぎるということは起きないのでしょうか?もしかしたら、$2^kX_i\in I$でもある可能性はないでしょうか?

実は、これも$I$の設計により、$X$と$2^k X$の両方が$I$に含まれるような整数$X$は存在しないことが保証されています（この事実は上記同様簡単に確かめられるので、演習にご活用ください！）。

これにより、ストリームの読み取り回数が一意に決定されることが保証され、アルゴリズムは前述のような曖昧な状況には遭遇しないのです。

以上です！これで実用的なrANSアルゴリズムが完成しました。

tANSアルゴリズムの概要

最後に、非常に短くではありますが、tANSというrANSと非常に関係の深いアルゴリスムを紹介します。

前の節では、各時刻$i$において状態値$X_i$を特定の範囲に制限するrANSのストリーミング版を見てきました。$E(X,s)$は一対一の写像（単射）であるため、rANS符号化プロセス全体を通して$E(X,s)$に供給される入力は有限個しかありません。

より具体的には、ストリーミングrANSでは、$s \in S$と$X \in \{lP(s),\cdots,2^klP(s)-1\}$に対して$E(X,s)$を定義すれば十分であり、このようなペア$(X,s)$は有限個しかないということです。

tANSアルゴリズム（tabled Asymmetric Numerical System）は、符号化/復号化プロセスの開始時に$E(X,s)$の表を作成することでrANSの速度を向上させる、ANS族の一種です。この表により、ユークリッド除算や整数乗算を含む$E(X,s)$の計算を、ただの表の参照にまで削減できます。

このアルゴリズムの課題は表の作成方法にあります。$E(X,s)$のすべての値を計算することもできますが、これでは$E$の計算を避けることを目的とするtANSの意義が失われてしまいます。

Jarek Dudaの論文[1]は、これらの表の値を明示的に計算することなく$E(X,s)$の表を作成する方法を示していますが、その方法を詳しく説明していたら本記事の範囲を大きく超えてしまいますので、今回はこのあたりで御免を蒙ります。

結論

本記事では、あらゆる圧縮の場面において強力なツールとして使われているrANSとそのストリーミング版について紹介いたしました。

基本的なrANSコーダーは文字の出現確率に基づく最適なエントロピー符号化を実現しますが、そのままでは状態値のサイズが増大することによる実用上の制限に直面します。この問題は、多少の圧縮率とのトレードオフはあるものの、ストリーミングrANSという状態値を制限する仕組みを導入することで完全な解決を見ました。

また、圧縮率と計算複雑性の間で異なるトレードオフを提供するANS族の一種であるtANSについても簡単に触れました。

これらの近代エントロピー符号化技術は、3Dモデル圧縮のみならず、さまざまな場面で現代のIT技術を影から支えている、まさに縁の下の力持ちと言ってよいと思います。本稿が、少しでも多くの方にとって、普段陽の当たらない彼らを知るきっかけになれば幸いです。

では、今回はこれにて。

参照

1. Duda, J. (2013). Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. arXiv preprint arXiv:1311.2540. https://arxiv.org/pdf/1311.2540