Asymmetric Numeral Systems (ANS, 非対称記数法) を理解することを目指しています。
記事の一覧
- ANSの基本的なアイディア (この記事)
- Range ANS (rANS)
- Streaming rANS (執筆予定)
- Table ANS (tANS) (執筆予定)
はじめに
ANSアルゴリズムは、zip圧縮のような無歪み圧縮アルゴリズムの一つです。アメリカではかなり実装が進んでおり、英語のWeb情報も多いのですが、日本では論文、Webともに情報が少ないです。また、Dudaによる論文がarXivのみで公開されているためか、ジャーナル論文もまだ少ないようです。そのため、アルゴリズムの紹介の記事があっても、英語論文の式をそのままコピーしただけで、理解が進んでいない印象を受けます。
また、ANS圧縮関連の論文を読むと、いきなり$C(s, x)$と$D(x)$の数式が出てきます。これら数式をプログラムに実装することはいちおう可能ですが、結局何をやっているか理解できていないので、プログラムを変更することはできません。
本稿は、ANS圧縮の符号化および復号の仕組みを、具体例を通して状態遷移として理解することを目的とします。私が理解した方法を書いていくので、よく書かれている、Asymmetric Binary Systemsから導入するという形式は用いません。また、ANSの説明で多く見かけられる、復号を先に説明するという手順も用いずに、符号化を説明した後に復号を説明します。
背景
無歪み圧縮の中で、確率を与えてデータをエントロピーまで圧縮できるようなアルゴリズムは、エントロピー符号と呼ばれることが多いです。元々は画像圧縮の界隈で、変換符号化(DCT)やLempel-Ziv圧縮などと区別するために使われていたと思います。
現在、エントロピー圧縮アルゴリズムとしては以下が多く使われています。
-
Huffman符号
1952年にHuffmanによって提案されたアルゴリズムです。有限集合を木符号として表現したときにベストに圧縮できるアルゴリズムです。圧縮率を上げるにはアルファベットサイズを大きくしたり、文脈ごとに符号木を作ったりする他、シンボル単位でなくブロック単位で符号化したりする必要があるのですが、アルファベットサイズを大きくするとメモリが大量に必要となる他、シンボルの経験頻度を更新しながら適応的圧縮を実装しようとするとアルゴリズムが複雑になるといったデメリットがありますが、シンプルなアルゴリズムであることと、符号化および復号が高速であるため、今までも多く使われています。 -
算術符号
1979年ごろ、PascoおよびRissanenによって提案されたアルゴリズムです。シンボルの経験頻度を更新しながら適応的圧縮を実装するという拡張が簡単であるというメリットがありますが、Huffman符号よりは符号化および復号の速度が遅いというデメリットがあります。 -
レンジ符号
算術符号とは独立にMartinによって提案されたアルゴリズムです。算術符号と同じく区間を用いて符号化するアルゴリズムですが、RissanenやLangdonによるIBMの特許成立より前に提案されたアルゴリズムであることから、IBMの特許に抵触しないという話が出てきたことから、2000年代になって多く使われるようになってきました。算術符号との最も大きな違いは、算術符号は0から1までの小数区間を用いていますが、レンジ符号は整数の区間を用いている点です。 -
非対称記数法
2008年ごろからDudaによって提案されているアルゴリズムです。整数計算のみを用いたアルゴリズムであることから、算術符号やレンジ符号の性能を、Huffman符号の符号化・復号速度で実現しているということで、最近多く用いられています。
ANSの基本的なアイディア
ANSの基本的なアイディアは以下のとおりです。
シンボル列を１つの大きな整数に変換する
-
符号化
初期状態の整数値$x_0$を決めて、入力シンボル列$s_1, s_2, \ldots, s_n$を整数値で表される状態の列$x_1, x_2, \ldots, x_n$に変換する。最終状態の整数値$x_n$を入力シンボル列に対する符号語とする。 -
復号
最終状態の整数値$x_n$を入力し、出力シンボル列と状態の列を逆順に順次もとめる。このときシンボル列$s_n, s_{n-1}, \ldots, s_1$が出力される。状態が初期状態$x_0$に戻ったら復号を終了する。
符号化と復号の１ステップは以下のとおりです。
-
符号化の１ステップ
現在の状態が$x_{i-1}$であるとき、シンボル$s_i$が入力されると、状態が$x_i$に更新される。 -
復号の１ステップ
現在の状態が$x_i$であるとき、シンボル$s_i$を出力して、状態が$x_{i-1}$に更新される。
次の記事
参考情報
論文
-
Jarek Duda, "Asymmetric numeral systems," arXiv:0902.0271 https://arxiv.org/abs/0902.0271
-
Jarek Duda, "Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding," arXiv:1311.2540 https://arxiv.org/abs/1311.2540
-
James Townsend, "A tutorial on the range variant of asymmetric numeral systems," arXiv:2001.09186 https://arxiv.org/abs/2001.09186
-
Josef Pieprzyk, Jarek Duda, Marcin Pawlowski, Seyit Camtepe, Arash Mahboubi, Pawel Morawiecki, "Compression Optimality of Asymmetric Numeral Systems," arXiv:2209.02228 https://arxiv.org/abs/2209.02228
-
Ping Ang Hsieh and Ja-Ling Wu, "A Review of the Asymmetric Numeral System and Its Applications to Digital Images," Entropy (Basel). 2022 Mar 7;24(3):375. doi: 10.3390/e24030375 https://pmc.ncbi.nlm.nih.gov/articles/PMC8946946/
Web
-
Streaming Asymmetric Numeral System Explained https://graphallthethings.com/posts/streaming-ans-explained/
-
Understanding ANS coding through examples
https://medium.com/@bredelet/understanding-ans-coding-through-examples-d1bebfc7e076