こんばんは、川合です。
運良く圧縮パラメータ最適化方法を思いつけて、それなりに効果があ
ったので、bim2binをバージョンアップします。
ついでに展開ルーチンのバグを直しました（だから、bim2bin4eで圧
縮したものはもちろんbim2bin4fでも展開できますが、4fで圧縮したも
のの一部は4eで展開できません）。展開ルーチンのバグはASKAで展開
ルーチンを書いているときに発見したものです。
それとbim2bin4eに対して、tek1のフォーマット互換性は保たれてい
ますが、tek2のフォーマット互換性は保たれていません。
http://k.hideyosi.com/bim2bi4f.lzh (38.4KB)
圧縮比較表は次のように更新されました。ブロックサイズなどは前回
と同じ条件ですが、追加で次のオプションをつけています。hellok1〜
zero64kはclv:2、bim2bincとkdun00bはclv:1、osaskgoは追加オプショ
ン無し。
org tek0 tek1 tek2 bz2 rk
hellok1 272 128 126 125 166 208
zero4k 4096 27 25 25 43 100
zero64k 65536 28 27 27 43 108
bim2binc 53792 15091 14556 14152 12903 11608
kdun00b 655360 46246 45651 44453 47306 36736
osaskgo 1973741 1149662 1140715 1129698 1047411 909824
org tek0 tek1 tek2 bz2 rk
hellok1 217.6 102.4 100.8 100.0 132.8 166.4
zero4k 16384 108.0 100.0 100.0 172.0 400.0
zero64k 242726 103.7 100.0 100.0 159.3 400.0
bim2binc 463.4 130.0 125.4 121.9 111.2 100.0
kdun00b 1784.0 125.9 124.3 121.0 128.8 100.0
osaskgo 216.9 126.4 125.4 124.2 115.1 100.0
対rk指数のワースト値が、127.0→125.4(tek1)、125.9→124.2(tek2)
と、1.6以上さがっています。不得意の部分が改善して、汎用可逆圧縮
としては好ましいという印象がさらに強くなっています。
毎度のOSASKアプリです。以下はclv:2とclv:1が混ざっています（
clv:2で時間がかかったらclv:1にした）。
tek0 tek1 tek2 tek0→tek2での改善率
helloc4 497 491 489 1.61%
helloc9 176 174 172 2.27%
bballc0 628 619 617 1.75%
bballc2 295 293 291 1.36%
invader2 1699 1678 1676 1.35%
invader5 1258 1242 1241 1.35%
clvというのは圧縮レベルで、デフォルトが0です。0でも結構小さく
なります。1にすると圧縮時間が劇的に増えますが、圧縮率が少しよく
なります。2にすると圧縮時間がさらに増えますが、圧縮率もさらにも
う少しよくなります。基本的に限界に迫りたいとき以外はデフォルト
のままでいいと思います。
ええとinvader2はtek2の値が改悪になっています。これを回避する
ことはたぶんできるのですが、今回のバージョンではこの改悪を気に
しないことにしました（どうも前のは運よく高圧縮になっただけのよ
うなので）。
僕としては、ついにinvader5がTownsOS版と同じサイズになったのが
うれしいです（笑）。
圧縮速度ですが、clv:0ならたぶんtek0と同程度くらいには速くなっ
ています。とりあえずbim2bin4eよりは明らかに速いです。もっと速く
するには、最長一致検索アルゴリズムをまともにすればいいだけなの
ですが、相変わらず手抜きでやっていません。すみません。
ええと、今回の値がtek1/tek2の最終的な圧縮率だと思う人がいるか
もしれませんが、全然そんなことはありません。tek1/tek2はまだまだ
潜在能力を秘めていて、さらに圧縮率が上がる余地があります（確実に
圧縮率が上がりそうなことを面倒なのでやってない・・・展開ルーチン
側には既に展開用コードが書いてあるのですが）。
tek1とtek2の符号化の基本はスライド辞書法＋UC0（汎用符号0：ユニ
バーサルコード0）になっています。UC0はハフマン符号よりもずっと単
純な代わりに圧縮率の劣る符号で、今まで考えたD3やD4やL0aやL1aや
L1bやdf符号のどれにでも化けるような、そんな符号です（もちろんこ
れらを超える符号にもなれる）。
bzip2がブロックソートを使っているのに対して、LHAの「スライド辞
書法＋ハフマン符号」は旧世代アルゴリズムなどとも言われていますが
、tek1/tek2はそのLHAにも劣るアルゴリズムといえるでしょう（そうで
ないと展開ルーチンがLHA並みに大きくなってしまいますし）。しかし
それでもtek2はLHAの最高圧縮形式である-lh7-形式といい勝負をしてい
ます。今は全体的見て圧縮率ではやや劣っている感じですが、今後の圧
縮アルゴリズムの改良で、lh7に勝てるようになる可能性はあります。
ちなみにlh5というのが一般的に配布されているlzhの圧縮形式です。
tek1 tek2 lh5 lh7 bz2 rk
bim2binc 14556 14152 15073 14106 12903 11608
kdun00b 45694 44453 46955 45446 47306 36736
osaskgo 1140715 1129698 1137462 1098990 1047411 909824
tek1 tek2 lh5 lh7 bz2 rk
bim2binc 125.4 121.9 129.9 121.5 111.2 100.0
kdun00b 124.3 121.0 127.8 123.7 128.8 100.0
osaskgo 125.4 124.2 125.0 120.8 115.1 100.0
とりあえずこんなにしょぼいアルゴリズムだけでもここまでいけると
いうのを示したのはそれなりに意味があると自分では思っています。ス
ライド辞書法は展開時にブロックソートよりも少ないメモリしか必要と
しませんし、UC0はハフマン符号よりも少ないメモリしか必要としませ
ん。
それでは。
--
川合 秀実(KAWAI Hidemi)
OSASK計画代表 / システム設計開発担当
E-mail:kawai !Atmark! osask.jp
Homepage http://osask.jp/