tek :: OSASK計画

tekのページ ^[1]

• (by K^[2], 2004.11.15)
• ここは対外的なページではなく、いろいろな議論とか不確定情報とかも話題にできるページ。
  • 対外的なページは[[Z:tek]]。

Kの基本方針 ^[3]

• つまり他の人にとっては「Kが推奨する方針」くらいの意味です。

• l2d3とtek0はフェードアウト。
  • ただし過去のバージョンでl2d3やtek0をサポートしたことあるアプリについては、例外的にサポートを続ける。

tek対応状況 ^[4]

• 厳密にはosacmp対応状況

• Windowsアプリ
  • edimg0h以降で l2d3/tek0/tek1/tek2/tek5 に対応。
  • obj2bim4b以降で tek0/tek1/tek2/tek5 に対応。
    • このobj2bim4は、tolset08に入っている。
  • sartol0i以降で tek1/tek2/tek5 に対応。
  • Susieプラグイン spibmpk1.spi で tek1/tek2/tek5 に対応。
    • このプラグインはBMPのプラグイン（8bitカラー、24bitカラー）。
    • Susieは拡張子ではなくファイルの中身でフォーマット判定をする仕様なので、.bmpでも、.bmp.tek5とかでもどちらでもOK。

• POSIX（Linuxとか）アプリ
  • (まだ書いてない)

• そのほか
  • OSASK
    • OSASK ver.4.6以降で tek0/tek1/tek2/stk5 に対応。
    • OSASK ver.4.7（Twicth4）以降で tek0/tek1/tek2/tek5 に対応。
    • shibai1aが、 tek1/tek2/tek5 の2重圧縮に対応。
  • Mona
    • 拡張子の変更が必要になるが、Mona 0.2.0では stk5 に対応。

リンク ^[5]

• [[Z:tek]]
  • 対外向けtekページ。他の圧縮形式との定量的な比較あり。
• tek5​/rangecoder^[6]
  • tek5で使われているレンジコーダの紹介。
• room​/000^[7]
  • 圧縮しないのは非常識か？
• why_sar^[8]
  • sarの紹介だが、一番下に他の圧縮形式との定量的な比較がある。
• tek1^[9]
  • かなり古い内容のページ（tek1​/comp^[10]以外はほとんど現状を反映していない）。
    • tek1​/comp^[10]にも、他の圧縮形式との定量的な比較がある。
• tek2^[11]、tek3^[12]
  • これもまた古い内容のページ。全く現状を反映していない。
• tek​/history^[13]
  • これはおすすめしません（これを読んだらかえって混乱すると思う）。

• (まだ他にもたくさんあるのでちょくちょく書き足します。)

その他のリンク ^[14]

• 自分でtekに関するページを作ったら、自発的にURLとちょっとした紹介（1行程度）を書き足そう！
  • この欄に限り、書き足し自由＆自分が書いた文章の編集も自由。
• たまにKがこの欄にあるリンクを上のリンクへ引き上げます。
  
  
  
  
• [[dev-j:t5exe]] 大したものじゃないから追加するのも引けたけど。Unix風味環境(ELFとかPEとか関係ないのでcygwinでも動くのかな?)で実行ファイルを圧縮できます。

OS-Wikiのtekのページの旧内容 ^[15]

• 一時退避的にここにおきます。

tekフォーマット誕生のいきさつと目的など ^[16]

• もともとtekはOSASKの実行ファイル内の.dataセクション内の0x00のかたまりの部分を、他のOSと同等程度の手ごろな大きさにまとめたいという必要から開発がはじまった。
  • この問題はOSASKに限らず他のOSでも発生している。win32やLinuxでは、.bssセクションは必ずゼロクリアされるというルールを設けることで、この問題を解決しているようである。
