6: 2004-10-08 (金) 18:18:05 [6] | 現: 2024-01-08 (月) 12:59:04 k-tan[7] [8] | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | * tek5で使われているレンジコーダの効果を紹介するページ | + | TITLE:x |
+ | * tek5で使われているレンジコーダの効果を紹介するページ [#f57aff38] | ||
-(by [[K]], 2004.09.19) | -(by [[K]], 2004.09.19) | ||
-l2d3とかtek0とかUC0とかは(まあ)分かるけど、レンジコーダってなによ、どうしてそんなもので小さくなるのよ、ってたまに聞かれるので、適当に説明。 | -l2d3とかtek0とかUC0とかは(まあ)分かるけど、レンジコーダってなによ、どうしてそんなもので小さくなるのよ、ってたまに聞かれるので、適当に説明。 | ||
- | *** 非常に大雑把な説明 | + | *** 非常に大雑把な説明 [#a4eecf9e] |
-どんなデータもビットの集まりです。だから1ビットを出力するのに平均0.5ビットしか要しなければ、データは半分にできます。そんなうまい話があるもんか、というのは当然の疑問ですが、そんなうまい話があるのです。 | -どんなデータもビットの集まりです。だから1ビットを出力するのに平均0.5ビットしか要しなければ、データは半分にできます。そんなうまい話があるもんか、というのは当然の疑問ですが、そんなうまい話があるのです。 | ||
-たとえば"0"のビットと"1"のビットの割合が半々だったとします。このとき、"0"を出力するのに1ビット要して、"1"を出力するのにもやはり1ビットを要します。これはあたりまえの結果で、とりあえず不思議はありません。 | -たとえば"0"のビットと"1"のビットの割合が半々だったとします。このとき、"0"を出力するのに1ビット要して、"1"を出力するのにもやはり1ビットを要します。これはあたりまえの結果で、とりあえず不思議はありません。 | ||
Line 9: | Line 10: | ||
-本当はここから算術圧縮やその改良型であるところのレンジコーダを解説するべきなのですが、そういう高度なことは他のページのほうが詳しいですし、ここではそれを読みたくない(理解したくない)という人がなんとなく雰囲気をつかんでもらうことを意図しているので、他の(いいかげんな)説明で行きます。 | -本当はここから算術圧縮やその改良型であるところのレンジコーダを解説するべきなのですが、そういう高度なことは他のページのほうが詳しいですし、ここではそれを読みたくない(理解したくない)という人がなんとなく雰囲気をつかんでもらうことを意図しているので、他の(いいかげんな)説明で行きます。 | ||
- | *** 手法は違うけど、分かりやすそうな考えかた | + | *** 手法は違うけど、分かりやすそうな考えかた [#u0298858] |
-算術圧縮やレンジコーダの説明抜きで、1ビットをより少ないビットで出力する例を紹介します。これを読めば、きっとなんとなく分かったつもりにはなれます。 | -算術圧縮やレンジコーダの説明抜きで、1ビットをより少ないビットで出力する例を紹介します。これを読めば、きっとなんとなく分かったつもりにはなれます。 | ||
-まずここで、魔法のテーブルを考えます。 | -まずここで、魔法のテーブルを考えます。 | ||
Line 22: | Line 23: | ||
-ちなみに''レンジコーダのほうがもっと柔軟で拡張性のある考え方''ですが、とにかくビットの出現頻度の偏(かたよ)りを利用して1ビットを1ビット未満の長さで出すという発想は同じなのです。でも、これはレンジコーダのアルゴリズムとは''全く別である''ことを忘れないでください。 | -ちなみに''レンジコーダのほうがもっと柔軟で拡張性のある考え方''ですが、とにかくビットの出現頻度の偏(かたよ)りを利用して1ビットを1ビット未満の長さで出すという発想は同じなのです。でも、これはレンジコーダのアルゴリズムとは''全く別である''ことを忘れないでください。 | ||
- | *** こんな1ビット単位のレンジコーダで縮むのか | + | *** こんな1ビット単位のレンジコーダで縮むのか [#dbe98605] |
-ここまでの話で推測できるように、ビットが"0"か"1"に偏(かたよ)ってないと、レンジコーダによる圧縮は効きません。偏りが無い場合のテーブルは、 | -ここまでの話で推測できるように、ビットが"0"か"1"に偏(かたよ)ってないと、レンジコーダによる圧縮は効きません。偏りが無い場合のテーブルは、 | ||
|デコード|0|1| | |デコード|0|1| | ||
Line 36: | Line 37: | ||
-理解を助けるために例を出します。たとえば、もし、0x00と0xffしかないファイルがあって、しかもこれがランダムで等確率に並んでいたとしましょう。これですと最上位ビットは"0"なのか"1"なのか全く予測できませんし、偏りが無いので平均1bitで出力されます。しかし第2ビットは第1ビットが"0"なら"0"がくるものばかりで極端に偏っていますし、第1ビットが"1"なら"1"が来るものばかりで偏っています。そんなわけで、これは平均0ビットでエンコードされます。第3ビットは、それまでの上位2ビットが"00"と"11"の場合で場合分けされて別々に偏りを出しているので、やはり平均0bitでいけます。これが第8ビットまで続いて、結局、このデータ列は1/8に圧縮できることになります。これはハフマンでやった場合と全く同じです。 | -理解を助けるために例を出します。たとえば、もし、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に圧縮できることになります。これもやはりハフマンと同じです。 | -もう一つ例を出します。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ビットの統計の部分で偏りが出るからです。 | + | -これでとりあえずレンジコーダではハフマンと同程度にはできそうだと分かってもらえたと思いますが、今度はレンジコーダのほうがよくできる例を出します。普通にハフマンを使うと、0x00と0xffのどちらも最低で1ビットを割り振るので、つまり1/8より小さくすることはできません(LHAがそれより小さくできるのはスライド辞書を併用しているからです。もちろんLZMAやtek5もスライド辞書を併用していますが)。しかし、レンジコーダによるエンコードなら、0x00がほとんどで0xffはめったに出ない、なんていう場合、圧縮率を1/8よりもっとずっとよくできます。というのは、第1ビットの統計の部分で偏りが出るからです。 |
- | *** もっと偏りを出すための方法 | + | *** もっと偏りを出すための方法 [#s4ec7e23] |
-LZMAやtek5ではさらに圧縮率を上げるために、つまりもっと偏りを出すために、さらに工夫をしています。 | -LZMAやtek5ではさらに圧縮率を上げるために、つまりもっと偏りを出すために、さらに工夫をしています。 | ||
-たとえば、C言語ソースなどのテキストファイルを考えたとき、アルファベットの直後にはアルファベットが来やすいだろうとか、数字の後ろには数字が来ることが多いだろうとか、タブの後ろにはタブが来そうだとか、0x0dのあとには0x0aが来そうだとか、そういう性質を、ビットの偏りに反映させたいと考えます。 | -たとえば、C言語ソースなどのテキストファイルを考えたとき、アルファベットの直後にはアルファベットが来やすいだろうとか、数字の後ろには数字が来ることが多いだろうとか、タブの後ろにはタブが来そうだとか、0x0dのあとには0x0aが来そうだとか、そういう性質を、ビットの偏りに反映させたいと考えます。 | ||
Line 45: | Line 46: | ||
-他にも-lpというオプションがあり、これはバイト列の何番目かによって統計情報が変えるほうが偏りが出るのではないかというものです。1バイト目は0x00が多いとか、2バイト目は0xaaが多いとか、そういうものです。このような性質が周期的に繰り返されていると仮定して、そのバイト位置のオフセットの下位1ビット(2バイト周期)、下位2ビット(4バイト周期)、下位3ビット(8バイト周期)、下位4ビット(16バイト周期)をビット列の場合分けに利用するというものです。-lc8で-lp4にした場合、ワークエリアはかなり大量に必要になります。 | -他にも-lpというオプションがあり、これはバイト列の何番目かによって統計情報が変えるほうが偏りが出るのではないかというものです。1バイト目は0x00が多いとか、2バイト目は0xaaが多いとか、そういうものです。このような性質が周期的に繰り返されていると仮定して、そのバイト位置のオフセットの下位1ビット(2バイト周期)、下位2ビット(4バイト周期)、下位3ビット(8バイト周期)、下位4ビット(16バイト周期)をビット列の場合分けに利用するというものです。-lc8で-lp4にした場合、ワークエリアはかなり大量に必要になります。 | ||
- | *** LZMAからtek5での改良点 | + | *** LZMAからtek5での改良点 [#c722bbe5] |
-これはLZMAやstk5では行われていない手法で、tek5では行われている(行う予定の)手法です。 | -これはLZMAやstk5では行われていない手法で、tek5では行われている(行う予定の)手法です。 | ||
-LZMAやstk5のレンジコーダでは、1ビットをエンコードするたびに(1ビットをデコードするたびに)それまで出力したビット列を観察し、次にまたビットを出すときに、"0"と"1"の長さの比をどうするか決めています。そしてこの計算を軽くするために、多少の精度を犠牲にしている部分があります。 | -LZMAやstk5のレンジコーダでは、1ビットをエンコードするたびに(1ビットをデコードするたびに)それまで出力したビット列を観察し、次にまたビットを出すときに、"0"と"1"の長さの比をどうするか決めています。そしてこの計算を軽くするために、多少の精度を犠牲にしている部分があります。 | ||
Line 55: | Line 56: | ||
-これらのすべてについて、圧縮率の改善効果があるということが確認されています。 | -これらのすべてについて、圧縮率の改善効果があるということが確認されています。 | ||
- | *** おまけ | + | *** おまけ [#df18fd72] |
//-stk5やLZMAでは、1bitを10.828~0.1665bitに変換できる。・・・違うかも。 | //-stk5やLZMAでは、1bitを10.828~0.1665bitに変換できる。・・・違うかも。 | ||
//-tek5では、1bitを通常モードで15.99976~0.0002441bitに変換できる。拡張モードではもっと極端な比率も可能。 | //-tek5では、1bitを通常モードで15.99976~0.0002441bitに変換できる。拡張モードではもっと極端な比率も可能。 | ||
Line 61: | Line 62: | ||
-stk5やLZMAでは、1bitを6.0458~0.022004bitに変換できる。 | -stk5やLZMAでは、1bitを6.0458~0.022004bitに変換できる。 | ||
-tek5では、1bitを通常モードで16~0.000022014bitに変換できる。拡張モードではもっと極端な比率も可能。 | -tek5では、1bitを通常モードで16~0.000022014bitに変換できる。拡張モードではもっと極端な比率も可能。 | ||
- | * こめんと欄 | + | * こめんと欄 [#r667a8d2] |
#comment | #comment |
(This host) = http://osask.net