こんばんは、川合です。
またもやbim2binのバージョンアップです。しかもまたフォーマット
いじりました。しかしフォーマットについては本質的な改変はなく、主
に"1"と"0"の意味を反転させた程度です。しかも反転させた理由はその
ほうが展開ルーチンをアセンブラで書きやすい場合がある、というだけ
ですが。
今回改良されているのはむしろ圧縮ルーチンのほうで、圧縮率を多少
犠牲にしてよければ、かなり短い時間で圧縮できるようになっています
。さらに、maxdisを変化させてもあまり圧縮時間に影響しなくなったの
で、maxdisを積極的に変更して、圧縮率を大きく改善することもできて
います。
http://k.hideyosi.com/bim2bi4h.lzh (51.8KB)
なお、ちょっとの変更でtek0もl2d3も高速化できますが（共通のルー
チンなので）、今回は高速化していません。できるだけはやくtek1/tek
2への移行を進めてほしいという間接的な意思表示です。
まず、毎度の圧縮表です。
org tek0 tek1 tek2 bz2 rk
hellok1 272 128 125 124 166 208
zero4k 4096 27 26 25 43 100
zero64k 65536 28 28 27 43 108
bim2binc 53792 15091 14474 14067 12903 11608
kdun00b 655360 46246 42098 41411 47306 36736
osaskgo 1973741 1149662 1097475 1092517 1047411 909824
org tek0 tek1 tek2 bz2 rk
hellok1 219.4 103.2 100.8 100.0 133.9 167.7
zero4k 16384 108.0 103.7 100.0 172.0 400.0
zero64k 242726 103.7 107.4 100.0 159.3 400.0
bim2binc 463.4 130.0 124.7 121.2 111.2 100.0
kdun00b 1784.0 125.9 114.6 112.7 128.8 100.0
osaskgo 216.9 126.4 120.6 120.1 115.1 100.0
この結果を出すのに使った圧縮パラメータは、次のとおりです。まず
、どれも一律に全部BS:0を付けました。これはbsiz:8mと同じ意味です
（BS:8mやbsiz:0でも同じ意味）。また、"00"のバイトが大量に連続し
ている部分が多分なさそうなhellok1、bim2binc、osaskgoはclv:5を指
定しました。zero4k、zero64k、kdun00bはclv:4です。また、kdun00bは
MD:512kを指定して、その他はMD:0を指定しました。MDはmaxdisのこと
で、0だと最大の2mを指定したとみなされます。
まず見てすぐに分かるのは、tek2のすばらしいスコアです。例によっ
てライバルたちと比べると、こうなります（今回からgzipにも登場して
もらいました）。
tek1 tek2 lh7 gzip bz2 rk
bim2binc 124.7 121.2 121.5 120.9 111.2 100.0
kdun00b 114.6 112.7 123.7 121.4 128.8 100.0
osaskgo 120.6 120.1 120.8 122.2 115.1 100.0
tek2は3つすべてのファイルでlh7に勝ち、gzipに対してもbim2bincで
負けてはいるものの、osaskgoは大勝しています。またkdun00bの圧縮率
では群を抜いていて、もし遠い将来にブロックソート法（bz2のアルゴ
リズム）と組み合わせたら、非常に強い圧縮フォーマットになれそうな
予感がします（それでもrkが最強であることは揺るぎないのですが）。
さて、BSとMDはそれぞれbsizとmaxdisの省略表記であることは説明し
たので、今度はclvについてです。
今回からclvをもっと細かく分けました。意味は次のとおりです。
clv:0 -- 圧縮率は犠牲にしていいのでとにかく圧縮速度優先。tek1/
tek2においては、これを指定されるともはやUC0符号のパラ
メータの最適化を完全に略し、僕が先日決めた、これでた
いていのものはそれなりに縮むだろうというパラメータを
固定的に利用する。符号パラメータに自由度がないという
点でこれはl2d3的である。圧縮に際しては、最長一致検索
処理以外に時間のかかりそうな処理はない。
clv:1 -- もっとも圧縮率を軽視した「普通」。bim2bin4hではclv指
定を省略すると、clv:1を指定したものとみなされる。tek
1/tek2においては、これを指定されるとUC0符号のパラメ
ータの最適化はするが、寿命はすべて無限大を使う。これ
によりパラメータ最適化のための時間を減らしている。一
般的な使用にあってはこれで十分であろうと思われる。パ
ラメータの自由度はあるが、符号寿命という概念がないと
いう意味でこれはtek0的である。しかしtek0的であるとは
いえ、調整可能な必要なパラメータは多いので、圧縮率は
tek0よりもずっとよい。
clv:2 -- 圧縮率と圧縮速度のバランスをとった「普通」。もし圧縮
時間で問題が出ないのであれば、ぜひおすすめしたいモー
ドである。デフォルト値による符号寿命の利用をするのが
clv:1のと違いである。完全ではないにしても、tek1/tek2
の機能を一通り使っているわけである。
clv:3 -- やや圧縮率を優先した「普通」。clv:2では時間がかかる
のでやらないでいた最低一致長パラメータの最適化をやる
ようになり、さらに符号寿命の最適値を検索するようにな
る。一般にclv:3はclv:2に比べて2〜3倍の時間がかかる。
clv:4 -- 圧縮率をもっとも優先した「普通」。圧縮速度を上げるた
めにパラメータ検索の範囲を絞ってきたが、それを広く解
放する。clv:4はclv:3に比べて、さらに3倍ほどの時間がか
かる。OSASKアプリなどをリリースする際には、このレベル
での圧縮が望ましい。サイズが大きなファイルでは、clv:4
では辛いかもしれないので、clv:3やclv:2でもいいだろう
。
clv:5 -- これは普通に考えられる範囲を超えた圧縮率優先モードで
実はこれがbim2bin4gでの標準モードに匹敵する。clv:5は
clv:4とほとんど変わらないのだが、clv:4では"00"の連続
部分などの、同一バイトの繰り返しに対して圧縮速度が猛
烈に悪くなる（圧縮率には影響はない）という欠陥があり
、そのような場合に遭遇したら適当に手を抜くようになっ
ている。clv:5ではそのような場合でもまじめにやるとい
うだけのことである。同一バイトの繰り返しが（あったと
しても）そう長くは続かないだろうと思われるなら、clv:4
の代わりに、clv:5をおすすめできる。
clv:6 -- これはかなり極端な圧縮率優先モードで、まず使わない。
まず猛烈に時間がかかるのは間違いない。しかもだからと
いって、これで小さくなる可能性がどれほどあるのかとい
うとそれも疑問である。bim2bincでさえ、このモードでは
何日かかるか分かったものではない。
clv:7 -- これはさらに極端な圧縮率優先モードで、当然使わない。
はっきりいって僕が圧縮率改善のための研究用に残してあ
るだけである。
これらでどのくらい圧縮速度が変わるとかというと、たとえばosaskg
oの場合、clv:1だとBS:0、MD:0でもC3-533MHzでも75秒で終わります（
MDをデフォルトの32kにすれば、57秒にまで減る）。しかしclv:5にする
と、これが51分になります。一方hellok1などの小物は、clv:5でも一瞬
で終わります。
clv:1での圧縮速度をもっと上げられないのかというと、実はたぶん
まだ2〜3倍に上げる余地はあると思われます。ただ面倒なのでやってい
ません。またclv:2以上のものについても、パラメータ最適化方法をも
っとまじめに時間をかけて研究すれば、たぶん劇的に速くできそうです
。しかし、いくらなんでもそこまで時間をかけているといつまでたって
も他の開発ができないし、これらの改良は圧縮フォーマットに影響しな
いと思われるので（つまり展開ルーチンは変えなくてよい）、後回しで
も問題はないと考えました。
やっと圧縮速度を気にしないで自由にいじれるようになったMD（
maxdis）ですが、これは大きければそれでいいという場合もある一方、
小さいほうがいい場合もあります。それはそれぞれのファイルでいろい
ろ試してみないとわかりません。ファイルの特性によりけりです。なお
MDパラメータは、展開時に必要になるバッファメモリの量でもあります
（OSASKの場合メモリへの展開が主で、しかも展開結果をそのままバッ
ファとして使ってよいので、MDがいくつであっても消費メモリ量に違い
はありません）。圧縮率を上げたいときのおすすめの方法としては、
clv:2くらいでいろんなMDで圧縮してみて、一番よかった値を見つけて
それでclv:4で仕上げをすることです。なお、BSは2のべきである必要が
ありましたが、MDは2MB以下でありさえすれば、適当な値でかまいませ
ん。10kとか234kとか、お好きにどうぞ。デフォルトは今まで通り、
32kです。BSもデフォルトが32kになっているので、圧縮率を上げたい
場合は、BSも8mにするべきでしょう（BSはどんなファイルでも、大き
ければ大きいほど圧縮率はよい）。BSもMDも圧縮時間にはあまり影響
しません。
なお、clv:1ではどのくらい圧縮率が変わるのかということにも興味
があると思いますので、挙げておきます。
org tek0 tek1 tek2 bz2 rk
hellok1 272 128 127 126 166 208
zero4k 4096 27 26 25 43 100
zero64k 65536 28 28 27 43 108
bim2binc 53792 15091 14553 14271 12903 11608
kdun00b 655360 46246 43263 42902 47306 36736
osaskgo 1973741 1149662 1120099 1120097 1047411 909824
org tek0 tek1 tek2 bz2 rk
bim2binc 463.4 130.0 125.4 122.9 111.2 100.0
kdun00b 1784.0 125.9 117.8 116.8 128.8 100.0
osaskgo 216.9 126.4 123.1 123.1 115.1 100.0
比べやすいように、clv:4、clv:5の結果も再掲します。
org tek0 tek1 tek2 bz2 rk
bim2binc 463.4 130.0 124.7 121.2 111.2 100.0
kdun00b 1784.0 125.9 114.6 112.7 128.8 100.0
osaskgo 216.9 126.4 120.6 120.1 115.1 100.0
結局ファイルによってまちまちですが、clv:1だって今まで常用して
きたtek0よりはずっといいので、そう考えればそう捨てたものではあり
ません。
毎度のOSASKアプリ編です。
tek0 tek1 tek2 tek0→tek2での改善率
helloc4 497 493 489 1.61%
helloc9 176 175 172 2.30%
bballc0 628 612 617 1.75%
bballc2 295 293 292 1.02%
invader2 1699 1672 1672 1.59%
invader5 1258 1243 1236 1.75%
helloc9のtek1が1バイト改善。bballc0ではともに改善したもののtek1
とtek2とで結果が逆転。bballc2のtek2は結果が1バイト改悪。invader2
はともに改善。invader5はともに改悪。
---
僕はワーストの圧縮指数が低ければ低いほど、「汎用」として好まし
いと思っていまして、現在のtek2がlh7やgzipはおろか、bz2に対しても
この観点では優秀な結果を残せていることに満足しています。とくにス
ライド辞書法では定番とされるハフマン符号を使わずにこの結果を出せ
たのは、非常に興味深いと思っています。
しかし、たとえばosaskgoのMD:0（＝2MB）などというのは、lh7や
gzipのスライド辞書バッファサイズを超えており、大きな辞書を使った
から圧縮率がよくなったのは当然と言えなくもありません。また今回圧
縮率を優先するためにすべてBS:0で圧縮していますが、これはtek1/tek
2の特徴であるランダムアクセス特性の改善というメリットがまったく
生きてない状況でもあります。
でもこれらは裏を返せば、単一のフォーマットの範囲で非常に多様な
形式をサポートできている証でもあります。gzipやlh7で、なぜ辞書バッ
ファを2MBまで利用できるようにしなかったのかは分かりませんが、必
要があれば利用できるというtek1などのほうが、フォーマットとしては
いいでしょう（もちろん使わないこともできるのだから）。また必ずラ
ンダムアクセス特性に配慮しなければいけなくなるようなフォーマット
仕様よりは、場合によっては圧縮率も優先できるようなフォーマットの
ほうがいいでしょう。つまりtek1やtek2にはスケーラビリティに優れて
いて、それゆえにさまざまな用途にマッチし、汎用符号の名に恥じない
ものだと思っています。さらに展開速度はとても速く展開ルーチンは単
純で、さらにランダムアクセス特性（部分展開）にまで配慮可能なので
すから、申し分ありません。
懸念されていた圧縮速度についてはとりあえずclv:1を使うというこ
とで問題ないだろうと思っています。これでもtek0よりは十分に小さい
わけですし、展開に時間がかからないというメリットを考えれば、圧縮
率がそれほどよくなくても、許せる状況は少なくないと思います。特に
僕の理想どおり、ほとんどのOSで圧縮ファイルのまま自由に読めるよう
になれば、clv:1の圧縮率であったとしても、使いたいと思う人はいる
でしょう。で、余裕のある人はclv:2〜4を使うと。
なおclv:1で作ったもののほうが展開が速いということはまずありま
せん。むしろ高圧縮で圧縮ファイルのサイズが小さいほうが展開は速い
でしょう。まあ差があったとしても微々たる差だとは思いますが。
またtek1/tek2では、展開速度（？MB/s）は常にほぼ一定です。これ
は結局アルゴリズムらしいアルゴリズムが結局一種類しかないことに起
因します（ファイル特性によって切り替えられるのは、パラメータであ
ってアルゴリズムではない。その辺が7zipなどとは違うわけです）。い
やもちろん単純なバイトコピーが多いほうが速いですが、容量によって
スループットが落ちたりはしません。だから100MBのものの展開に要す
る時間は、単純に1MBの100倍だと考えて問題ありません。
---
さて僕としてはもうbim2binの改良を続ける気はほとんどなくて、
OSASKでのtek1/tek2展開サポートのほうに関心が移っています。今回も
本質的なフォーマットの改変はほとんどやっていませんし、今後ももう
やる予定はないので、bim2bin4はバージョンhがリリース候補版になる
と思います（バグがなければ）。圧縮速度も速くなったことですし、興
味がある人はこれを気にいろいろ圧縮してみて遊んでみてください（
BMP+tek1（もしくはBMP+tek2）は、他の画像圧縮形式に対してどこまで
がんばれているか？とかね）。
せっかくなので一つ僕もやってみました。OSASK ver.4.5の壁紙です
。1024x768x4bppです。とりえあえず可逆圧縮限定です。
非圧縮： 393334
GIF： 13640
圧縮TIF：32088 (LZW圧縮)
PNG： 15563
tek0： 6389
tek1： 5934 (BS:0 MD:0 clv:4 -- 数秒で圧縮完了)
tek2： 5612 (BS:0 MD:0 clv:4 -- 数秒で圧縮完了)
gzip： 6341 (もちろん-9)
lh7： 6395
bz2： 4906 (もちろん-9)
rk： 4344 (もちろん-c -mx3)
率直な印象として、GIFからPNGの結果はあまりにお粗末な気が・・・
。またgzipは、htmlの圧縮にも使われるくらいですから、圧縮したまま
読むという方面でも活躍している圧縮形式であるともいえると思います
。そういう意味でtek1/tek2のライバルだと思いますが、tek1やtek2の
ほうが圧縮率がいいです。rkは圧縮率は高いですがメモリを食いすぎま
すし、bz2はrkを除けば最強ですが、やはり展開速度と癖のなさではtek
1やtek2にかなり利がありそうです。ということで、汎用圧縮形式とし
てはtek1かtek2かbz2かrkがよくて、それ以外は互換性以外の理由では
積極的に使う理由はないかもしれません。そしてこの4つの中でどれ
か一つだけを選べといわれたら、僕はtek1を選ぶでしょう。
また今までGIFからPNGなどの形式が生まれてきたのも（そしてさえな
い圧縮率なのに生き残ってきたのも）、ひとえにgzipやlh7などが、tek
のような「圧縮したまま利用するフォーマット」を追求することなく、
展開時の速度やアルゴリズムの単純さやランダムアクセス性よりも、ひ
たすら圧縮率を追いかけてきたせいでしょう。癖がなくどんな形式との
組み合わせでもほぼ一定の効果が期待できるtek1/tek2によって、この
状況を少しずつ変えていきたいです。
それでは。
--
川合 秀実(KAWAI Hidemi)
OSASK計画代表 / システム設計開発担当
E-mail:kawai !Atmark! osask.jp
Homepage http://osask.jp/