• ただ0x00をまとめるだけならランレングス圧縮でもつければそれでよかったのだが、.dataセクション内の初期値群はもしかしたらintで1のかたまりの部分があったりするかもしれず、そういう場合も圧縮できたらちょっとかっこいいかなと思い、軽い気持ちでごく簡単なスライド辞書式のLZ圧縮を採用してみた。OSASKのAPIにはLZ圧縮を解くためのAPIがあり、アプリのスタートアップルーチンがこのAPIを呼んで.dataセクションを初期化するという仕組みになっている。
• これで結果的にOSがサービスの一部として圧縮展開用のルーチンを持つことになった。どうせならもっとこのルーチンを活用してやろうということで、ファイルアクセスの際に圧縮されているかどうかのチェックを自動でやるようにして、圧縮されていればOSが内部で自動展開し、圧縮の有無をアプリに感知させることなくシームレスにアクセスできるようにしてみた（圧縮しても拡張子を変える必要はない）。これが大成功で、あらゆるアプリもあらゆるデータもコンパクトになった。ディスクアクセス時間も大幅に短縮された。
• またアプリも単純化された。たとえば画像ファイルを考える場合、OSASKではBMPだけをサポートしていればたいていの用途にかなう。しかもBMPもRLE圧縮のサポートはなくてもそれほど問題ではない。もちろん、TIFやGIFやPNGなどもサポートすればそれに越したことはないが、そんなものがなくても、適当なツールで画像を一度無圧縮BMPに変換し、それをtekで圧縮すればそれでいいわけである。一般的な傾向として、tek圧縮のほうがTIFやGIFやPNGよりも圧縮率がよく、展開も速いからである。
• こうしてOSが圧縮を積極的にサポートする効用に気がついたため、この技術をOSASKというOSに限定されない技術とし、展開ルーチンライブラリの開発や、フォーマットの改良などを行っている。

• このようないきさつのため、tekフォーマットの目的は次のようになっている。
  • 汎用圧縮フォーマットであることを追及する。特定の対象にのみ強いフォーマットにはならないようにする。
  • 展開に必要なリソースに配慮する。tekフォーマットの意図するところは、GIFやTIFなどの代用的なものであり、アーカイバのような書庫管理ではない。つまり展開速度は十分に速くなくてはならないし、展開時に大量のワークエリアが必要であったりしてもいけない（もし展開のためのリソースが多ければ、その画像やデータなどを直接閲覧できない場合が発生してしまう）。もちろんtekは画像ファイル限定ではなく、テキストも実行バイナリも各アプリのセーブデータも、その他のなんにでも適用可能で、一様に利益をもたらす。
    • なおアーカイブ用途としては、sarという形式を提唱している（sarはtarのような無圧縮規格であるがもちろんtekを適用してもよく、実際sarファイルのほとんど全てはtekが掛かった状態で扱われている）。 参考→why_sar^[8]
  • 非常に著名な圧縮形式では、圧縮を明示的に解かなくても内容を自由に閲覧できるツールが開発されているが、tekはそういう利用を最初から前提にして、この分野でのデファクトスタンダードなフォーマットになるのを目指している。圧縮しても拡張子を変えないでよい（＝それくらい冗長なシグネチャがある）というのもそのためである。OSASKのようにOSレベルでの自動展開サポートが普及するか、それが無理なOSでは各アプリがファイルオープンの際に先頭16バイトをチェックし、tekであれば展開した後に扱う機能が普及してほしいと思っている。
  • この流れにより、現在のように多種多様な形式が乱立するのではなく、シンプルなフォーマットを（必要に応じて）共通の汎用アルゴリズムで圧縮する、という流れになればと思う。もちろんtek圧縮は完璧ではないし、対象によってはより圧縮率の高いものやより高速に展開できるものもあるだろうが、現状ではtekに劣るものがまだたくさんあるというのも事実である。tekに劣る形式が徐々にフェードアウトしてtekに一本化されれば、展開ルーチンの最適化はさらに進むであろうし、もしかしたらJPEGやMPEGのようにデコード支援用のハードウェアが開発されるかもしれない（tekの展開アルゴリズムはワークエリアが少なくて済むので、ハードウェア化もしやすいかもしれない）。
  • なお今のところ圧縮時間に関してはほとんど配慮していない。それは目的とは直接関係ないからである。したがって、圧縮時間も重要になるような用途には多分向かない。まあしかし、圧縮率を犠牲にしてもいいのなら、いくらでも圧縮時間は短縮できるであろう。
  • そして圧縮の世界もtekを超える基準での競争に限定されることで、より発展していくだろう。

