tek1​/comp のバックアップソース(No.21) :: OSASK計画

• 差分^[1] を表示
• 現在との差分^[2] を表示
• tek1/comp^[3] へ行く。

* [[tek1]]の続き
-(by [[K]], 2004.07.05)

//-''遅くとも7/6の夜までには詳細をOSASK-MLで説明しますので、それまでは一切の質問をしないでください。まあIRCでの質問ならかまいませんが。''

-tek1～tek5の圧縮展開比較表
--MLに書いたら読みにくくなるのでデータだけこっちでまとめ

//--''たくさんの形式があってよく分からない人へ：''tek2～tek5は今のところベータ版であり、今理解できないならまだ理解しないほうがいいです。このページは、現在の開発状況を確認するためだけのものです。
//---もし現状を少しでも知りたいということであれば、とりあえずtek5が本命で、それ以外はオマケだという認識でいてください。

*** 比較表
-サイズ （num128以外では、tek1～2とstk1～2はほぼ同じなので、stk1～2は省略）
||無圧縮|tek0|tek1|tek2|stk5|tek5|lh7|gzip|bzip2|LZMA|LZO|rk|PAQ|h
|~hellok1|RIGHT:272|RIGHT:128|RIGHT:144|RIGHT:135|RIGHT:126|RIGHT:124|RIGHT:205|RIGHT:143|RIGHT:166|RIGHT:121|RIGHT:193|RIGHT:208|RIGHT:116|
|~zero4k|RIGHT:4096|RIGHT:27|RIGHT:25|RIGHT:25|RIGHT:28|RIGHT:28|RIGHT:86|RIGHT:49|RIGHT:43|RIGHT:39|RIGHT:91|RIGHT:100|RIGHT:30|
|~zero64k|RIGHT:65536|RIGHT:28|RIGHT:27|RIGHT:29|RIGHT:29|RIGHT:29|RIGHT:117|RIGHT:108|RIGHT:43|RIGHT:90|RIGHT:422|RIGHT:108|RIGHT:43|
|~bim2binc|RIGHT:53792|RIGHT:15019|RIGHT:17166|RIGHT:16323|RIGHT:12712|RIGHT:12579|RIGHT:14181|RIGHT:13467|RIGHT:12903|RIGHT:12708|RIGHT:16015|RIGHT:11608|RIGHT:9215|
|~kdun00b|RIGHT:655360|RIGHT:46246|RIGHT:49855|RIGHT:46794|RIGHT:33549|RIGHT:32909|RIGHT:45520|RIGHT:42553|RIGHT:47306|RIGHT:34037|RIGHT:52148|RIGHT:36736|RIGHT:29157|
|~osaskgo|RIGHT:1973741|RIGHT:1149662|RIGHT:1274931|RIGHT:1172344|RIGHT:942375|RIGHT:936928|RIGHT:1099064|RIGHT:1087874|RIGHT:1047411|RIGHT:942369|RIGHT:1177820|RIGHT:909824|RIGHT:748512|
|~osask.bmp|RIGHT:393334|RIGHT:6389|RIGHT:7740|RIGHT:7135|RIGHT:3860|RIGHT:3669|RIGHT:6467|RIGHT:5687|RIGHT:4906|RIGHT:4236|RIGHT:8618|RIGHT:4344|RIGHT:2429|
|~num128|RIGHT:131072|RIGHT:106953|||RIGHT:66036||RIGHT:118548|RIGHT:124645|RIGHT:25542|RIGHT:84237|RIGHT:131136|RIGHT:1192|RIGHT:|
---細かい圧縮条件をこちらにまとめました。→[[tek1/comp/opt]]

