2: 2004-06-11 (金) 04:44:40 |
3: 2004-06-11 (金) 04:44:40 |
| * 補助バッファ | | * 補助バッファ |
| -いきさつと原理 | | -いきさつと原理 |
- | --tek1/tek2がBMPなどの圧縮に際して思いがけずよい傾向を示しました。それで非常に気をよくして、JPEGに勝てる方法はないものかと(もちろんあるわけないのですが)あれこれ考えていたら、以前ディスクイメージ圧縮の際にFATの部分が圧縮しにくそうで、これをどうにかしたいと考えていて、なかなか面白そうなアイデアを持っていたのを思い出しました。 | + | --tek1/tek2がBMPの圧縮に際して思いがけずよい傾向を示しました。それで非常に気をよくして、JPEGに勝てる方法はないものかと(もちろんあるわけないのですが)あれこれ考えていたら、以前ディスクイメージ圧縮の際にFATの部分が圧縮しにくそうで、これをどうにかしたいと考えていて、なかなか面白そうなアイデアを持っていたのを思い出しました。 |
| --たとえばFAT16では 03 00 04 00 05 00 06 00 07 00 08 00 ... みたいな部分がよく出てきます。これをもっと一般的に考えると、2バイトの整数が0x0000~0xFFFFまであって0000からFFFFまで順番に並んだ128KBのデータ(もしくはそれに類するもの)を圧縮できるかということです。 | | --たとえばFAT16では 03 00 04 00 05 00 06 00 07 00 08 00 ... みたいな部分がよく出てきます。これをもっと一般的に考えると、2バイトの整数が0x0000~0xFFFFまであって0000からFFFFまで順番に並んだ128KBのデータ(もしくはそれに類するもの)を圧縮できるかということです。 |
- | --この128KBにおいては、00~FFまでのすべてのバイトの出現率は等しく、また2バイト以上の繰り返し構造は皆無で、まさにtek1/tek2が1バイトも縮められないタイプのデータです。まあtek2では、符号寿命を512に設定してやれば、上位バイト部分に短い符号を割り振って(1bitとか)16bitを9(下位)+1(上位)=10bitにして7割程度には圧縮できるかもしれません。しかしこれでも所詮は7割です。人間が見れば明らかに圧縮できそうな感じのデータなのに、たったの3割しか減らせていないわけです。 | + | --この128KBにおいては、00~FFまでのすべてのバイトの出現比率は等しく、また2バイト以上の繰り返し構造は皆無で、まさにtek1/tek2が1バイトも縮められないタイプのデータです。まあtek2では、符号寿命を512に設定してやれば、上位バイト部分に短い符号を割り振って(1bitとか)16bitを9(下位)+1(上位)=10bitにして7割程度には圧縮できるかもしれません。しかしこれでも所詮は7割です。人間が見れば明らかに圧縮できそうな感じのデータなのに、たったの3割しか減らせていないわけです。 |
| --補助バッファを使った圧縮では、まずこのデータ列を次のように解析します。 | | --補助バッファを使った圧縮では、まずこのデータ列を次のように解析します。 |
| 00 00 01 00 02 00 03 00 04 00 05 00 06 00 07 00 | | 00 00 01 00 02 00 03 00 04 00 05 00 06 00 07 00 |
| 02 30 00 [02 20 00 02 20 00 02 20 00 ...] | | 02 30 00 [02 20 00 02 20 00 02 20 00 ...] |
| --24bitカラーのBMPの場合も、3バイト前の差分にすればx方向のグラデーションに対して小さな差分値がたくさん得られるでしょう(もしくはFFやFEなどの大きな差分値)。xのドット数の3倍の前の差分にすれば、y方向のグラデーションにも対応できます。 | | --24bitカラーのBMPの場合も、3バイト前の差分にすればx方向のグラデーションに対して小さな差分値がたくさん得られるでしょう(もしくはFFやFEなどの大きな差分値)。xのドット数の3倍の前の差分にすれば、y方向のグラデーションにも対応できます。 |
- | --tek2では差分値に対しても出現頻度にあわせてビット長を調節します(本データと差分値とでは統計上別々に扱われ、符号寿命も独立に存在する)。これによりグラデーションが非線形でスライド辞書法による恩恵がなくても結構小さくできることが予想されます。そんなわけでもしかしたら、WAVファイルに適用したときはADPCMに近い圧縮率にはなるかもしれません。tek1やtek3では残念ながらこのような効果は一切期待できません。 | + | --tek2では差分値に対しても出現頻度にあわせてビット長を調節します(本データと差分値とでは統計上別々に扱われ、符号寿命も独立に存在する)。これによりグラデーションが非線形でスライド辞書法による恩恵がなくても結構小さくできることが''予想''されます。そんなわけで''もしかしたら''、WAVファイルに適用したときはADPCMに近い圧縮率にはなるかもしれません。tek1やtek3では残念ながらこのような効果は一切期待できません。 |
| ---ということでせいぜいADPCMレベルであって、結局不可逆圧縮のMP3やJPEGに追いつける見込みがないことに変わりはない。見分けられない、聞き分けられないレベルの劣化すらないということだけがせいぜいのなぐさめ。 | | ---ということでせいぜいADPCMレベルであって、結局不可逆圧縮のMP3やJPEGに追いつける見込みがないことに変わりはない。見分けられない、聞き分けられないレベルの劣化すらないということだけがせいぜいのなぐさめ。 |
| --本質的にはスライド辞書法のままなので、展開速度はほとんど変わりません。しかし補助バッファの分だけ(補助バッファをスライド辞書で参照する分だけ)追加のメモリが必要です。 | | --本質的にはスライド辞書法のままなので、展開速度はほとんど変わりません。しかし補助バッファの分だけ(補助バッファをスライド辞書で参照する分だけ)追加のメモリが必要です。 |