バリエーション ^[17]

• 開発済みの形式
  • tek0：tek系初代の形式
    • 展開アルゴリズムの単純さ、展開速度、圧縮率、の3つのどれにおいてもいまいちぱっとしない。補助バッファ利用圧縮やマルチブロック拡張機能などもない。
  • tek1：展開速度・展開アルゴリズムの単純さをもっとも追求した形式
    • 圧縮率はかなり低い。
    • stk1仕様なら展開ルーチンは270バイトで書ける。
    • フルセット仕様の中には未だ開発検討中で確定していない部分もある。
  • tek2：tek1の展開速度を2～5割ほど犠牲にして圧縮率を改善した形式
    • stk2仕様なら展開ルーチンは531バイトで書ける。
  • tek5：圧縮率をもっとも追求した形式
    • その圧縮率はほとんどのケースでgzipやbzip2を超える。展開速度の点でもこれらに対して引けを取らない。LZMAをアルゴリズムの基礎においているが、改良を加えているためLZMAよりも高速・高圧縮率になる傾向が強い（LZMAより高速なのはstk5のみ）。
    • stk5仕様なら展開ルーチンは1426バイトで書ける。

ベンチマーク ^[18]

• tekのそれぞれについての簡単なベンチマークです

• • • paqarは展開時間がきわめて長く、さらに膨大なワークスペースを要求するために、上記の形式と同列で比較するべきではないと思うが、それぞれのデータがどこまで圧縮できるかを示す指標として導入した。まだ圧縮の余地があるのに圧縮できていない場合を発見するのに役立つ。
      
      
• サイズ

  osaskbmp		kdun00b	bim2binc	osaskgo	zero64k
  無圧縮	393334	655360	53792	1973741	65536
  LZO	8618	52148	16015	1177820	422
  stk1	7740	49855	17166	1274931	27
  stk2	7135	46794	16323	1172344	29
  lh7	6467	45520	14181	1099064	117
  tek0	6389	46246	15019	1149662	28
  gzip	5687	42553	13467	1087874	108
  PPMd	5609	39546	11099	966659	151
  dgc	5072	43216	12624	986880	528
  bzip2	4906	47306	12903	1047411	43
  LZMA	4236	34037	12708	942369	90
  stk5	3860	33549	12712	942375	29
  tek5	3669	32909	12579	936928	29
  paqar	2429	29157	9215	748512	43

• 規格化指数（上記でそれぞれの一位が100になるように規格化しただけのもの）

  osaskbmp		kdun00b	bim2binc	osaskgo	zero64k
  無圧縮	16193	2248	583.7	263.7	242726
  LZO	354.8	178.9	173.8	157.4	1563
  stk1	318.6	171.0	186.3	170.3	100.0
  stk2	293.7	160.5	177.1	156.6	107.4
  lh7	266.2	156.1	153.9	146.8	433.3
  tek0	263.0	158.6	163.0	153.6	103.7
  gzip	234.1	145.9	146.1	145.3	400.0
  PPMd	230.9	135.6	120.4	129.1	559.3
  dgc	208.8	148.2	137.0	131.8	1956
  bzip2	202.0	162.2	140.0	139.9	159.3
  LZMA	174.4	116.7	137.9	125.9	333.3
  stk5	158.9	115.1	137.9	125.9	107.4
  tek5	151.0	112.9	136.5	125.2	107.4
  paqar	100.0	100.0	100.0	100.0	159.3

• • tek5については、why_sar^[8]にも圧縮率比較データがあります。
  • さらにテスト：[[Z:tek/dump]]

• 展開速度
  • （準備中）

解説 ^[20]

• 圧縮率比較方法に関するK^[2]の主張。

