tek1​/adv2

tek1の続き

• tek1～tek3で（将来的には）利用可能な補助バッファ利用の展開について
  • tek3ではすでに実装済み

補助バッファ

• いきさつと原理
  • tek1/tek2がBMPの圧縮に際して思いがけずよい傾向を示しました。それで非常に気をよくして、JPEGに勝てる方法はないものかと（もちろんあるわけないのですが）あれこれ考えていたら、以前ディスクイメージ圧縮の際にFATの部分が圧縮しにくそうで、これをどうにかしたいと考えていて、なかなか面白そうなアイデアを持っていたのを思い出しました。
  • たとえば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割しか減らせていないわけです。
  • 補助バッファを使った圧縮では、まずこのデータ列を次のように解析します。

    00 00 01 00 02 00 03 00 04 00 05 00 06 00 07 00
                            ↓
    00 00 [01 00 01 00 01 00 01 00 01 00 01 00 01 00]

  • []でくくった部分は、2バイト前との差分です。これはいかにも簡単に圧縮できそうな雰囲気です。そしてこの差分値のデータが補助バッファの中身そのものです。差分はそれぞれバイト単位でとって、繰り下がりのことは考えません。そのせいで多少損をすることもあるでしょうが、この辺をうまくやろうとすると複雑になりすぎるのでやりません。
  • 補助バッファを利用する場合、フォーマットにはデータのどの範囲が差分による圧縮なのかの情報が含まれます。範囲とともにどれだけ前との差分であるかも記録されています。そして展開ルーチンは差分情報を補助バッファ内に展開し、その差分値を使って本データを復元します。
  • FAT12に対しても、ちゃんと効果があります。この場合、差分は3バイト前との間でとります。

    02 30 00 04 50 00 06 70 00 08 90 00 ...
                    ↓
    02 30 00 [02 20 00 02 20 00 02 20 00 ...]

  • 24bitカラーのBMPの場合も、3バイト前の差分にすればx方向のグラデーションに対して小さな差分値がたくさん得られるでしょう（もしくはFFやFEなどの大きな差分値）。xのドット数の3倍の前の差分にすれば、y方向のグラデーションにも対応できます。
  • tek2では差分値に対しても出現頻度にあわせてビット長を調節します（本データと差分値とでは統計上別々に扱われ、符号寿命も独立に存在する）。これによりグラデーションが非線形でスライド辞書法による恩恵がなくても結構小さくできることが予想されます。そんなわけでもしかしたら、WAVファイルに適用したときはADPCMに近い圧縮率にはなるかもしれません。tek1やtek3では残念ながらこのような効果は一切期待できません。
    • ということでせいぜいADPCMレベルであって、結局不可逆圧縮のMP3やJPEGに追いつける見込みがないことに変わりはない。見分けられない、聞き分けられないレベルの劣化すらないということだけがせいぜいのなぐさめ。
  • 本質的にはスライド辞書法のままなので、展開速度はほとんど変わりません。しかし補助バッファの分だけ（補助バッファをスライド辞書で参照する分だけ）追加のメモリが必要です。
  • このような仕組みはテキストや実行バイナリにはほとんど効果がありません。たとえば「OSASK」の語のあとに「PTBTL」などという語が現れることはまずなくて、結局普通のコピーだけで十分に用が足りるからです。実行バイナリについてはコード部分には効果がないですが、データ部分にこの手の圧縮が有効なデータテーブルを持つ場合はありうるので、そこでは効果を発揮できます。ジャンプテーブルのように、値そのものよりも差分をとるほうが値が小さくまとめやすい場合とかにも効果があるかもしれません。
  • tek圧縮には、データファイルの構造を単純化させてプログラマの負担を減らすということもあり、テキストや実行バイナリにはあまり効かないなどの好き嫌いがあっても、このような仕組みはいれてもいいと考えました。もしこれがなければ、プログラマはこの手のtek圧縮が効きにくいデータに対して、自前で加工して圧縮しやすいフォーマットに改良する努力をすることになるかもしれません。そういう努力を否定するわけではありませんが、汎用的に利用できそうなこういう簡単な努力については、tek側で一括で面倒を見てあげましょう、とそういうわけです。
    • 結局のところ、KHBIOSでディスクイメージを扱うことが念頭にあって、ディスクイメージは結局FAT系が一番多くなってしまうんだろうなあという想像があって、そうなるとやっかいなFAT部分をどうにかしたいという、それだけのことが決め手だったりする（笑）。
  • なおtek3で実験したところ、 00 01 02 03 ... FE FF という内容の256バイトのファイルを、29バイトにできました（18バイトのOSACMPヘッダ込みで29バイト、正味データは11バイトということ）。
  • 0000～FFFFの128KBのファイルなら40バイトになりました（19+21）。

こめんと欄