tek5​/rangecoder :: OSASK計画

tek5で使われているレンジコーダの効果を紹介するページ

• (by K, 2004.09.19)
• l2d3とかtek0とかUC0とかは（まあ）分かるけど、レンジコーダってなによ、どうしてそんなもので小さくなるのよ、ってたまに聞かれるので、適当に説明。

非常に大雑把な説明

• どんなデータもビットの集まりです。だから1ビットを出力するのに平均0.5ビットしか要しなければ、データは半分にできます。そんなうまい話があるもんか、というのは当然の疑問ですが、そんなうまい話があるのです。
• たとえば"0"のビットと"1"のビットの割合が半々だったとします。このとき、"0"を出力するのに1ビット要して、"1"を出力するのにもやはり1ビットを要します。これはあたりまえの結果で、とりあえず不思議はありません。
• 今度は、"0"のビットがやたらと多くて、"1"のビットがあまり出現しないと分かっているとします。このとき、たった1つの"1"を出力するのに3bitも要する代償として、1つの"0"を出力するのに0.5ビットくらいしか使わないでいいということができるのです。
• 本当はここから算術圧縮やその改良型であるところのレンジコーダを解説するべきなのですが、そういう高度なことは他のページのほうが詳しいですし、ここではそれを読みたくない（理解したくない）という人がなんとなく雰囲気をつかんでもらうことを意図しているので、他の（いいかげんな）説明で行きます。

手法は違うけど、分かりやすそうな考えかた

• 算術圧縮やレンジコーダの説明抜きで、1ビットをより少ないビットで出力する例を紹介します。これを読めば、きっとなんとなく分かったつもりにはなれます。
• まずここで、魔法のテーブルを考えます。

  デコード	1	01	001	0001	00001	000001	0000001	0000000
  エンコード	000	001	010	011	100	101	110	111

• このテーブルはこう使います。たとえば 010001100000000000000000 を出力したいときは、
  • 01_0001_1_0000000_0000000_000
• と分解して、
  • 001_011_000_111_111_111
• と出力します（後ろには適当に0を補った）。これなら24ビットを18ビットで出力できたことになります。
• この例ですと、"1"を出力するのに3bit要しますが、"0"は最小で0.429ビットで出力できています。これが1ビットをより少ないビットで出力できるという分かりやすい例だと思います。
• ちなみにレンジコーダのほうがもっと柔軟で拡張性のある考え方ですが、とにかくビットの出現頻度の偏（かたよ）りを利用して1ビットを1ビット未満の長さで出すという発想は同じなのです。でも、これはレンジコーダのアルゴリズムとは全く別であることを忘れないでください。

こんな1ビット単位のレンジコーダで縮むのか

• ここまでの話で推測できるように、ビットが"0"か"1"に偏（かたよ）ってないと、レンジコーダによる圧縮は効きません。偏りが無い場合のテーブルは、

  デコード	0	1
  エンコード	0	1

• にするのが一番いいのですが、しかしこれだと当然ながら圧縮されないのです。しかも偏りはかなり必要です。わずかな偏りではほとんど圧縮できません。
• 実際のファイルをただのビット列だと見たら、偏りはほとんどありません。"0"の個数は"1"の個数と大体同じです。2倍も3倍も違ったりはしません。これじゃあダメなのです。これじゃあハフマンに勝てないのです。ということで、ここからはその辺を解決するためのテクニックを紹介します。これはLZMAやtek5で実際に使われているやり方です。

