ページへ戻る

− Links

 印刷 

tek1​/adv2 のバックアップ差分(No.1) :: OSASK計画

osaskwiki:tek1/adv2 のバックアップ差分(No.1)
  Next »[4]
1: 2004-06-11 (金) 04:44:40 ソース[5]
Line 1: Line 1:
 +* [[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を1+9=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では残念ながらこのような効果は一切期待できません。
 +--本質的にはスライド辞書法のままなので、展開速度はほとんど変わりません。
 +--このような仕組みはテキストや実行バイナリにはほとんど効果がありません。たとえば「OSASK」の語のあとに「PTBTL」などという語が現れることはまずなくて、結局普通のコピーだけで十分に用が足りるからです。実行バイナリについてはコード部分には効果がないですが、データ部分にこの手の圧縮が有効なデータテーブルを持つ場合はありうるので、そこでは効果を発揮できます。ジャンプテーブルのように、値そのものよりも差分をとるほうが値が小さくまとめやすい場合とかにも効果があるかもしれません。
 +--tek圧縮には、データファイルの構造を単純化させてプログラマの負担を減らすということもあり、テキストや実行バイナリにはあまり効かないなどの好き嫌いがあっても、このような仕組みはいれてもいいと考えました。もしこれがなければ、プログラマはこの手のtek圧縮が効きにくいデータに対して、自前で加工して圧縮しやすいフォーマットに改良する努力をすることになるかもしれません。そういう努力を否定するわけではありませんが、汎用的に利用できそうなこういう簡単な努力については、tek側で一括で面倒を見てあげましょう、とそういうわけです。
 +---結局のところ、KHBIOSでディスクイメージを扱うことが念頭にあって、ディスクイメージは結局FAT系が一番多くなってしまうんだろうなあという想像があって、そうなるとやっかいなFAT部分をどうにかしたいという、それだけのことが決め手だったりする（笑）。
 +
 +* こめんと欄
 +
 +#comment
  Next »[4]
ページ別名: 未設定
ページ作成: ゲスト
サイト管理: lina

Links list

(This host) = http://osask.net

  1. (This host)/modules/osaskwiki/index.php?cmd=backup&pgid=349&age=1&action=nowdiff
  2. (This host)/modules/osaskwiki/index.php?cmd=backup&pgid=349&age=1&action=source
  3. (This host)/modules/osaskwiki/349.html
  4. (This host)/modules/osaskwiki/index.php?cmd=backup&pgid=349&action=diff&age=2
  5. (This host)/modules/osaskwiki/?cmd=backup&pgid=349&action=source&age=1
  6. (This host)/modules/osaskwiki/index.php?cmd=backup&pgid=349
  7. (This host)/modules/osaskwiki/index.php?cmd=backup&action=diff&pgid=349&age=2
  8. (This host)/modules/osaskwiki/index.php?cmd=backup&action=diff&pgid=349&age=3
  9. (This host)/modules/osaskwiki/index.php?cmd=backup&action=diff&pgid=349&age=4
  10. (This host)/modules/osaskwiki/index.php?cmd=backup&action=diff&pgid=349&age=Cur