room​/000j :: OSASK計画

特別会議室

• (by K, 2004.06.03)
• 詳しくはroom参照
  • この会議室内のトップページ：room​/000

圧縮しないのは非常識か？

• room​/000iからの続き

• 自分で言っといてなんですが、果たして本当に僕が言ったとおりであるかはある程度の検証が必要ですよね。まあtek1の展開速度が常にHDDの転送速度（キャッシュがヒットしない場合）よりも速いっていうのはよほどちぐはぐなCPUを使わない限りはあっていると思うのですが（たとえHDDが1万回転でも）、微妙なのはBMP+tek1（むしろこの場合は圧縮率のほうが重要だろうからtek2でもいいけど）がPNGや圧縮TIFFやGIFや圧縮BMPに比べて本当に小さいかどうかってことです。もちろんGIFとかですとアニメーション形式などもありますので、BMP+tek1で何でも代用できるというわけではありませんが。まあそれなら単純で処理しやすい無圧縮のアニメーション形式があってもいいじゃないか、という話にはなるかもしれません。 -- K 2004-06-04 (金) 15:18:39
• ということは、tek1/tek2の仕様を固めて、圧縮速度を上げたやつをリリースしなければ、話は前に進めないわけです。いやもちろん圧縮が遅くても圧縮率には影響しませんが、いろいろ圧縮して比べるのにくたびれてしまいますので。 -- K 2004-06-04 (金) 15:32:36
• でももし本当にPNGや圧縮TIFFがtek1とかtek2に負けるようだと、ある意味情けないです。だってそれらは画像対象の専用圧縮形式なので、画像に固有の統計的性質をあてにして設計されているはずで、一般的なものはそれほど縮まなくて画像なら縮むというアルゴリズムを積極的に利用できるからです。tek1/tek2のような汎用型（しかも圧縮率よりも展開速度やアルゴリズムの簡単さを図ったもの）に同等くらいのところまで追いつかれたらちょっと情けないでしょう、rkなどの高圧縮率追求型に負けるのならまだしも。 -- K 2004-06-04 (金) 15:37:11
• ↑の件について実験しました。PNGやGIFやTIFはなんだったのかと思う結果が出ました。＞[[［OSASK 6972］>OSASK:6972]] -- K 2004-06-07 (月) 19:44:50
• PNGとの差は画像の種類にもよるかも...(今回のケースでは色数も少なく同じ色が連続する部分が多いが、そうではない場合についても検討する必要あり) -- Zakky 2004-06-07 (月) 22:18:47
• とてもいい意見でそのとおりだと思います。ぜひサンプルデータをください。tekやgzip、bzip2、rkなどについては僕のほうですぐにできますので。 -- K 2004-06-07 (月) 22:35:20
• pngの圧縮はLZ77だったと思います。仕様公開されてます。5. 圧縮について。そして、圧縮率変更も可能です。つまり、画像専用の圧縮形式という意味では、そうではないと思います。GIFもそうではなかったでしょうか。また、うちの環境ではPNGのファイルサイズがもっと小さくなりました。lh7はサイズがあいませんでした。7z形式では圧縮形式…LZMA:4496,bzip2:5021,deflate(gz相当?):6415,deflate:5899<高圧縮型。いそいでやってるので正確な値と違うかもしれませんし、バージョンが古いかもしれませんが。それにしても、tek1,tek2(tek0も)は(bmpに関しては)非常にいい結果なのではないでしょうか。 -- くーみん 2004-06-07 (月) 22:44:20
• おお、訂正情報ありがとうございます。そうかPNGの圧縮コアは汎用コアの流用だったのか・・・。圧縮率が振るわないのはスライド辞書が32KB制限されているからなのね。ためしにtek2圧縮のオプションをMD:32kにしてみました。あれ？それでも5618・・・6バイトしか変わらない？うむう、なぞだあ。 -- K 2004-06-07 (月) 22:57:34
• XP標準のペイントのPNG保存でも7508、GIMPで余計なデータを保存しなければ6484程度にはなりました。…でも大きいな。 -- くーみん 2004-06-07 (月) 23:12:22
• LZMAってやっぱりスライド辞書法なのかな。スライド辞書だけでbzip2よりも小さくできるとは・・・。さすがだ。となるとやっぱりtek1/tek2もまだまだなんだなあ。LZMAのアルゴリズムって簡単なのかなあ？展開速度も興味あるなあ・・・。 -- K 2004-06-08 (火) 00:39:06
• LZWなんてモロに汎用の圧縮じゃないんですか？画像の性質を圧縮に利用したのはPICやPI((C)やなぎさわ氏)とかJPGですよね。tekはこれらには勝てるのかな？ -- I.Tak. 2004-06-08 (火) 10:09:52
• LZWそのものは汎用ですが、TIFFやGIFでの使い方は画像イメージ全体を汎用圧縮時のように扱うのではなく、ラインごとで周期的なものにあわせて工夫するとか、なんかそんな感じのことをやっているんだろうと勝手に思い込んでいました。JPGはたぶん自然画で圧倒的に強いと思うので、たぶんtekの出番はなさそうです。MAGとかならどうなのかな？しかし仮にこれらの形式のほうが圧縮率がよかったら、PNGってなんかすごく微妙ですね・・・。先発のフォーマットのほうが圧縮率がいい？ -- K 2004-06-08 (火) 11:21:23
• どうやらPIが非常にいいようです。ついでBMP+LHA。 http://cclub-flying.dsl.gr.jp/~sage/sagepage/tec/imgspec/ より。ただPIはちょっと重いという人もいるみたいです。とりあえず、BMP＋汎用圧縮に勝てるのがPIだけなら、非自然画ではPI以外のフォーマットはあまり価値がない？（これまでのソフトウェア資産やビューアの対応度をべつにすれば）。 -- K 2004-06-08 (火) 11:52:52
• さっそくVix 2.21でOSASKの壁紙をPI形式で保存させてみました。5625バイトでした。この例でもPNGには勝っているようです。さすがですね。ではtekはどうなのかというと、まずtek0とtek1では歯が立ちませんが、BMP+tek2ならMD:32kでも5618なので微妙に勝っております。これはなかなか悪くない気がしました。もっとも他のBMPファイルで試したらtek2惨敗の可能性はあります。 -- K 2004-06-08 (火) 13:30:00
• 2chのOSASKスレッドをみたらLZOという形式が紹介されていたので探してみました（できれば特徴と圧縮ツールのURLくらいは書いておいてほしいと思いました）。LZOはlzopというプログラムで圧縮展開でき、猛烈に展開が速いことが特徴のようです。多分tek1よりも速いです。ただ、圧縮率は結構犠牲になっています。LZOは圧縮もモードによってはかなり速くできるので、インターネットでのパケット圧縮などで活躍しているそうです。で、肝心の圧縮結果ですが、-9の最高圧縮率で次のようになりました。括弧内はtek1に対するパーセントです（対rkではないので注意）。bim2binc：16015(110.6%)、kdun00b：52148(123.9%)、osaskgo：1177820（107.3%）、osask.bmp：8618(145.2%)。展開が速いのがとてもありがたいことは間違いないですが、tek1はわずかなコードの追加で結構健闘しているtek2をサポートできるということもありますし、圧縮である以上やっぱりそれなりの圧縮率もほしい気がしますので（あまり圧縮率がよくないと結局は使ってもらえない可能性もある）、とりあえずLZOは見送りです。しかしファイルシステムで圧縮するときや、OSがRAM内部のデータを圧縮してスワップを減らすなどの、展開速度だけではなく圧縮速度もそれなりに重要なときは、LZOは大変ふさわしいアルゴリズムのような気がします。 -- K 2004-06-08 (火) 14:36:32
• 7zはLGPLのオープンソース「LZMA: Improved and optimized version of LZ77 algorithm」…7zFormatより…lzmaのsdk(できれば多少は調べて欲しいと思いましたｗ、サポートするのがコミュニティの役目の一つだから、浮いた時間を開発時間に使ってもらえればいいんだけれど)短いので、解説だけでも読んでくだされば。私もソースを読む時間等は取れませんが。 -- くーみん 2004-06-09 (水) 20:58:41
• 実はこれでも20分くらい「LZMA」などでせっせと検索したのですが（7zとは独立に存在しているアルゴリズムだと頭から思い込んでいたせいもあって）、見つけられませんでした。非常に助かりました。ありがとうございます。で、LZMAはとてもいいです。ついさっきまで、かなり本気でtek2を完全に破棄して、LZMAをtek2の中身にしてしまおうと考えていたくらいです。 -- K 2004-06-09 (水) 23:22:49
• それをかろうじて思いとどまらせたのは、展開速度の問題でした。LZMAはあのtek0よりもさらに遅いのです（わずかな差ではありますが）。今、いろいろと最適化の余地を検討していますが、どうにかなるものなのかどうにもならないのか、まずはそれを突き止めたいです。 -- K 2004-06-09 (水) 23:26:02
  • 参考：EPIA-VE5000でのosaskgoの展開速度（C版 --- ASKA版は多分1.5～2倍は速い）

    meth.	deco.time	size	vs rk	score	score2
    tek0	1.39[sec]	1149662	126.4	36.7	175.7
    tek1	0.75[sec]	1097475	120.6	15.5	90.5
    tek2	0.82[sec]	1092517	120.1	16.5	98.5
    tek3	0.22[sec]	1318722	144.9	9.9	31.9
    LZMA	1.42[sec]	953821	104.8	6.8	148.8
    LZO	0.20[sec]	1177820	129.5	5.9	25.9
    bzip2	2.52[sec]	1047411	115.1	38.1	290.1
    GCA	4.91[sec]	1002311	110.2	50.1
    gzip	1.35[sec]	1111684	122.2	30.0
    lh7	1.21[sec]	1099064	120.8	25.2

  • bzip2とtek3（暫定）とLZOはおまけです。たぶんLZOは既にアセンブラ化されていると思います（そうでないとこの圧縮率でこの速さは出ない）。bzip2はアセンブラ化されているかどうかは僕には想像がつきませんが、ブロックソート法では圧縮率の代償として展開速度低下があるという傾向はつかめると思います。
  • score = time x (vs_rk - 100)
    • なんとなく計算してみたくなったので（笑）。小さければ小さいほど圧縮率と展開速度のバランスに優れていることを示していると思う。
    • LZOが僕の予想通りアセンブラ化されているとすれば、公平化のためには1.5倍くらいして8.9くらいのつもりで見るといいと思う。
  • score2 = time x vs_rk
    • scoreの指標がどれくらい実感に近いのかを確認するために計算した参考値。この指標で比較するとrkでの圧縮率に影響されないが、この指標ではあんなにがんばっているLZMAがtek2に劣ることになってしまう。これはいくらなんでも圧縮率の評価が弱すぎるわけだ。