• まず、データをビットの列ではなく、バイトの列（8bitの列）であると解釈します。そして、そのうちの下位7bitのことは考えないでおいて、上位1bitだけを考えてみます。そうすると、100バイトのファイルならとにかく100bitの列が得られます。
• この100bitですが、もしこれがASCIIテキストなら、そのほとんどが"0"です。他の形式のファイルだとしても、それなりに偏りがでます。まあこの段階で偏りがほとんど無いとしても実は問題ないのですが、とりあえずそれなりに偏りがあるとします。そうだとすれば、これは結構縮みます。これで残りは700bitです。
• 今度は第2ビットを取り出して、それで偏りを・・・と思うかもしれませんが、そうはしません。そもそもこの方法でやっていくと、最下位ビット（第8ビット）なんてほとんど偏りがありません（まあ偶数ばかりとか奇数ばかりのバイナリとかだったら効果があるかもしれませんが）。そんなのはうまくいかないので、第2ビット以降のビット列の考え方は違います。
• それぞれのバイト列について、第1ビットが"0"だった場合と、第1ビットが"1"だった場合とで分類して、それぞれをまとめて、別々に第2ビットを取り出します。これだと、まあまあ偏ります。つまりデコードの場合、まず最上位ビット（第1ビット）をデコードして、次にその最上位ビットに基づいて第2ビットのエンコード用の対応表を選択して、それでデコードするわけです。
• 第3ビットは、第1と第2の結果の両方が使えますので、4通りに分けてから統計を取ります。・・・この調子で行くと最下位ビットは128通りに分けられます。下位のビットほど細かく分類されているので偏ります。それで平均してみると1バイトがたとえば6bitくらいで出力できていて、これでうまくいくわけです。
• 理解を助けるために例を出します。たとえば、もし、0x00と0xffしかないファイルがあって、しかもこれがランダムで等確率に並んでいたとしましょう。これですと最上位ビットは"0"なのか"1"なのか全く予測できませんし、偏りが無いので平均1bitで出力されます。しかし第2ビットは第1ビットが"0"なら"0"がくるものばかりで極端に偏っていますし、第1ビットが"1"なら"1"が来るものばかりで偏っています。そんなわけで、これは平均0ビットでエンコードされます。第3ビットは、それまでの上位2ビットが"00"と"11"の場合で場合分けされて別々に偏りを出しているので、やはり平均0bitでいけます。これが第8ビットまで続いて、結局、このデータ列は1/8に圧縮できることになります。これはハフマンでやった場合と全く同じです。
• もう一つ例を出します。0x01と0x23です。この場合、第1ビットはどちらも"0"ですので極端に偏って平均0ビット。第2ビットも"0"しかないので、平均0ビット。しかし第3ビットは"0"と"1"が半々に出てくるので平均1ビット。第4ビットはそれまでが"000"の場合は"0"だけですし、"001"の場合も"0"だけですので、どちらも極端に偏ってそれぞれ平均0ビット。・・・というふうになって、やっぱりこのデータ列も1/8に圧縮できることになります。これもやはりハフマンと同じです。
• これでとりあえずレンジコーダではハフマンと同程度にはできそうだと分かってもらえたと思いますが、今度はレンジコーダのほうがよくできる例を出します。普通にハフマンを使うと、0x00と0xffのどちらも最低で1ビットを割り振るので、つまり1/8より小さくすることはできません（LHAがそれより小さくできるのはスライド辞書を併用しているからです。もちろんLZMAやtek5もスライド辞書を併用していますが）。しかし、レンジコーダによるエンコードなら、0x00がほとんどで0xffはめったに出ない、なんていう場合、圧縮率を1/8よりもっとずっとよくできます。というのは、第1ビットの統計の部分で偏りが出るからです。

もっと偏りを出すための方法

