tek1​/comp :: OSASK計画

tek1^[1]の続き ^[2]

• (by K^[3], 2004.07.05)

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

比較表 ^[4]

• サイズ （num128以外では、tek1～2とstk1～2はほぼ同じなので、stk1～2は省略）

  無圧縮		tek0	tek1	tek2	stk5	tek5	lh7	gzip	bzip2	LZMA	LZO	rk	PAQ
  hellok1	272	128	144	135	126	124	205	143	166	121	193	208	116
  zero4k	4096	27	25	25	28	28	86	49	43	39	91	100	30
  zero64k	65536	28	27	29	29	29	117	108	43	90	422	108	43
  bim2binc	53792	15019	17166	16323	12712	12579	14181	13467	12903	12708	16015	11608	9215
  kdun00b	655360	46246	49855	46794	33549	32909	45520	42553	47306	34037	52148	36736	29157
  osaskgo	1973741	1149662	1274931	1172344	942375	936928	1099064	1087874	1047411	942369	1177820	909824	748512
  osask.bmp	393334	6389	7740	7135	3860	3669	6467	5687	4906	4236	8618	4344	2429
  num128	131072	106953			66036		118548	124645	25542	84237	131136	1192

  • • 細かい圧縮条件をこちらにまとめました。→tek1​/comp​/opt^[5]

• 規格化指数

  無圧縮		tek0	stk1	tek1	stk2	tek2	stk5	tek5	lh7	gzip	bzip2	LZMA	LZO	rk	PAQ
  hellok1	234.5	110.3	124.1	124.1	116.4	116.4	108.6	106.9	176.7	123.3	143.1	104.3	166.4	179.3	100.0
  zero4k	16384	108.0	100.0	100.0	100.0	100.0	112.0	112.0	344.0	196.0	172.0	156.0	364.0	400.0	120.0
  zero64k	242726	103.7	100.0	100.0	107.4	107.4	107.4	107.4	433.3	400.0	159.3	333.3	1563	400.0	159.3
  bim2binc	583.7	163.0	186.3	186.3	177.1	177.1	137.9	136.5	153.9	146.1	140.0	137.9	173.8	126.0	100.0
  kdun00b	2248	158.6	171.0	171.0	160.5	160.5	115.1	112.9	156.1	145.9	162.2	116.7	178.9	126.0	100.0
  osaskgo	263.7	153.6	170.3	170.3	156.6	156.6	125.9	125.2	146.8	145.3	139.9	125.9	157.4	121.5	100.0
  osask.bmp	16193	263.0	318.6	318.6	293.7	293.7	158.9	151.0	266.2	234.1	202.0	174.4	354.8	178.8	100.0
  num128	327680	267383							296370	311613	63855	210593	32840	2980
  (max)		263.0	318.6	318.6	293.7	293.7	158.9	151.0	266.2	234.1	202.0	174.4	354.8	178.8	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が落ちる程度で、それほど傾向は変わらない。
• tar+stk5（.tar.tk/.ttk）、sar(sar+stk5)

  tar		ttk	sar	lh7	tgz	tbz	tar.lzma
  bim2bi4j	266725	65255		902616	84581	72747	65314
  osat45i	759808	503442	502423	532093	528923	547131	503545
  cantrbry[6]	2821120	482972		714769	735997	568667	483768

  • ディスクイメージへの強さが、tarへの強さにつながったのかも？
  • ロングファイルネーム対応のSF16ができるまで.img.tk(.itk)は不便だろうから、とりあえず.tar.tk(.ttk)で。
  • cantrbryはよく分からないけど有名な圧縮対象のようです。
    • http://www.emit.jp/gca/cmptest.html^[7]
    • http://compression.ca/act-canterbury.html^[8]

• 展開速度
  • 参考：EPIA-VE5000でのosaskgoの展開速度

    meth.	deco.time	t-idx	size	vs PAQ	score	score2	言語	備考
    tek1	0.15[sec]	1.0	1274931	170.3	70.3	0.35	ASKA	Cでは0.18[sec]
    LZO	0.18[sec]	1.3	1177820	157.4	74.6	0.25	?	←おそらくasm
    tek2	0.18[sec]	1.3	1172344	156.6	73.6	0.24	ASKA	Cでは0.27[sec]
    lh7	1.04[sec]	9.9	1099064	146.8	463.3	1.01	?
    stk5	1.18[sec]	11.3	953743	127.4		0.23	ASKA	Cでは1.37[sec]
    gzip	1.24[sec]	11.9	1087874	145.3		1.11	?
    stk5	1.39[sec]	13.4	942375	125.9		0.23	ASKA	Cでは1.63[sec]
    tek0	1.39[sec]	13.4	1149662	153.6	734.3	2.06	C
    LZMA	1.42[sec]	13.7	953728	127.4	375.4	0.28	C
    LZMA	1.66[sec]	16.1	942369	125.9		0.28	C
    bzip2	2.52[sec]	24.7	1047411	139.9	985.5	1.57	?
    GCA	4.91[sec]	48.6	1002311	133.9	1647.5	1.89	?
    PAQ	5000[sec]以上		748512	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には何か理論的な根拠があるのかもしれない。

• 補足（履歴）
  • 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を追加

圧縮形式の説明 ^[9]

• 無圧縮
• 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/^[10]
  • 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）

過去ログ ^[11]

• tek1​/oldlog​/000^[12]
• tek1​/oldlog​/001^[13]

おまけ ^[14]

• minna.sar
  • とても強いtek5ですが、圧縮率で負けるときももちろんあります（展開速度と圧縮率の両方で負ける例はまだないですが）。
  • http://www.emit.jp/dgca/cmptest.html^[15]
  • の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以上に得意不得意が偏っていそうです。

こめんと欄 ^[16]

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