[tek1/comp のバックアップソース(No.4)]

印刷
差分を表示
現在との差分を表示
tek1/comp へ行く。
* [[tek1]]の続き
-(by [[K]], 2004.06.23)
-tek1～tek4の圧縮展開比較表
--MLに書いたら読みにくくなってきたのでこっちにまとめ

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

*** 比較表
-サイズ （num128以外では、tek1～4とstk1～4はほぼ同じなので、stk1～4は省略）
||無圧縮|tek0|tek1|tek2|tek3|tek4|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:27||RIGHT:86|RIGHT:49|RIGHT:43|RIGHT:39|RIGHT:91|RIGHT:100|
|zero64k|RIGHT:65536|RIGHT:28|RIGHT:27|RIGHT:29|RIGHT:30||RIGHT:117|RIGHT:108|RIGHT:43|RIGHT:90|RIGHT:422|RIGHT:108|
|bim2binc|RIGHT:53792|RIGHT:15019|RIGHT:17166|RIGHT:16323|RIGHT:14424||RIGHT:14181|RIGHT:14029|RIGHT:12903|RIGHT:12787|RIGHT:16015|RIGHT:11608|
|kdun00b|RIGHT:655360|RIGHT:46246|RIGHT:49855|RIGHT:46794|RIGHT:41432||RIGHT:45520|RIGHT:44589|RIGHT:47306|RIGHT:34517|RIGHT:52148|RIGHT:36736|
|osaskgo|RIGHT:1973741|RIGHT:1149662|RIGHT:1274931|RIGHT:1172344|RIGHT:1087673||RIGHT:1099064|RIGHT:1111648|RIGHT:1047411|RIGHT:953821|RIGHT:1177820|RIGHT:909824|
|osask.bmp|RIGHT:393334|RIGHT:6389|RIGHT:7740|RIGHT:7135|RIGHT:5633||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|stk3|tek3|stk4|tek4|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:108.0|RIGHT:108.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:111.1|RIGHT:111.1|||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:124.3|RIGHT:124.3|121.7?||RIGHT:122.2|RIGHT:120.9|RIGHT:111.2|RIGHT:110.2|RIGHT:138.0|RIGHT:100.0|
|kdun00b|RIGHT:1899|RIGHT:134.0|RIGHT:144.4|RIGHT:144.4|RIGHT:135.6|RIGHT:135.6|RIGHT:120.0|RIGHT:120.0|117.8?||RIGHT:131.9|RIGHT:129.2|RIGHT:137.1|RIGHT:100.0|RIGHT:151.1|RIGHT:106.4|
|osaskgo|RIGHT:216.9|RIGHT:126.4|RIGHT:140.1|RIGHT:140.1|RIGHT:128.9|RIGHT:128.9|RIGHT:119.5|RIGHT:119.5|?||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:129.7|RIGHT:129.7|120.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:129.7|RIGHT:129.7|||RIGHT:148.9|RIGHT:146.0|RIGHT:137.1|RIGHT:110.2|RIGHT:198.4|RIGHT:106.4|
--(max)は、bim2binc、kdun00b、osaskgo、osask.bmpのみ対象（他はあまりにtek系が得意なため除外）
--(max)で判断すると安定して圧縮率のよいものは以下の順になる。
|rk|LZMA|tek4|stk4|tek3|stk3|bzip2|gzip|tek0|lh7|tek2|stk2|tek1|stk1|LZO|
|106.4|110.2|||129.7|129.7|137.1|146.0|147.0|148.9|164.2|164.2|178.2|178.2|198.4|
--↑これは主にosask.bmpの結果で決まっているともいえるので、参考までにosask.bmpを除いて集計すると以下のようになる。
---しかし、「汎用圧縮符号」としては弱点があるというのは好ましくない。そしてosask.bmpの内容は多くの符号の共通の弱点を突く内容なのだろう。
|rk|LZMA|tek4|stk4|tek3|stk3|gzip|lh7|tek0|bzip2|tek2|stk2|tek1|stk1|LZO|
|106.4|110.2|||124.3|124.3|129.2|131.9|134.0|137.1|140.6|140.6|147.8|147.8|151.1|
---bzip2が落ちてlh7が少し回復する以外は、順位そのものの傾向は変わらない。
-tar+tek4（.tar.tk/.ttk）
||tar|ttk|lh7|tgz|tbz|tar.lzma|
|bim2bi4j|RIGHT:266725||RIGHT:902616|RIGHT:84581|RIGHT:72747|RIGHT:65314|
|osat45i|RIGHT:759808||RIGHT:532093|RIGHT:528923|RIGHT:547131|RIGHT:503545|
|[[cantrbry:http://corpus.canterbury.ac.nz/descriptions/]]|RIGHT:2821120||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]|
|tek3|0.51[sec]|RIGHT:4.6|RIGHT:1087673|119.5|RIGHT:89.7|C|ASKA版開発中|
|tek4||||||C||
|lh7|1.04[sec]|RIGHT:9.9|1099064|120.8|RIGHT:205.9|?||
|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.06.23　　tek1～tek3の全面刷新により、いったん出直し。
---2004.06.24　　tek2の情報を記載
---2004.06.26　　tek2の情報を改定
---2004.06.28　　tek3の情報を記載
---2004.07.03　　kdun00bの規格化指数を計算ミスしていたので修正

*** 圧縮形式の説明
-無圧縮
-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倍くらいは速い。
-stk1
--tek1でBS:0かつ補助バッファを使わないもの（subset-tek1）
-stk2
--tek2でBS:0かつ補助バッファを使わないもの（subset-tek2）
-stk3
--tek3でBS:0かつ補助バッファを使わないもの（subset-tek3）
-lh7
-gzip
-bzip2
-LZMA
-LZO
-rk

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

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

* こめんと欄
-これだけ見てデコードルーチンの簡単さ、圧縮率を総合評価するとtek0が圧勝じゃない？こんな結果でいいのか？ -- [[名無しさん]] SIZE(10){2004-06-24 (木) 17:15:00}
-（[[tek1]]系のページは議論向きではないので、こういう意見は是非[[impressions]]や[[room/000]]にお願いします。） -- [[K]] SIZE(10){2004-06-24 (木) 17:29:36}
-tek1～tek3の名称が展開速度の順で再整理されたってことですよね?(これに関して記事を書くかもしれないので確認) -- ''Zakky'' SIZE(10){2004-06-24 (木) 18:41:19}
-はいそうです。このページは数日後にリリースされるbim2bin4の告知の際に投稿するOSASK-MLの内容を（結果的に先取りして）書いています。ここでは詳細なデータばかりでなぜ再整理するのかの理由などがありませんが、それはMLの本文のほうに書く予定なので、ご了承ください。＞Zakkyさん -- [[K]] SIZE(10){2004-06-24 (木) 19:32:24}

#comment
« Prev Next »
tek1/comp のバックアップ一覧
tek1/comp のバックアップソース(No. All)
tek1​/comp のバックアップソース(No.4) :: OSASK計画

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