サイトトップへ
OSASK.NET
  サイトトップへ       新掲示板(閉鎖済)   Wiki(凍結済)   旧掲示板(廃止済)   ニュース(廃止済)  
17: 2004-06-30 (水) 11:13:46 ソース 現: 2024-01-08 (月) 12:59:01 k-tan ソース
Line 1: Line 1:
-* 特別会議室+TITLE:x 
 +* 特別会議室 [#h5c5663f]
-詳しくは[[room]]参照 -詳しくは[[room]]参照
-(by [[K]], 2004.06.03) -(by [[K]], 2004.06.03)
-*** 圧縮しないのは非常識か?+*** 圧縮しないのは非常識か? [#k378dc7a]
-過去ログリスト -過去ログリスト
--[[room/000a]] 2004-05-29 (土) 12:50:09 - 2004-05-30 (日) 01:55:06 --[[room/000a]] 2004-05-29 (土) 12:50:09 - 2004-05-30 (日) 01:55:06
Line 14: Line 15:
--[[room/000h]] 2004-06-02 (水) 01:47:32 - 2004-06-02 (水) 04:02:39 --[[room/000h]] 2004-06-02 (水) 01:47:32 - 2004-06-02 (水) 04:02:39
--[[room/000i]] 2004-06-02 (水) 16:02:18 - 2004-06-03 (木) 05:34:10 --[[room/000i]] 2004-06-02 (水) 16:02:18 - 2004-06-03 (木) 05:34:10
 +--[[room/000j]] 2004-06-04 (金) 15:18:39 - 2004-06-10 (木) 02:10:57
-関連リンク -関連リンク
--[[tmp/圧縮について]] --[[tmp/圧縮について]]
Line 19: Line 21:
---- ----
--自分で言っといてなんですが、果たして本当に僕が言ったとおりであるかはある程度の検証が必要ですよね。まあtek1の展開速度が常にHDDの転送速度(キャッシュがヒットしない場合)よりも速いっていうのはよほどちぐはぐなCPUを使わない限りはあっていると思うのですが(たとえHDDが1万回転でも)、微妙なのはBMP+tek1(むしろこの場合は圧縮率のほうが重要だろうからtek2でもいいけど)がPNGや圧縮TIFFやGIFや圧縮BMPに比べて本当に小さいかどうかってことです。もちろんGIFとかですとアニメーション形式などもありますので、BMP+tek1で何でも代用できるというわけではありませんが。まあそれなら単純で処理しやすい無圧縮のアニメーション形式があってもいいじゃないか、という話にはなるかもしれません。 -- [[K]] SIZE(10){2004-06-04 (金) 15:18:39} 
--ということは、tek1/tek2の仕様を固めて、圧縮速度を上げたやつをリリースしなければ、話は前に進めないわけです。いやもちろん圧縮が遅くても圧縮率には影響しませんが、いろいろ圧縮して比べるのにくたびれてしまいますので。 -- [[K]] SIZE(10){2004-06-04 (金) 15:32:36} 
--でももし本当にPNGや圧縮TIFFがtek1とかtek2に負けるようだと、ある意味情けないです。だってそれらは画像対象の専用圧縮形式なので、画像に固有の統計的性質をあてにして設計されているはずで、一般的なものはそれほど縮まなくて画像なら縮むというアルゴリズムを積極的に利用できるからです。tek1/tek2のような汎用型(しかも圧縮率よりも展開速度やアルゴリズムの簡単さを図ったもの)に同等くらいのところまで追いつかれたらちょっと情けないでしょう、rkなどの高圧縮率追求型に負けるのならまだしも。 -- [[K]] SIZE(10){2004-06-04 (金) 15:37:11} 
--↑の件について実験しました。PNGやGIFやTIFはなんだったのかと思う結果が出ました。>[[[OSASK 6972]>OSASK:6972]] -- [[K]] SIZE(10){2004-06-07 (月) 19:44:50} 
--PNGとの差は画像の種類にもよるかも...(今回のケースでは色数も少なく同じ色が連続する部分が多いが、そうではない場合についても検討する必要あり) -- ''Zakky'' SIZE(10){2004-06-07 (月) 22:18:47} 
--とてもいい意見でそのとおりだと思います。ぜひサンプルデータをください。tekやgzip、bzip2、rkなどについては僕のほうですぐにできますので。 -- [[K]] SIZE(10){2004-06-07 (月) 22:35:20} 
--pngの圧縮はLZ77だったと思います。仕様公開されてます。[[5. 圧縮について:http://tech.millto.net/~pngnews/kndh/PngSpec/5.htm]]。そして、圧縮率変更も可能です。つまり、画像専用の圧縮形式という意味では、そうではないと思います。GIFもそうではなかったでしょうか。また、うちの環境ではPNGのファイルサイズがもっと小さくなりました。lh7はサイズがあいませんでした。7z形式では圧縮形式…LZMA:4496,bzip2:5021,deflate(gz相当?):6415,deflate:5899<高圧縮型。いそいでやってるので正確な値と違うかもしれませんし、バージョンが古いかもしれませんが。それにしても、tek1,tek2(tek0も)は(bmpに関しては)非常にいい結果なのではないでしょうか。 -- ''くーみん'' SIZE(10){2004-06-07 (月) 22:44:20} 
--おお、訂正情報ありがとうございます。そうかPNGの圧縮コアは汎用コアの流用だったのか・・・。圧縮率が振るわないのはスライド辞書が32KB制限されているからなのね。ためしにtek2圧縮のオプションをMD:32kにしてみました。あれ?それでも5618・・・6バイトしか変わらない?うむう、なぞだあ。 -- [[K]] SIZE(10){2004-06-07 (月) 22:57:34} 
--XP標準のペイントのPNG保存でも7508、GIMPで余計なデータを保存しなければ6484程度にはなりました。…でも大きいな。 -- ''くーみん'' SIZE(10){2004-06-07 (月) 23:12:22} 
--LZMAってやっぱりスライド辞書法なのかな。スライド辞書だけでbzip2よりも小さくできるとは・・・。さすがだ。となるとやっぱりtek1/tek2もまだまだなんだなあ。LZMAのアルゴリズムって簡単なのかなあ?展開速度も興味あるなあ・・・。 -- [[K]] SIZE(10){2004-06-08 (火) 00:39:06} 
--LZWなんてモロに汎用の圧縮じゃないんですか?画像の性質を圧縮に利用したのはPICやPI((C)やなぎさわ氏)とかJPGですよね。tekはこれらには勝てるのかな? -- [[I.Tak.]] SIZE(10){2004-06-08 (火) 10:09:52} 
--LZWそのものは汎用ですが、TIFFやGIFでの使い方は画像イメージ全体を汎用圧縮時のように扱うのではなく、ラインごとで周期的なものにあわせて工夫するとか、なんかそんな感じのことをやっているんだろうと勝手に思い込んでいました。JPGはたぶん自然画で圧倒的に強いと思うので、たぶんtekの出番はなさそうです。MAGとかならどうなのかな?しかし仮にこれらの形式のほうが圧縮率がよかったら、PNGってなんかすごく微妙ですね・・・。先発のフォーマットのほうが圧縮率がいい? -- [[K]] SIZE(10){2004-06-08 (火) 11:21:23} 
--どうやらPIが非常にいいようです。ついでBMP+LHA。 http://cclub-flying.dsl.gr.jp/~sage/sagepage/tec/imgspec/ より。ただPIはちょっと重いという人もいるみたいです。とりあえず、BMP+汎用圧縮に勝てるのがPIだけなら、非自然画ではPI以外のフォーマットはあまり価値がない?(これまでのソフトウェア資産やビューアの対応度をべつにすれば)。 -- [[K]] SIZE(10){2004-06-08 (火) 11:52:52} 
--さっそくVix 2.21でOSASKの壁紙をPI形式で保存させてみました。5625バイトでした。この例でもPNGには勝っているようです。さすがですね。ではtekはどうなのかというと、まずtek0とtek1では歯が立ちませんが、BMP+tek2ならMD:32kでも5618なので微妙に勝っております。これはなかなか悪くない気がしました。もっとも他のBMPファイルで試したらtek2惨敗の可能性はあります。 -- [[K]] SIZE(10){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]] SIZE(10){2004-06-08 (火) 14:36:32} 
--7zはLGPLのオープンソース「LZMA: Improved and optimized version of LZ77 algorithm」…[[7zFormat:http://www.7-zip.org/7z.html]]より…[[lzmaのsdk:http://www.7-zip.org/sdk.html]](できれば多少は調べて欲しいと思いましたw、サポートするのがコミュニティの役目の一つだから、浮いた時間を開発時間に使ってもらえればいいんだけれど)短いので、解説だけでも読んでくだされば。私もソースを読む時間等は取れませんが。 -- ''くーみん'' SIZE(10){2004-06-09 (水) 20:58:41} 
--実はこれでも20分くらい「LZMA」などでせっせと検索したのですが(7zとは独立に存在しているアルゴリズムだと頭から思い込んでいたせいもあって)、見つけられませんでした。非常に助かりました。ありがとうございます。で、LZMAはとてもいいです。ついさっきまで、かなり本気でtek2を完全に破棄して、LZMAをtek2の中身にしてしまおうと考えていたくらいです。 -- [[K]] SIZE(10){2004-06-09 (水) 23:22:49} 
--それをかろうじて思いとどまらせたのは、展開速度の問題でした。LZMAはあのtek0よりもさらに遅いのです(わずかな差ではありますが)。今、いろいろと最適化の余地を検討していますが、どうにかなるものなのかどうにもならないのか、まずはそれを突き止めたいです。 -- [[K]] SIZE(10){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|RIGHT:36.7|RIGHT:175.7| 
-|tek1|0.75[sec]|1097475|120.6|RIGHT:15.5|RIGHT:90.5| 
-|tek2|0.82[sec]|1092517|120.1|RIGHT:16.5|RIGHT:98.5| 
-|tek3|0.22[sec]|1318722|144.9|RIGHT:9.9|RIGHT:31.9| 
-|LZMA|1.42[sec]|RIGHT:953821|104.8|RIGHT:6.8|RIGHT:148.8| 
-|LZO|0.20[sec]|1177820|129.5|RIGHT:5.9|RIGHT:25.9| 
-|bzip2|2.52[sec]|1047411|115.1|RIGHT:38.1|RIGHT:290.1| 
-|GCA|4.91[sec]|1002311|110.2|RIGHT:50.1|| 
-|gzip|1.35[sec]|1111684|122.2|RIGHT:30.0|| 
-|lh7|1.21[sec]|1099064|120.8|RIGHT: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]] SIZE(10){2004-06-09 (水) 23:52:23} 
--tek3の暫定版とLZOも表に入れておきました。tek3の圧縮率がひどいように見えるかもしれませんが、例によって僕は展開速度と安定重視で符号化の方針を決めているので、これはしょうがないです。LZOはOSASK.BMPやkdun00bが苦手で(というかテキストと実行バイナリに特化している感じ?)、汎用としては少々弱いところがあります。まあその辺のことはbim2bin4iのリリース時に説明しますので、今はこれくらいにします。 -- [[K]] SIZE(10){2004-06-10 (木) 01:58:51} 
--LZMAはアルゴリズム的にはこれ以上速くはできないっぽいです。もちろんASKA化によってそれなりには速くできそうですが、(デコードされた)1bitを得るためには整数乗算を1回やらないといけないので、C→ASKAにしてもtek系と同じ比率で速くなるという見込みはあまりありません。なんかもったいないなあ。・・・ということで将来的には併用確定。LZMAは「時間が取れたら」OSASKやKHBIOSに実装するということにして、とりあえず今はtek系の実装を急ぐことにします。 -- [[K]] SIZE(10){2004-06-10 (木) 02:10:57} 
--http://students.fhs-hagenberg.ac.at/se/se00001/Projects_LZMA_.htmlなにこれ -- [[名無しさん]] SIZE(10){2004-06-10 (木) 16:34:53} 
--GCAのページ見たら展開速度が速いみたいなことが強調してあったので、ほうブロックソートでも速いやつがあるのか、とさっそくosaskgoで実験してみました。・・・なんだー、bzip2よりもさらにおそいじゃん・・・。 -- [[K]] SIZE(10){2004-06-16 (水) 20:40:55} 
-すみません。改めてこちらに書きます。せんえつながら意見とか少し思った事です。・極々小さなファイルは逆に大きくなる。既にエントロピーの高いデータ(jpeg等)に圧縮を行うのは無駄⇒無圧縮形式もあるべき。・ファイルサイズだけでなくクラスタギャップも重要視すると完璧(FAT等も考慮)⇒小さいファイルはアーカイブも行う・大きなファイルの途中を開く時先頭セクタから順次見る必要が出る⇒大きなデータは複数チャンクに分けファイル先頭に索引つける・キャッシュファイルも圧縮?・ランダムアクセスは辛くないかな?・DMA転送のみで終わる無圧縮に比べ複数バスやCPUを使うので優しくない?⇔CPU、メモリとHDD容量のトレードオフ -- ''Chihaya'' SIZE(10){2004-06-22 (火) 21:12:30} -すみません。改めてこちらに書きます。せんえつながら意見とか少し思った事です。・極々小さなファイルは逆に大きくなる。既にエントロピーの高いデータ(jpeg等)に圧縮を行うのは無駄⇒無圧縮形式もあるべき。・ファイルサイズだけでなくクラスタギャップも重要視すると完璧(FAT等も考慮)⇒小さいファイルはアーカイブも行う・大きなファイルの途中を開く時先頭セクタから順次見る必要が出る⇒大きなデータは複数チャンクに分けファイル先頭に索引つける・キャッシュファイルも圧縮?・ランダムアクセスは辛くないかな?・DMA転送のみで終わる無圧縮に比べ複数バスやCPUを使うので優しくない?⇔CPU、メモリとHDD容量のトレードオフ -- ''Chihaya'' SIZE(10){2004-06-22 (火) 21:12:30}
-たくさんの論点がありますが、まずは簡単なものだけを。圧縮してもろくに小さくならないものについては、僕も圧縮するべきではないと思います(というか小さくならない時点で、既に圧縮ではなくなって、ただのエンコードになっている)。ファイルサイズではなくて消費クラスタの観点をということについては、OSASKのファイルシステムでカバーする予定(複数の小さいファイルを1つのクラスタにまとめる)ですので、圧縮の是非の問題からとりあえず切り離します。大きいファイルを開くときに前からアクセスしなければいけないという点については、それは他の圧縮形式に言えることであって、ランダムアクセス対策を施しているtek1~tek3には無縁です(内部がマルチブロック化されており、先頭にブロック先頭位置を高速に割り出すための階層構造のインデックスまでついています)。このおかげでランダムアクセス性能も問題ないでしょう。残りの論点はあとで。 -- [[K]] SIZE(10){2004-06-22 (火) 22:10:16} -たくさんの論点がありますが、まずは簡単なものだけを。圧縮してもろくに小さくならないものについては、僕も圧縮するべきではないと思います(というか小さくならない時点で、既に圧縮ではなくなって、ただのエンコードになっている)。ファイルサイズではなくて消費クラスタの観点をということについては、OSASKのファイルシステムでカバーする予定(複数の小さいファイルを1つのクラスタにまとめる)ですので、圧縮の是非の問題からとりあえず切り離します。大きいファイルを開くときに前からアクセスしなければいけないという点については、それは他の圧縮形式に言えることであって、ランダムアクセス対策を施しているtek1~tek3には無縁です(内部がマルチブロック化されており、先頭にブロック先頭位置を高速に割り出すための階層構造のインデックスまでついています)。このおかげでランダムアクセス性能も問題ないでしょう。残りの論点はあとで。 -- [[K]] SIZE(10){2004-06-22 (火) 22:10:16}
Line 76: Line 37:
-僕は展開ルーチンのサイズを追求していません。かつては追求していましたが。詳しくは[[[OSASK 6985]>OSASK:6985]]を参照してください。 -- [[K]] SIZE(10){2004-06-30 (水) 11:11:08} -僕は展開ルーチンのサイズを追求していません。かつては追求していましたが。詳しくは[[[OSASK 6985]>OSASK:6985]]を参照してください。 -- [[K]] SIZE(10){2004-06-30 (水) 11:11:08}
-bim2bin4iは既に過去の形式なのでバグが残っていたとしても直しません。でもbim2bin4kのtek2もたまに挙動不審です。昨日気がつきました。これは直します。ちなみにbim2bin4iのtek2の後継はtek4です。今のtek3はbim2bin4iでいうところのtek1相当です。bim2bin4iのtek1と今のtek3を比べて、これから出てくるtek4にわくわくするのが現時点でのbim2bin4iの使い方でしょう。 -- [[K]] SIZE(10){2004-06-30 (水) 11:13:46} -bim2bin4iは既に過去の形式なのでバグが残っていたとしても直しません。でもbim2bin4kのtek2もたまに挙動不審です。昨日気がつきました。これは直します。ちなみにbim2bin4iのtek2の後継はtek4です。今のtek3はbim2bin4iでいうところのtek1相当です。bim2bin4iのtek1と今のtek3を比べて、これから出てくるtek4にわくわくするのが現時点でのbim2bin4iの使い方でしょう。 -- [[K]] SIZE(10){2004-06-30 (水) 11:13:46}
 +-今後tek1のフォーマットは変更になる可能性がありますか? -- ''sakky'' SIZE(10){2004-07-02 (金) 03:38:03}
 +-まあいかなる可能性もゼロではないのですが、tek1のフォーマットをいじる可能性はかなり低いです。というのは、tek1は展開速度重視型で、圧縮率を上げるために今よりも複雑にすれば展開速度が落ちてしまうだろうからです。もし圧縮率を改善できるよいアイデアをまた思いついたとしても、それはきっと多少の展開速度の低下を招くのでtek2以降にのみ適用されるということになると思われます。・・・まあ展開速度がほとんど落ちなくて劇的に圧縮率が改善するようなアイデアだったりしたらtek1にも入れるでしょうけど、もうそんな都合のいいアイデアは存在しない気がします。・・・ってな感じです。 -- [[K]] SIZE(10){2004-07-02 (金) 11:43:05}
 +-それではもう安心して使用してもよいのでしょうか -- ''sakky'' SIZE(10){2004-07-02 (金) 12:00:52}
 +-うーん、そうですねえ。tek1全体(補助バッファやマルチブロックを含む)のテストは不十分なので自信がないですが、stk1の範囲なら今後変更しない可能性は98%くらいです。・・・このようなイマイチはっきりしない回答ですみません。自分でも今までの前科があるので、どうも言い切りにためらいを覚えるのです。あと1週間待ってもらえれば、これが99%か0%なのかはっきりしますし、さらに2週間くらい待ってもらえれば、100%か0%になると思います(つまりそれくらいでstk1~4の仕様は固定されます)。 -- [[K]] SIZE(10){2004-07-02 (金) 13:23:05}
 +-わかりました。ところでチェックサムとかCRCは無いのでしょうか? -- ''sakky'' SIZE(10){2004-07-02 (金) 13:28:44}
 +-CRC等はstk1の範囲に入っておりまして、まずdtk1s.cでhedのbit6(0x40)を1にして圧縮データ全体のサイズを圧縮データの直前に置かせます。これで末尾に追加情報を持たせられるようになって、その追加情報でCRCやECCなどの情報を何らかのフォーマットで記録しようと思っています。ということで、とりあえず将来CRCやECCをサポートしても、今のデコードライブラリで無事に展開できるというわけです(今のライブラリではチェックはできませんが)。追加情報というのは展開そのものには必要とされない情報の全てです(チェック情報とかコメントとか)。 -- [[K]] SIZE(10){2004-07-02 (金) 13:43:31}
 +-わかりました。返答ありがとうございました。 -- ''sakky'' SIZE(10){2004-07-02 (金) 14:32:04}
 +-Chihayaさんとのやり取りを読みつつ、結局僕がsarフォーマットの開発に至ってしまったところを見ると、結局はChihayaさんのセンスが最強だったのかなあと思う今日この頃。 -- [[K]] SIZE(10){2004-12-09 (木) 11:49:36}
#comment #comment

トップ   差分 バックアップ 複製 名前変更 リロード印刷に適した表示   ページ新規作成 全ページ一覧 単語検索 最新ページの一覧   ヘルプ
新着

目次
メンバー一覧


最新の20件
2016-10-01 2016-09-08
  • @MenuBar.
2016-09-07 2016-09-04 2016-08-15 2015-09-23 2014-07-30 2014-07-04 2014-02-04 2013-10-26 2013-06-21 2013-06-17 2013-06-15 2013-04-02 2013-02-09 2013-02-04 2012-12-25 2012-12-01 2012-05-28 2012-03-31

トピック一覧
一般用コメント最新
新掲示板lina
2016/9/5 20:58
SandBoxゲスト
2016/9/4 12:01
RecentDeletedlina
2015/6/2 19:29
Old-OSASK-MLlina
2014/6/29 9:14
hideyosi/メールhideyosi
2014/1/6 20:17
hideyosi/募集中lina
2013/11/8 19:56

このサイトは川合秀実から委託を受けて、OSASKコミュニティによって管理・運営されています。