tek1​/comp のバックアップソース(No.6) :: 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～5とstk1～5はほぼ同じなので、stk1～5は省略）
||無圧縮|tek0|tek1|(tek2)|tek5|lh7|gzip|bzip2|LZMA|LZO|rk|
|hellok1|RIGHT:272|RIGHT:128|RIGHT:144|RIGHT:135|RIGHT:126|RIGHT:205|RIGHT:143|RIGHT:166|RIGHT:121|RIGHT:193|RIGHT:208|
|zero4k|RIGHT:4096|RIGHT:27|RIGHT:25|RIGHT:25|RIGHT:28|RIGHT:86|RIGHT:49|RIGHT:43|RIGHT:39|RIGHT:91|RIGHT:100|
|zero64k|RIGHT:65536|RIGHT:28|RIGHT:27|RIGHT:29|RIGHT:29|RIGHT:117|RIGHT:108|RIGHT:43|RIGHT:90|RIGHT:422|RIGHT:108|
|bim2binc|RIGHT:53792|RIGHT:15019|RIGHT:17166|RIGHT:16323|RIGHT:12795|RIGHT:14181|RIGHT:14029|RIGHT:12903|RIGHT:12787|RIGHT:16015|RIGHT:11608|
|kdun00b|RIGHT:655360|RIGHT:46246|RIGHT:49855|RIGHT:46794|RIGHT:33944|RIGHT:45520|RIGHT:44589|RIGHT:47306|RIGHT:34517|RIGHT:52148|RIGHT:36736|
|osaskgo|RIGHT:1973741|RIGHT:1149662|RIGHT:1274931|RIGHT:1172344|RIGHT:953828|RIGHT:1099064|RIGHT:1111648|RIGHT:1047411|RIGHT:953821|RIGHT:1177820|RIGHT:909824|
|osask.bmp|RIGHT:393334|RIGHT:6389|RIGHT:7740|RIGHT:7135|RIGHT:4361|RIGHT:6467|RIGHT:6341|RIGHT:4906|RIGHT:4779|RIGHT:8618|RIGHT:4344|
|num128|RIGHT:131072|RIGHT:106953||||RIGHT:118548|RIGHT:124645|RIGHT:25542|RIGHT:84237|RIGHT:131136|RIGHT:1192|