• LZMAやtek5ではさらに圧縮率を上げるために、つまりもっと偏りを出すために、さらに工夫をしています。
• たとえば、C言語ソースなどのテキストファイルを考えたとき、アルファベットの直後にはアルファベットが来やすいだろうとか、数字の後ろには数字が来ることが多いだろうとか、タブの後ろにはタブが来そうだとか、0x0dのあとには0x0aが来そうだとか、そういう性質を、ビットの偏りに反映させたいと考えます。
• 具体的にはどうするのかというと、ビット列を作る場合に、直前の1バイトがいくつであったかを調べ、それによってまた場合分けしてやろうということです。256通り全てで統計を取ると大変すぎるので、たいていは直前バイトの上位3ビットを取り出して、8通りの状態から第1ビットのデコード方法を決めます（上位3ビットくらいをみれば、直前が数字であったか、アルファベットであったか、タブであったかくらいは分かる）。そして第2ビットは、直前バイトの8通りにさらに先ほどの第1ビットのデコード結果を加えて、16通りでやります。この調子で行くと最後の第8ビットは1024通りにもなりますが、それぞれの状況に応じてビット列がどうなっているかを調べて、エンコード・デコードしていくのです。
• 直前バイトの上位3bitを使うというのはデフォルトでしかなく、-lcオプションで、0～8に調整できます。8だと直前バイトの8bitをすべて使ってやるので、最後の第8ビットは3万通り以上にも分けられていることになります。一方で、-lc0ですと直前バイトの情報は全く使わないことになります。-lc8で直前バイトをフルに使うと、それぞれの状況に応じてのビットの出現頻度統計情報をメモリで管理しなければいけなくなり、それは第8ビットのところで3万通り以上ですし、そのほかの第1～第7ビットの分も入れると6万通りを超えます。そのためエンコード時にもデコード時にもこれらを管理するためのワークエリアが必要になります。
• 他にも-lpというオプションがあり、これはバイト列の何番目かによって統計情報が変えるほうが偏りが出るのではないかというものです。1バイト目は0x00が多いとか、2バイト目は0xaaが多いとか、そういうものです。このような性質が周期的に繰り返されていると仮定して、そのバイト位置のオフセットの下位1ビット（2バイト周期）、下位2ビット（4バイト周期）、下位3ビット（8バイト周期）、下位4ビット（16バイト周期）をビット列の場合分けに利用するというものです。-lc8で-lp4にした場合、ワークエリアはかなり大量に必要になります。

LZMAからtek5での改良点

• これはLZMAやstk5では行われていない手法で、tek5では行われている（行う予定の）手法です。
• LZMAやstk5のレンジコーダでは、1ビットをエンコードするたびに（1ビットをデコードするたびに）それまで出力したビット列を観察し、次にまたビットを出すときに、"0"と"1"の長さの比をどうするか決めています。そしてこの計算を軽くするために、多少の精度を犠牲にしている部分があります。
• tek5ではこれをやめて少しくらい計算が重くなってもいいので精度よく計算できるモードがあります。しかしもちろんこれはオフにすることもできます。どうしてかというと、不正確さがたまたま圧縮に有利になることがありますし、圧縮率よりも速度がほしい時だってありうるからです。
• またLZMAやstk5では、"0"と"1"の出現比が1:1000よりも極端になった場合を扱えず、常に1:1000くらいとして近似しています。これは実用上十分な場合もありますが、先の0x00と0xffのときのように、あるビットに関しては完全にどちらかしか出ない、という場合もありえます。これはまさに比が0:1の場合で、これを1:1000で近似するのはそれなりに損です。ということで、tek5ではこの比を1:10000くらいまで対応できるようになっています。
  • この1:1000や1:10000という数字は間違っている気がしてきた。が、とにかくtek5ではより極端な比が扱えるようになったことはまちがいない。1:275と、1:726810かもしれない。
• LZMAやstk5では、過去のビット列から出現比を予想する場合、どのくらい速く新しい傾向に追従できるようにするか、を決めるパラメータが固定されています。これは結構有害で、このせいで"0"と"1"が交互に来る場合などでは無圧縮よりも長くなってしまうという問題がありました。ということで、このパラメータを可変にして、全く追従しなかったり、LZMAくらいで追従したり、むしろそれよりも速く追従したりを選択できるようになっています。
• これらの設定はすべてファイルの途中で何度でも変更可能です。アーカイブなど、ファイルの途中で統計的傾向がどんどん変わるものでは都合がいいでしょう。
• これらのすべてについて、圧縮率の改善効果があるということが確認されています。

おまけ

• stk5やLZMAでは、1bitを6.0458～0.022004bitに変換できる。
• tek5では、1bitを通常モードで16～0.000022014bitに変換できる。拡張モードではもっと極端な比率も可能。

こめんと欄