長らくご愛顧いただいたOsask-Wikiでしたが2016/9/30をもって終了・凍結としました。
ページの内容やボタン等に編集可能だった時の名残りが残っておりますが新たなページ設置や内容の変更等はできません。
tek5/rangecoder のバックアップの現在との差分(No.7)
- 差分 を表示
- ソース を表示
- tek5/rangecoder へ行く。
7: 2009-11-17 (火) 12:07:39  |
現: 2024-01-08 (月) 12:59:04 k-tan |
||
|---|---|---|---|
| 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 38: | Line 39: | ||
| -これでとりあえずレンジコーダではハフマンと同程度にはできそうだと分かってもらえたと思いますが、今度はレンジコーダのほうがよくできる例を出します。普通にハフマンを使うと、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 | ||
- tek5/rangecoder のバックアップ一覧
- tek5/rangecoder のバックアップの現在との差分(No. All)
|
Counter: 64,
today: 3,
yesterday: 0
|
ぺージ情報 | 閲覧可 | 編集可 | |||
|---|---|---|---|---|---|---|
| ぺージ名 : | tek5/rangecoder | グループ : | すべての訪問者 | グループ : | すべての訪問者 | |
| ページ作成 : | k-tan | ユーザー : | すべての訪問者 | ユーザー : | すべての訪問者 | |
| ページ別名 : | 未設定 | |||||