-規格化指数
||無圧縮|tek0|stk1|tek1|(stk2)|(tek2)|stk5|tek5|lh7|gzip|bzip2|LZMA|LZO|rk|
|hellok1|RIGHT:224.8|RIGHT:105.8|RIGHT:119.0|RIGHT:119.0|RIGHT:111.6|RIGHT:111.6|RIGHT:104.1|RIGHT:104.1|RIGHT:169.4|RIGHT:118.2|RIGHT:137.2|RIGHT:100.0|RIGHT:159.5|RIGHT:171.9|
|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|
|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|
|bim2binc|RIGHT:463.4|RIGHT:129.4|RIGHT:147.9|RIGHT:147.9|RIGHT:140.6|RIGHT:140.6|RIGHT:110.2|RIGHT:110.2|RIGHT:122.2|RIGHT:120.9|RIGHT:111.2|RIGHT:110.2|RIGHT:138.0|RIGHT:100.0|
|kdun00b|RIGHT:1931|RIGHT:136.2|RIGHT:146.9|RIGHT:146.9|RIGHT:137.9|RIGHT:137.9|RIGHT:100.0|RIGHT:100.0|RIGHT:134.1|RIGHT:131.4|RIGHT:139.4|RIGHT:101.7|RIGHT:153.6|RIGHT:108.2|
|osaskgo|RIGHT:216.9|RIGHT:126.4|RIGHT:140.1|RIGHT:140.1|RIGHT:128.9|RIGHT:128.9|RIGHT:104.8|RIGHT:104.8|RIGHT:120.8|RIGHT:122.2|RIGHT:115.1|RIGHT:104.8|RIGHT:129.5|RIGHT:100.0|
|osask.bmp|RIGHT:9055|RIGHT:147.0|RIGHT:178.2|RIGHT:178.2|RIGHT:164.2|RIGHT:164.2|RIGHT:100.4|RIGHT:100.4|RIGHT:148.9|RIGHT:146.0|RIGHT:112.9|RIGHT:110.0|RIGHT:198.4|RIGHT:100.0|
|num128|RIGHT:327680|RIGHT:267383|||||||RIGHT:296370|RIGHT:311613|RIGHT:63855|RIGHT:210593|RIGHT:32840|RIGHT:2980|
|(max)||RIGHT:147.0|RIGHT:178.2|RIGHT:178.2|RIGHT:164.2|RIGHT:164.2|RIGHT:110.2|RIGHT:110.2|RIGHT:148.9|RIGHT:146.0|RIGHT:137.1|RIGHT:110.2|RIGHT:198.4|RIGHT:108.2|
--(max)は、bim2binc、kdun00b、osaskgo、osask.bmpのみ対象（他はあまりにtek系が得意なため除外）
--(max)で判断すると安定して圧縮率のよいものは以下の順になる。
|rk|LZMA|tek5|stk5|bzip2|gzip|tek0|lh7|(tek2)|(stk2)|tek1|stk1|LZO|
|108.2|110.2|110.2|110.2|139.4|146.0|147.0|148.9|164.2|164.2|178.2|178.2|198.4|
--↑これは主にosask.bmpの結果で決まっているともいえるので、参考までにosask.bmpを除いて集計すると以下のようになる。
---しかし、「汎用圧縮符号」としては弱点があるというのは好ましくない。そしてosask.bmpの内容は多くの符号の共通の弱点を突く内容なのだろう。
|rk|LZMA|tek5|stk5|gzip|lh7|tek0|bzip2|(tek2)|(stk2)|tek1|stk1|LZO|
|108.2|110.2|110.2|110.2|131.4|134.1|136.2|139.4|140.6|140.6|147.8|147.8|153.6|
---bzip2が落ちてlh7が少し回復する以外は、順位そのものの傾向は変わらない。
-tar+tek5（.tar.tk/.ttk）
||tar|ttk|lh7|tgz|tbz|tar.lzma|
|bim2bi4j|RIGHT:266725|RIGHT:65255|RIGHT:902616|RIGHT:84581|RIGHT:72747|RIGHT:65314|
|osat45i|RIGHT:759808|RIGHT:503442|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 rk|score|言語|備考|
|tek1|0.15[sec]|RIGHT:1.0|RIGHT:1274931|140.1|RIGHT:40.1|ASKA|Cでは0.18[sec]|
|LZO|0.18[sec]|RIGHT:1.3|RIGHT:1177820|129.5|RIGHT:38.4|?|←おそらくasm|
|(tek2)|0.18[sec]|RIGHT:1.3|RIGHT:1172344|128.9|RIGHT:37.6|ASKA|Cでは0.27[sec]|
|lh7|1.04[sec]|RIGHT:9.9|1099064|120.8|RIGHT:205.9|?||
|tek5|||RIGHT:953828|104.8||||
|gzip|1.24[sec]|RIGHT:11.9|RIGHT:1111684|122.2|RIGHT:264.2|?||
|tek0|1.39[sec]|RIGHT:13.4|1149662|126.4|RIGHT:353.8|C||
|LZMA|1.42[sec]|RIGHT:13.7|RIGHT:953821|104.8|RIGHT:65.8|C||
|bzip2|2.52[sec]|RIGHT:24.7|1047411|115.1|RIGHT:373.0|?||
|GCA|4.91[sec]|RIGHT:48.6|1002311|110.2|RIGHT:495.7|?||
--いずれも圧縮データを読み込む時間がデコードタイムに加算されてしまっています。
---したがって、tek1やLZOは小さくない誤差を含んでいる可能性が高い。
---試しに1274931バイトのファイルリードだけやらせてみたら0.05[sec]だった。
--「言語」はこの展開速度の測定につかったデコードルーチンの記述言語です。
--たぶんLZOは既にアセンブラ化されていると思います（そうでないとこの圧縮率でこの速さは出ない）。bzip2はアセンブラ化されているかどうかは僕には想像がつきませんが、ブロックソート法では圧縮率の代償として展開速度低下があるという傾向はつかめると思います。
--GCA、gzip、lh7に関しては展開ルーチンの記述言語は不明です。
--t-idx = (time - 0.05) x 10
--score = (t-idx) x (vs_rk - 100)
---なんとなく計算してみたくなったので（笑）。小さければ小さいほど圧縮率と展開速度のバランスに優れていることを示していると思う。

--補足（履歴）
---2004.07.05　　方針を変更して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

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

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

* こめんと欄

#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
  • 7: 2004-07-07 (水) 13:24:10^[12]
  • 8: 2004-07-07 (水) 13:24:10^[13]
  • 9: 2004-07-08 (木) 20:50:27^[14]
  • 10: 2004-07-10 (土) 01:40:26^[15]
  • 11: 2004-07-10 (土) 20:22:31^[16]
  • 12: 2004-07-12 (月) 23:20:01^[17]
  • 13: 2004-07-12 (月) 23:20:01^[18]
  • 14: 2004-07-14 (水) 01:45:48^[19]
  • 15: 2004-07-14 (水) 01:45:48^[20]
  • 16: 2004-07-19 (月) 03:41:41^[21]
  • 17: 2004-10-10 (日) 15:52:29^[22]
  • 18: 2004-10-17 (日) 20:32:12^[23]
  • 19: 2004-10-18 (月) 19:26:47^[24]
  • 20: 2004-10-23 (土) 02:23:00^[25]
  • 21: 2009-11-17 (火) 12:07:37^[26]
  • 現: 2024-01-08 (月) 12:59:03^[27] ゲスト