• 一般的には圧縮の比較といえば圧縮率の比較をすると思うが、これはあまりよい指標ではないと考える。上記に挙げた規格化指数でも圧縮率でも、どちらも分母が違うだけであって相対的な比較の際には本質的な違いはないが、しかしどちらがより有用な知識を与えてくれるかという観点では異なる。まずは、以下の2つの印象を比べてほしい。
  
  
  • • 規格化指数

      osaskbmp		kdun00b	bim2binc	osaskgo	zero64k
      LZO	354.8	178.9	173.8	157.4	1563
      stk1	318.6	171.0	186.3	170.3	100.0
      stk2	293.7	160.5	177.1	156.6	107.4

      
      
    • 圧縮率

      osaskbmp		kdun00b	bim2binc	osaskgo	zero64k
      LZO	2.19%	7.96%	29.8%	59.7%	0.644%
      stk1	1.97%	7.61%	31.9%	64.6%	0.412%
      stk2	1.81%	7.14%	30.3%	59.4%	0.443%

      
      
• 圧縮率だけ見てしまうと、どうしても数値の大きいosaskgoのところを改善したいと思ってしまう。しかしここは規格化指数で分かるとおり、圧縮限界に対して1.6倍程度であり、むしろ改善の余地が大きいのはosaskbmpなのである。
• 圧縮率が小さい値になるということは、要するにもとのファイルが「すかすか」で本来持っている情報量に対して非常に巨大であったということでしかない。ここで規格化指数の無圧縮の部分を見ると、無圧縮のosaskgoは本来の情報量の2.6倍、無圧縮のosaskbmpは162倍ということが分かる。こういう差を考慮に入れずに、単に元のファイルに対する大きさだけで判断するのは、市場価値1万円のものがあって、A店はこれに100万円の値札をつけ、B店はこれに2万円の値札をつけているときに、A店で値引き交渉して10万円に負けさせて購入した場合（9割引）と、B店で値引き交渉して1万2千円にした場合（4割引）とで、A店での取引のほうが得だと判断するのと同じことである。・・・値札に惑わされてはならない（笑）。
• いくつかの種類のファイルを適当に混ぜて、この合計サイズによって比較をする人もあるが、これもいかがなものかと思う。実用上の参考になるようなブレンド比は人によって大きく異なるだろう（画像を多く持つ人もいるし、ログなどのテキストをたくさん持つ人もいる）。またたとえばosaskbmpとosaskgoとを足してしまえば、大幅に小さくなるosaskbmpの部分はosaskgoのサイズの前に埋没してしまい、その優劣は全く分からなくなるだろう。したがって勝手に混ぜることなく、それぞれを提示するのが好ましい方法だと考えている（kdun00bの例は統計的性質が大きく異なるデータが混在した一つのファイルをどれだけうまく圧縮できるかというところを見たいのであえて混ぜてある。それぞれを圧縮して合計するのとは意味が大きく異なることに注意）。

ダウンロード ^[21]

• （準備中）

課題 ^[22]

• マルチブロックサポートがまだできてない
• ECCレコード・リカバリーレコード（エラーチェック＆修復機能）のサポートがまだできてない
• フレーズモードのサポートができてない
  • これができると、たとえばtek1​/comp^[10]の「おまけ」にある minna.sar の圧縮率が9%くらいよくなる。tek5のbim2bincも136.5→132.8と3%ほど改善する。
• 差分モード（補助バッファ）のサポートができてない
  • これができると、たとえばこめんと欄の http://www.maximumcompression.com/data/bmp.php^[23] の圧縮率が、5%くらいよくなる。
• ファイル分割サポートがまだできてない
  • これはtekではなくsarでのサポートになる可能性もある。

• まともな圧縮ツールがない
  • bim2binはしょせんOSASKリンカであって、いつまでもそのおまけ機能でごまかすのは難がある。

こめんと欄 ^[24]

