長らくご愛顧いただいたOsask-Wikiでしたが2016/9/30をもって終了・凍結としました。
ページの内容やボタン等に編集可能だった時の名残りが残っておりますが新たなページ設置や内容の変更等はできません。
tek5/rangecoder のバックアップ差分(No.7)
- 現在との差分 を表示
- ソース を表示
- tek5/rangecoder へ行く。
6: 2004-10-08 (金) 18:18:05  |
7: 2009-11-17 (火) 12:07:39 |
||
|---|---|---|---|
| Line 36: | Line 36: | ||
| -理解を助けるために例を出します。たとえば、もし、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ビットの統計の部分で偏りが出るからです。 |
| *** もっと偏りを出すための方法 | *** もっと偏りを出すための方法 | ||
- tek5/rangecoder のバックアップ一覧
- tek5/rangecoder のバックアップ差分(No. All)
|
Counter: 62,
today: 1,
yesterday: 0
|
ぺージ情報 | 閲覧可 | 編集可 | |||
|---|---|---|---|---|---|---|
| ぺージ名 : | tek5/rangecoder | グループ : | すべての訪問者 | グループ : | すべての訪問者 | |
| ページ作成 : | k-tan | ユーザー : | すべての訪問者 | ユーザー : | すべての訪問者 | |
| ページ別名 : | 未設定 | |||||