5: 2004-10-08 (金) 18:18:05 |
現: 2024-01-08 (月) 12:59:04 k-tan |
- | * 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ビットを要します。これはあたりまえの結果で、とりあえず不思議はありません。 |
| -本当はここから算術圧縮やその改良型であるところのレンジコーダを解説するべきなのですが、そういう高度なことは他のページのほうが詳しいですし、ここではそれを読みたくない(理解したくない)という人がなんとなく雰囲気をつかんでもらうことを意図しているので、他の(いいかげんな)説明で行きます。 | | -本当はここから算術圧縮やその改良型であるところのレンジコーダを解説するべきなのですが、そういう高度なことは他のページのほうが詳しいですし、ここではそれを読みたくない(理解したくない)という人がなんとなく雰囲気をつかんでもらうことを意図しているので、他の(いいかげんな)説明で行きます。 |
| | | |
- | *** 手法は違うけど、分かりやすそうな考えかた | + | *** 手法は違うけど、分かりやすそうな考えかた [#u0298858] |
| -算術圧縮やレンジコーダの説明抜きで、1ビットをより少ないビットで出力する例を紹介します。これを読めば、きっとなんとなく分かったつもりにはなれます。 | | -算術圧縮やレンジコーダの説明抜きで、1ビットをより少ないビットで出力する例を紹介します。これを読めば、きっとなんとなく分かったつもりにはなれます。 |
| -まずここで、魔法のテーブルを考えます。 | | -まずここで、魔法のテーブルを考えます。 |
| -と出力します(後ろには適当に0を補った)。これなら24ビットを18ビットで出力できたことになります。 | | -と出力します(後ろには適当に0を補った)。これなら24ビットを18ビットで出力できたことになります。 |
| -この例ですと、"1"を出力するのに3bit要しますが、"0"は最小で0.429ビットで出力できています。これが1ビットをより少ないビットで出力できるという分かりやすい例だと思います。 | | -この例ですと、"1"を出力するのに3bit要しますが、"0"は最小で0.429ビットで出力できています。これが1ビットをより少ないビットで出力できるという分かりやすい例だと思います。 |
- | -ちなみに''レンジコーダのほうがもっと柔軟で拡張性のある考え方''ですが、とにかくビットの出現頻度の偏(かたよ)りを利用して1ビットを1ビット未満の長さで出すという発想は同じなのです。つまり、これはレンジコーダのアルゴリズムとは''全く別である''ことを忘れないでください。 | + | -ちなみに''レンジコーダのほうがもっと柔軟で拡張性のある考え方''ですが、とにかくビットの出現頻度の偏(かたよ)りを利用して1ビットを1ビット未満の長さで出すという発想は同じなのです。でも、これはレンジコーダのアルゴリズムとは''全く別である''ことを忘れないでください。 |
| | | |
- | *** こんな1ビット単位のレンジコーダで縮むのか | + | *** こんな1ビット単位のレンジコーダで縮むのか [#dbe98605] |
| -ここまでの話で推測できるように、ビットが"0"か"1"に偏(かたよ)ってないと、レンジコーダによる圧縮は効きません。偏りが無い場合のテーブルは、 | | -ここまでの話で推測できるように、ビットが"0"か"1"に偏(かたよ)ってないと、レンジコーダによる圧縮は効きません。偏りが無い場合のテーブルは、 |
| |デコード|0|1| | | |デコード|0|1| |
| -理解を助けるために例を出します。たとえば、もし、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が来そうだとか、そういう性質を、ビットの偏りに反映させたいと考えます。 |
| -他にも-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"の長さの比をどうするか決めています。そしてこの計算を軽くするために、多少の精度を犠牲にしている部分があります。 |
| -tek5ではこれをやめて少しくらい計算が重くなってもいいので精度よく計算できるモードがあります。しかしもちろんこれはオフにすることもできます。どうしてかというと、不正確さがたまたま圧縮に有利になることがありますし、圧縮率よりも速度がほしい時だってありうるからです。 | | -tek5ではこれをやめて少しくらい計算が重くなってもいいので精度よく計算できるモードがあります。しかしもちろんこれはオフにすることもできます。どうしてかというと、不正確さがたまたま圧縮に有利になることがありますし、圧縮率よりも速度がほしい時だってありうるからです。 |
| -またLZMAやstk5では、"0"と"1"の出現比が1:1000よりも極端になった場合を扱えず、常に1:1000くらいとして近似しています。これは実用上十分な場合もありますが、先の0x00と0xffのときのように、あるビットに関しては完全にどちらかしか出ない、という場合もありえます。これはまさに比が0:1の場合で、これを1:1000で近似するのはそれなりに損です。ということで、tek5ではこの比を1:10000くらいまで対応できるようになっています。 | | -また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かもしれない。 | + | --この1:1000や1:10000という数字は間違っている気がしてきた。が、とにかくtek5ではより極端な比が扱えるようになったことはまちがいない。1:275と、1:726810かもしれない。 |
| -LZMAやstk5では、過去のビット列から出現比を予想する場合、どのくらい速く新しい傾向に追従できるようにするか、を決めるパラメータが固定されています。これは結構有害で、このせいで"0"と"1"が交互に来る場合などでは無圧縮よりも長くなってしまうという問題がありました。ということで、このパラメータを可変にして、全く追従しなかったり、LZMAくらいで追従したり、むしろそれよりも速く追従したりを選択できるようになっています。 | | -LZMAやstk5では、過去のビット列から出現比を予想する場合、どのくらい速く新しい傾向に追従できるようにするか、を決めるパラメータが固定されています。これは結構有害で、このせいで"0"と"1"が交互に来る場合などでは無圧縮よりも長くなってしまうという問題がありました。ということで、このパラメータを可変にして、全く追従しなかったり、LZMAくらいで追従したり、むしろそれよりも速く追従したりを選択できるようになっています。 |
| -これらの設定はすべてファイルの途中で何度でも変更可能です。アーカイブなど、ファイルの途中で統計的傾向がどんどん変わるものでは都合がいいでしょう。 | | -これらの設定はすべてファイルの途中で何度でも変更可能です。アーカイブなど、ファイルの途中で統計的傾向がどんどん変わるものでは都合がいいでしょう。 |
| -これらのすべてについて、圧縮率の改善効果があるということが確認されています。 | | -これらのすべてについて、圧縮率の改善効果があるということが確認されています。 |
| | | |
- | *** おまけ | + | *** おまけ [#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に変換できる。拡張モードではもっと極端な比率も可能。 |
| -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 |