-規格化指数
||無圧縮|tek0|stk1|tek1|stk2|tek2|stk5|tek5|lh7|gzip|bzip2|LZMA|LZO|rk|PAQ|
|hellok1|RIGHT:234.5|RIGHT:110.3|RIGHT:124.1|RIGHT:124.1|RIGHT:116.4|RIGHT:116.4|RIGHT:108.6|RIGHT:106.9|RIGHT:176.7|RIGHT:123.3|RIGHT:143.1|RIGHT:104.3|RIGHT:166.4|RIGHT:179.3|RIGHT:100.0|
|zero4k|RIGHT:16384|RIGHT:108.0|RIGHT:100.0|RIGHT:100.0|RIGHT:100.0|RIGHT:100.0|RIGHT:112.0|RIGHT:112.0|RIGHT:344.0|RIGHT:196.0|RIGHT:172.0|RIGHT:156.0|RIGHT:364.0|RIGHT:400.0|RIGHT:120.0|
|zero64k|RIGHT:242726|RIGHT:103.7|RIGHT:100.0|RIGHT:100.0|RIGHT:107.4|RIGHT:107.4|RIGHT:107.4|RIGHT:107.4|RIGHT:433.3|RIGHT:400.0|RIGHT:159.3|RIGHT:333.3|RIGHT:1563|RIGHT:400.0|RIGHT:159.3|
|bim2binc|RIGHT:583.7|RIGHT:163.0|RIGHT:186.3|RIGHT:186.3|RIGHT:177.1|RIGHT:177.1|RIGHT:137.9|RIGHT:136.5|RIGHT:153.9|RIGHT:146.1|RIGHT:140.0|RIGHT:137.9|RIGHT:173.8|RIGHT:126.0|RIGHT:100.0|
|kdun00b|RIGHT:2248|RIGHT:158.6|RIGHT:171.0|RIGHT:171.0|RIGHT:160.5|RIGHT:160.5|RIGHT:115.1|RIGHT:112.9|RIGHT:156.1|RIGHT:145.9|RIGHT:162.2|RIGHT:116.7|RIGHT:178.9|RIGHT:126.0|RIGHT:100.0|
|osaskgo|RIGHT:263.7|RIGHT:153.6|RIGHT:170.3|RIGHT:170.3|RIGHT:156.6|RIGHT:156.6|RIGHT:125.9|RIGHT:125.2|RIGHT:146.8|RIGHT:145.3|RIGHT:139.9|RIGHT:125.9|RIGHT:157.4|RIGHT:121.5|RIGHT:100.0|
|osask.bmp|RIGHT:16193|RIGHT:263.0|RIGHT:318.6|RIGHT:318.6|RIGHT:293.7|RIGHT:293.7|RIGHT:158.9|RIGHT:151.0|RIGHT:266.2|RIGHT:234.1|RIGHT:202.0|RIGHT:174.4|RIGHT:354.8|RIGHT:178.8|RIGHT:100.0|
|num128|RIGHT:327680|RIGHT:267383|||||||RIGHT:296370|RIGHT:311613|RIGHT:63855|RIGHT:210593|RIGHT:32840|RIGHT:2980|RIGHT:|
|(max)||RIGHT:263.0|RIGHT:318.6|RIGHT:318.6|RIGHT:293.7|RIGHT:293.7|RIGHT:158.9|RIGHT:151.0|RIGHT:266.2|RIGHT:234.1|RIGHT:202.0|RIGHT:174.4|RIGHT:354.8|RIGHT:178.8|RIGHT:100.0|
--(max)は、bim2binc、kdun00b、osaskgo、osask.bmpのみ対象（他はあまりにtek系が得意なため除外）
--(max)で判断すると安定して圧縮率のよいものは以下の順になる。
|PAQ|tek5|stk5|LZMA|rk|bzip2|gzip|tek0|lh7|tek2|stk2|tek1|stk1|LZO|
|100.0|151.0|158.9|174.4|178.8|202.0|234.1|263.0|266.2|293.7|293.7|318.6|318.6|354.8|
--↑これは完全にosask.bmpの結果で決まっているともいえるので、参考までにosask.bmpを除いて集計すると以下のようになる。
---しかし、「汎用圧縮符号」としては弱点があるというのは好ましくない。そしてosask.bmpの内容は多くの符号の共通の弱点を突く内容なのだろう。
|PAQ|rk|tek5|LZMA|stk5|gzip|lh7|bzip2|tek0|tek2|stk2|LZO|tek1|stk1|
|100.0|126.0|136.5|137.9|137.9|146.1|156.1|162.2|163.0|177.1|177.1|178.9|186.3|186.3|
---全体的にtek系が少し落ちて、rkがあがってbzip2が落ちる程度で、それほど傾向は変わらない。
//---bzip2が落ちてlh7が少し回復する以外は、順位そのものの傾向は変わらない。
-tar+stk5（.tar.tk/.ttk）、sar(sar+stk5)
||tar|ttk|sar|lh7|tgz|tbz|tar.lzma|
|bim2bi4j|RIGHT:266725|RIGHT:65255||RIGHT:902616|RIGHT:84581|RIGHT:72747|RIGHT:65314|
|osat45i|RIGHT:759808|RIGHT:503442|RIGHT:502423|RIGHT:532093|RIGHT:528923|RIGHT:547131|RIGHT:503545|
|[[cantrbry:http://corpus.canterbury.ac.nz/descriptions/]]|RIGHT:2821120|RIGHT:482972||RIGHT:714769|RIGHT:735997 |RIGHT:568667|RIGHT:483768|
--ディスクイメージへの強さが、tarへの強さにつながったのかも？
--ロングファイルネーム対応のSF16ができるまで.img.tk(.itk)は不便だろうから、とりあえず.tar.tk(.ttk)で。
--cantrbryはよく分からないけど有名な圧縮対象のようです。
---http://www.emit.jp/gca/cmptest.html
---http://compression.ca/act-canterbury.html

-展開速度
--参考：EPIA-VE5000でのosaskgoの展開速度
|meth.|deco.time|t-idx|size|vs PAQ|score|score2|言語|備考|
|tek1|0.15[sec]|RIGHT:1.0|RIGHT:1274931|RIGHT:170.3|RIGHT:70.3|RIGHT:0.35|ASKA|Cでは0.18[sec]|
|LZO|0.18[sec]|RIGHT:1.3|RIGHT:1177820|RIGHT:157.4|RIGHT:74.6|RIGHT:0.25|?|←おそらくasm|
|tek2|0.18[sec]|RIGHT:1.3|RIGHT:1172344|RIGHT:156.6|RIGHT:73.6|RIGHT:0.24|ASKA|Cでは0.27[sec]|
|lh7|1.04[sec]|RIGHT:9.9|RIGHT:1099064|RIGHT:146.8|RIGHT:463.3|RIGHT:1.01|?||
|stk5|1.18[sec]|RIGHT:11.3|RIGHT:953743|RIGHT:127.4||RIGHT:0.23|ASKA|Cでは1.37[sec]|
|gzip|1.24[sec]|RIGHT:11.9|RIGHT:1087874|RIGHT:145.3|RIGHT:|RIGHT:1.11|?||
|stk5|1.39[sec]|RIGHT:13.4|RIGHT:942375|RIGHT:125.9||RIGHT:0.23|ASKA|Cでは1.63[sec]|
|tek0|1.39[sec]|RIGHT:13.4|RIGHT:1149662|RIGHT:153.6|RIGHT:734.3|RIGHT:2.06|C||
|LZMA|1.42[sec]|RIGHT:13.7|RIGHT:953728|RIGHT:127.4|RIGHT:375.4|RIGHT:0.28|C||
|LZMA|1.66[sec]|RIGHT:16.1|RIGHT:942369|RIGHT:125.9|RIGHT:|RIGHT:0.28|C||
|bzip2|2.52[sec]|RIGHT:24.7|RIGHT:1047411|RIGHT:139.9|RIGHT:985.5|RIGHT:1.57|?||
|GCA|4.91[sec]|RIGHT:48.6|RIGHT:1002311|RIGHT:133.9|RIGHT:1647.5|RIGHT:1.89|?||
|PAQ|5000[sec]以上||RIGHT:748512|RIGHT:100.0|||?||
--いずれも圧縮データを読み込む時間がデコードタイムに加算されてしまっています。
---したがって、tek1やLZOは小さくない誤差を含んでいる可能性が高い。
---試しに1274931バイトのファイルリードだけやらせてみたら0.05[sec]だった。
--「言語」はこの展開速度の測定につかったデコードルーチンの記述言語です。
--たぶんLZOは既にアセンブラ化されていると思います（そうでないとこの圧縮率でこの速さは出ない）。bzip2はアセンブラ化されているかどうかは僕には想像がつきませんが、ブロックソート法では圧縮率の代償として展開速度低下があるという傾向はつかめると思います。
--GCA、gzip、lh7に関しては展開ルーチンの記述言語は不明です。
--t-idx = (time - 0.05) x 10
--score = (t-idx) x (vs_PAQ - 100)
---なんとなく計算してみたくなったので（笑）。小さければ小さいほど圧縮率と展開速度のバランスに優れていることを示していると思う。
--score2 = (t-idx) x (vs_PAQ / 100 - 1)^3
---こっちのほうがいいスケールなのかもしれない。^1や^2だと低圧縮率側がやたらといいことになるし、^4だとLZMAがずば抜けてしまうので、^3あたりが良さそう。もしかしたらこの3には何か理論的な根拠があるのかもしれない。
//---tek4が0.3くらいのバランス値でさらにt-idxの目標を5とおくと、vs_PAQの値は、140弱くらいにするべきだということになる（これはvs_rk換算では114.5に相当）。

-補足（履歴）
--2004.07.05　　方針を変更してtek5を追加
--2004.07.07　　比較基準にPAQを追加
--2004.07.08　　dtk5s.c関係の情報を更新
--2004.07.10　　osask.bmpの圧縮率を修正
--2004.07.11　　stk5、gzip、LZMAの圧縮率を上げる方法がわかったので、修正
--2004.07.12　　dtk5s.ask関係の情報を更新
--2004.07.13　　stk5、LZMAの圧縮率を上げるモードの存在に気がついたので、修正
--2004.07.19　　ちょっとだけsarを追加
--2004.10.10　　tek5を追加

*** 圧縮形式の説明
-無圧縮
-tek0
--引退間近の圧縮形式。今までごくろうさま。旧tek1～3の祖。
-tek1 --- 全てバイトストリーム、主なライバル：LZO
--LZOよりも速い展開速度の圧縮形式。圧縮率はやや劣る場合もあるが、得意不得意の差は小さく、その点でLZOよりも扱いやすい（旧tek3の子孫）。
-tek2 --- ほとんどバイトストリーム・一部ビットストリーム、主なライバル：LZO
--tek1の7割くらいの展開速度の圧縮形式。圧縮率ではLZOをほぼ完全に凌駕し、展開速度の点ではLZOと同等（旧tek3の子孫）。
-tek3 --- ほとんどビットストリーム・一部バイトストリーム、主なライバル：tek0
--tek2のさらに7割くらいの展開速度で、圧縮率を結構追求したもの（旧tek1の子孫）。これはtek0よりも圧縮率がよい。ひょっとすると既にこの段階でlh7よりもいい？''長期にわたってリリース見送り''
-tek4 --- 全てビットストリーム、主なライバル：lh7、gzip、bzip2など （デフォルト推奨）
--tek3のさらに7割くらいの展開速度で、圧縮率をかなり追求したもの（旧tek2の子孫）。lh7やgzipよりも高い圧縮率で、ものによってはLZMAにかなり近い圧縮率になる（予定）。tek1～4の中では一番展開速度が遅いが、それでもtek0やLZMAの2倍くらいは速い。''長期にわたってリリース見送り''
-tek5 --- もちろん全てビットストリーム・レンジコーダ使用
--LZMAを改良したもの
-stk1
--tek1でBS:0かつ補助バッファを使わないもの（subset-tek1）
-stk2
--tek2でBS:0かつ補助バッファを使わないもの（subset-tek2）
-stk5
--tek5でBS:0かつ補助バッファを使わないものでさらにレンジコーダを単純化したもの（subset-tek5）
-lh7
-gzip
-bzip2
-LZMA
-LZO
-rk
-PAQ
--PAQAR 1.3 -5
--http://cs.fit.edu/~mmahoney/compression/
--GPLで公開されている圧縮ソフト。驚異的な圧縮率。ただし圧縮にも展開にも猛烈な時間がかかる。EPIA-VE5000では、bim2bincが90秒以上（圧縮時間は展開時間にほぼ等しい）。その圧縮率はrkの比ではない。デフォルトの-6だと展開にメモリを230MBも消費するため、テスト環境の都合により120MBの-5にしている。

-展開ルーチンのコンパクトさにこだわる人向けの情報
--stk1の展開ルーチンは100行（dtk1s.c）
--stk2の展開ルーチンは161行（dtk2s.c） --- サイズ優先で最適化したら154行になる。
--stk5の展開ルーチンは321行（dtk5s.c）
--tek5の展開ルーチンは528行（dtk5f.c）
--展開速度はフルセット版もサブセット版もほぼ同じ
---stk5は例外で、フルセット版よりも速い
--（参考）
---l2d3の展開ルーチンは107行（マルチスレッド非対応）
---tek0の展開ルーチンは191行（マルチスレッド非対応）
--C言語の行数で考えるのは、単にC言語がビットストリームを効率よく記述できないという言語の欠陥を示しているだけのような気がしてきたので、ASKAで作った展開ライブラリのバイト数も併記します。これこそまさにアルゴリズムの規模を反映しているといえるでしょう。
---なおこれでも、どちらかといえばASKA版はサイズよりも展開速度優先で書かれています。
--stk1の展開ルーチンは270バイト（dtk1s.ask）
--stk2の展開ルーチンは531バイト（dtk2s.ask）
--stk5の展開ルーチンは1426バイト（dtk5s.ask）

* 過去ログ
-[[tek1/oldlog/000]]
-[[tek1/oldlog/001]]

* おまけ
-minna.sar
--とても強いtek5ですが、圧縮率で負けるときももちろんあります（展開速度と圧縮率の両方で負ける例はまだないですが）。
--http://www.emit.jp/dgca/cmptest.html
--のminna.dgcを展開して、sar+tek5してみました。結果は60254バイトでした。
--bz2、gca、dgcというブロックソート系には圧縮率で負けています。負けている部分を中心に圧縮指数を書いておきます。
||無圧縮|PAQ|PPMd|dgc|gca|bz2|sar+tek5|
|サイズ|365066|42366|51665|54080|55929|55933|60254|
|指数|861.7|100.0|121.9|127.6|132.0|132.0|142.2|
--なおこの手のデータにたいしては将来予定しているtek5のバージョンアップで圧縮率が改善する可能性はあります（でもバージョンアップは当分先ですが）。バージョンアップといってももちろんブロックソートを使う気はありませんので展開速度は落ちたりしません（ブロックソートを使ったらそれはもはやtek5ではない！）。
---どのくらい改善するのか実験してみました。一晩ででっちあげた簡単な拡張で、55383(130.7)にできることは確認しました。
---このルーチンですと、bim2bincも12238(132.8)に改善します。
---いつか時間ができたらこれをもっとまともにして正式な拡張にしたいです。
--ちなみにosask.bmpをDGCAにかけると5072バイトです（指数：208.8）。同じブロックソート系ではありますが、bzip2以上に得意不得意が偏っていそうです。

* こめんと欄
-表のヘッダ行が見難いので、勝手ながら一部だけ編集してみました。ちとルール破りですが、一度見て頂いたほうがいいかと思いまして。問題でしたら責任持って元に戻します。(ついでに、配色のご感想などいただければ。(^^;)） -- ''hideyosi'' SIZE(10){2004-10-23 (土) 02:20:24}
-格段に見やすくなりましたね。 -- ''uchan'' SIZE(10){2004-10-23 (土) 15:38:01}
-たての配色は好きだけど、横の配色は罫線がみにくくてちょっといやかも。 -- [[K]] SIZE(10){2004-10-23 (土) 17:16:57}
-ちょっ罫線を弄ってみますた。 -- ''hideyosi'' SIZE(10){2004-10-23 (土) 20:55:32}

#comment

• tek1/comp のバックアップ一覧^[6]
• tek1/comp のバックアップソース(No. All)
  • 1: 2004-06-29 (火) 03:26:47^[7]
  • 2: 2004-06-29 (火) 03:26:47^[8]
  • 3: 2004-06-29 (火) 03:26:47^[9]
  • 4: 2004-06-29 (火) 03:26:47^[10]
  • 5: 2004-07-05 (月) 22:36:52^[11]
  • 6: 2004-07-05 (月) 22:36:52^[12]
  • 7: 2004-07-07 (水) 13:24:10^[13]
  • 8: 2004-07-07 (水) 13:24:10^[14]
  • 9: 2004-07-08 (木) 20:50:27^[15]
  • 10: 2004-07-10 (土) 01:40:26^[16]
  • 11: 2004-07-10 (土) 20:22:31^[17]
  • 12: 2004-07-12 (月) 23:20:01^[18]
  • 13: 2004-07-12 (月) 23:20:01^[19]
  • 14: 2004-07-14 (水) 01:45:48^[20]
  • 15: 2004-07-14 (水) 01:45:48^[21]
  • 16: 2004-07-19 (月) 03:41:41^[22]
  • 17: 2004-10-10 (日) 15:52:29^[23]
  • 18: 2004-10-17 (日) 20:32:12^[24]
  • 19: 2004-10-18 (月) 19:26:47^[25]
  • 20: 2004-10-23 (土) 02:23:00^[26]
  • 21: 2009-11-17 (火) 12:07:37
  • 現: 2024-01-08 (月) 12:59:03^[27] ゲスト