• http://compression.ca/act/^[25] 圧縮率、速度の比較で有名なサイト。比較のテストデータも入手可能。 -- 名無しさん^[26] 2004-10-17 (日) 10:07:22
• ↑過去にそこのサンプルを使おうと思いましたが、比較のテストデータがまともに入手できたためしがないです。たとえばtextのサンプルを例にとりますが、ページの説明ではサイズが[1344739, 586960, 2988578]のはずなんですが、僕がダウンロードして解凍すると[1344739, 586969, 3005020]になります。textに限らず他のファイルでも同じ傾向で、いつもなぜかちょっと違います。 -- K^[2] 2004-10-17 (日) 12:13:39
• http://www.maximumcompression.com/data/bmp.php^[23] こんな比較はどうでしょう？ -- 名無しさん^[26] 2004-10-26 (火) 09:24:00
• 題材はいいのですが、tekにはこのような写真系画像に向いた拡張が予定されており（差分値を使った圧縮：tek1​/adv2^[27]）、できればそれができてからやってみたいです。・・・でもまあとりあえず今やっても悪いことはないと思ったのでやってみました。tek5で967384バイトでした。 -- K^[2] 2004-10-26 (火) 12:46:30
• そのページのほかのものと比べるとこんな感じです。太字は僕がテストしたものです。 -- K^[2] 2004-10-26 (火) 14:54:02

  フォーマット	サイズ	指数
  BMF 2.0	669016	100.0
  PAQAR 4.0	688977	103.0
  7-ZIP 4.09b (PPMd)	764420	114.3
  WINRAR 3.40	789353	118.0
  bzip2	890161	133.1
  tek5	967384	144.6
  LZMA	978124	146.2
  DGCA 1.06	1004896	150.2
  CABARC 1.00.0106 (CAB LZX:21)	1036845	155.0
  WINZIP 9.0	1225734	183.2
  LHA32 1.88.3.14	1241336	185.5
  GZIP 1.2.4	1256638	187.8

  • tek5の拡張版（差分値を使った圧縮）では指数換算で138くらいになる見込み
• http://www.maximumcompression.com/^[28] 画像以外の題材（テキスト, EXE）もテストされていますよ。 -- 名無しさん^[26] 2004-10-26 (火) 19:11:33
• それはわかっていますが、そんなこといっていたらきりがありません。ここは圧縮比較サイトではなく、tekの紹介ページです。既にここに書いた内容だけで傾向はつかめると思います。徹底比較がしたい人は比較サイトを作ればいいでしょう。 -- K^[2] 2004-10-26 (火) 19:32:55
• 徹底比較がしたいのではなくて、テストの参考にこんなのありますよという情報提供のつもりでしたが。どこに書けば良いか分からなかったので、色々な形式との比較があったここに書きました。場違いと判断された場合はコメントごと削除して頂いて結構です。 -- 名無しさん^[26] 2004-10-26 (火) 20:34:08
• 前から疑問に思っていたのですが、tekって語源は何かの略でしょうか？どこかに説明があったような気がしないでもないですが、僕には見つけられませんでした。 -- ZwergSpitz 2004-12-16 (木) 13:21:29
• ご推察のとおりtekは何かの略ですが、それが何の略であるかは今のところ秘密になっています。 -- K^[2] 2004-12-16 (木) 16:39:05
• そうなんですか、なんだか少しだけ気になります（笑） -- ZwergSpitz 2004-12-16 (木) 18:02:40
• バリエーションのtek5の中にstk5ってのがあるんですけどtek5のことですよね？ -- 名無しさん^[26] 2005-03-13 (日) 16:48:45
• tek5はstk5を含みますが、それ以外の高度な形式も含んでいます。 -- K^[2] 2005-03-13 (日) 17:06:30
• それではLZMAより速いのはstk5to -- 名無しさん^[26] 2005-03-13 (日) 18:35:59
• ↑ごめんなさい打ち間違えました。LZMAより速いのはstk5とtek5ということでいいのでしょうか？ -- 名無しさん^[26] 2005-03-13 (日) 18:38:08
• tek系とLZMAを速い順に並べるとこうなります。 stk1 tek1 stk2 tek2 stk5 LZMA tek5 -- K^[2] 2005-06-29 (水) 02:43:04
• このページは、OS-Wikiに置いておくにはちょっと大きすぎるので、近いうちに整理します。このページをトップページ的扱いにして、コンテンツをOSASK-Wikiに移動させます。原則として削除はしません。 -- K^[2] 2005-06-29 (水) 03:21:33

こめんと欄 ^[29]

• LZMA SDK が Ver4.62 以降でパブリックドメイン扱いになっているそうなので、tek5 圧縮ソフトは脱GPLができる？ -- 名無しさん 2012-01-27 (金) 23:56:51