サイトトップへ
OSASK.NET
  サイトトップへ       新掲示板(閉鎖済)   Wiki(凍結済)   旧掲示板(廃止済)   ニュース(廃止済)  

tek1の続き anchor.png

  • (by K, 2004.07.05)
  • tek1~tek5の圧縮展開比較表
    • MLに書いたら読みにくくなるのでデータだけこっちでまとめ
Page Top

比較表 anchor.png

  • サイズ (num128以外では、tek1~2とstk1~2はほぼ同じなので、stk1~2は省略)
    無圧縮tek0tek1tek2stk5tek5lh7gzipbzip2LZMALZOrkPAQ
    hellok1272128144135126124205143166121193208116
    zero4k40962725252828864943399110030
    zero64k655362827292929117108439042210843
    bim2binc5379215019171661632312712125791418113467129031270816015116089215
    kdun00b655360462464985546794335493290945520425534730634037521483673629157
    osaskgo19737411149662127493111723449423759369281099064108787410474119423691177820909824748512
    osask.bmp393334638977407135386036696467568749064236861843442429
    num1281310721069536603611854812464525542842371311361192
  • 規格化指数
    無圧縮tek0stk1tek1stk2tek2stk5tek5lh7gzipbzip2LZMALZOrkPAQ
    hellok1234.5110.3124.1124.1116.4116.4108.6106.9176.7123.3143.1104.3166.4179.3100.0
    zero4k16384108.0100.0100.0100.0100.0112.0112.0344.0196.0172.0156.0364.0400.0120.0
    zero64k242726103.7100.0100.0107.4107.4107.4107.4433.3400.0159.3333.31563400.0159.3
    bim2binc583.7163.0186.3186.3177.1177.1137.9136.5153.9146.1140.0137.9173.8126.0100.0
    kdun00b2248158.6171.0171.0160.5160.5115.1112.9156.1145.9162.2116.7178.9126.0100.0
    osaskgo263.7153.6170.3170.3156.6156.6125.9125.2146.8145.3139.9125.9157.4121.5100.0
    osask.bmp16193263.0318.6318.6293.7293.7158.9151.0266.2234.1202.0174.4354.8178.8100.0
    num12832768026738329637031161363855210593328402980
    (max)263.0318.6318.6293.7293.7158.9151.0266.2234.1202.0174.4354.8178.8100.0
    • (max)は、bim2binc、kdun00b、osaskgo、osask.bmpのみ対象(他はあまりにtek系が得意なため除外)
    • (max)で判断すると安定して圧縮率のよいものは以下の順になる。
      PAQtek5stk5LZMArkbzip2gziptek0lh7tek2stk2tek1stk1LZO
      100.0151.0158.9174.4178.8202.0234.1263.0266.2293.7293.7318.6318.6354.8
    • ↑これは完全にosask.bmpの結果で決まっているともいえるので、参考までにosask.bmpを除いて集計すると以下のようになる。
      • しかし、「汎用圧縮符号」としては弱点があるというのは好ましくない。そしてosask.bmpの内容は多くの符号の共通の弱点を突く内容なのだろう。
        PAQrktek5LZMAstk5gziplh7bzip2tek0tek2stk2LZOtek1stk1
        100.0126.0136.5137.9137.9146.1156.1162.2163.0177.1177.1178.9186.3186.3
      • 全体的にtek系が少し落ちて、rkがあがってbzip2が落ちる程度で、それほど傾向は変わらない。
  • tar+stk5(.tar.tk/.ttk)、sar(sar+stk5)
    tarttksarlh7tgztbztar.lzma
    bim2bi4j26672565255902616845817274765314
    osat45i759808503442502423532093528923547131503545
    cantrbry2821120482972714769735997568667483768
  • 展開速度
    • 参考:EPIA-VE5000でのosaskgoの展開速度
      meth.deco.timet-idxsizevs PAQscorescore2言語備考
      tek10.15[sec]1.01274931170.370.30.35ASKACでは0.18[sec]
      LZO0.18[sec]1.31177820157.474.60.25?←おそらくasm
      tek20.18[sec]1.31172344156.673.60.24ASKACでは0.27[sec]
      lh71.04[sec]9.91099064146.8463.31.01?
      stk51.18[sec]11.3953743127.40.23ASKACでは1.37[sec]
      gzip1.24[sec]11.91087874145.31.11?
      stk51.39[sec]13.4942375125.90.23ASKACでは1.63[sec]
      tek01.39[sec]13.41149662153.6734.32.06C
      LZMA1.42[sec]13.7953728127.4375.40.28C
      LZMA1.66[sec]16.1942369125.90.28C
      bzip22.52[sec]24.71047411139.9985.51.57?
      GCA4.91[sec]48.61002311133.91647.51.89?
      PAQ5000[sec]以上748512100.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を追加
Page Top

圧縮形式の説明 anchor.png

  • 無圧縮
  • 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)
Page Top

おまけ anchor.png

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

こめんと欄 anchor.png

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

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

目次
メンバー一覧


最新の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コミュニティによって管理・運営されています。