• ちなみにLZMAは展開時の消費メモリと展開ルーチンの複雑さの観点では、さしたる問題はなさそうです。うーん、やっぱり併用なのかなあ、tek1/tek2/tek3/LZMAの。これだけ全部入れたら、さすがに3KBくらいはOSが大きくなりそうだけど、でもここまで強烈だと、LZMAをあきらめるのは惜しい・・・。 -- K 2004-06-09 (水) 23:52:23
• tek3の暫定版とLZOも表に入れておきました。tek3の圧縮率がひどいように見えるかもしれませんが、例によって僕は展開速度と安定重視で符号化の方針を決めているので、これはしょうがないです。LZOはOSASK.BMPやkdun00bが苦手で（というかテキストと実行バイナリに特化している感じ？）、汎用としては少々弱いところがあります。まあその辺のことはbim2bin4iのリリース時に説明しますので、今はこれくらいにします。 -- K 2004-06-10 (木) 01:58:51
• LZMAはアルゴリズム的にはこれ以上速くはできないっぽいです。もちろんASKA化によってそれなりには速くできそうですが、（デコードされた）1bitを得るためには整数乗算を1回やらないといけないので、C→ASKAにしてもtek系と同じ比率で速くなるという見込みはあまりありません。なんかもったいないなあ。・・・ということで将来的には併用確定。LZMAは「時間が取れたら」OSASKやKHBIOSに実装するということにして、とりあえず今はtek系の実装を急ぐことにします。 -- K 2004-06-10 (木) 02:10:57
• http://students.fhs-hagenberg.ac.at/se/se00001/Projects_LZMA_.htmlなにこれ -- 名無しさん 2004-06-10 (木) 16:34:53
• GCAのページ見たら展開速度が速いみたいなことが強調してあったので、ほうブロックソートでも速いやつがあるのか、とさっそくosaskgoで実験してみました。・・・なんだー、bzip2よりもさらにおそいじゃん・・・。 -- K 2004-06-16 (水) 20:40:55

• room​/000へ続く