5: 2004-12-02 (木) 15:49:46  |
6: 2005-06-30 (木) 17:21:51 |
| | ~ | | ~ |
| | - [[dev-j:t5exe]] 大したものじゃないから追加するのも引けたけど。Unix風味環境(ELFとかPEとか関係ないのでcygwinでも動くのかな?)で実行ファイルを圧縮できます。 | | - [[dev-j:t5exe]] 大したものじゃないから追加するのも引けたけど。Unix風味環境(ELFとかPEとか関係ないのでcygwinでも動くのかな?)で実行ファイルを圧縮できます。 |
| | + | |
| | + | *** OS-Wikiのtekのページの旧内容 |
| | + | -一時退避的にここにおきます。 |
| | + | ---- |
| | + | *** tekフォーマット誕生のいきさつと目的など |
| | + | -もともと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が掛かった状態で扱われている）。 参考→[[OSASK:why_sar]] |
| | + | --非常に著名な圧縮形式では、圧縮を明示的に解かなくても内容を自由に閲覧できるツールが開発されているが、tekはそういう利用を最初から前提にして、この分野でのデファクトスタンダードなフォーマットになるのを目指している。圧縮しても拡張子を変えないでよい（＝それくらい冗長なシグネチャがある）というのもそのためである。OSASKのようにOSレベルでの自動展開サポートが普及するか、それが無理なOSでは各アプリがファイルオープンの際に先頭16バイトをチェックし、tekであれば展開した後に扱う機能が普及してほしいと思っている。 |
| | + | --この流れにより、現在のように多種多様な形式が乱立するのではなく、シンプルなフォーマットを（必要に応じて）共通の汎用アルゴリズムで圧縮する、という流れになればと思う。もちろんtek圧縮は完璧ではないし、対象によってはより圧縮率の高いものやより高速に展開できるものもあるだろうが、現状ではtekに劣るものがまだたくさんあるというのも事実である。tekに劣る形式が徐々にフェードアウトしてtekに一本化されれば、展開ルーチンの最適化はさらに進むであろうし、もしかしたらJPEGやMPEGのようにデコード支援用のハードウェアが開発されるかもしれない（tekの展開アルゴリズムはワークエリアが少なくて済むので、ハードウェア化もしやすいかもしれない）。 |
| | + | --なお今のところ圧縮時間に関してはほとんど配慮していない。それは目的とは直接関係ないからである。したがって、圧縮時間も重要になるような用途には多分向かない。まあしかし、圧縮率を犠牲にしてもいいのなら、いくらでも圧縮時間は短縮できるであろう。 |
| | + | --そして圧縮の世界もtekを超える基準での競争に限定されることで、より発展していくだろう。 |
| | + | |
| | + | *** バリエーション |
| | + | -開発済みの形式 |
| | + | --tek0：tek系初代の形式 |
| | + | ---展開アルゴリズムの単純さ、展開速度、圧縮率、の3つのどれにおいてもいまいちぱっとしない。補助バッファ利用圧縮やマルチブロック拡張機能などもない。 |
| | + | --tek1：展開速度・展開アルゴリズムの単純さをもっとも追求した形式 |
| | + | ---圧縮率はかなり低い。 |
| | + | ---stk1仕様なら展開ルーチンは270バイトで書ける。 |
| | + | ---フルセット仕様の中には未だ開発検討中で確定していない部分もある。 |
| | + | --tek2：tek1の展開速度を2～5割ほど犠牲にして圧縮率を改善した形式 |
| | + | ---stk2仕様なら展開ルーチンは531バイトで書ける。 |
| | + | --tek5：圧縮率をもっとも追求した形式 |
| | + | ---その圧縮率はほとんどのケースでgzipやbzip2を超える。展開速度の点でもこれらに対して引けを取らない。LZMAをアルゴリズムの基礎においているが、改良を加えているためLZMAよりも高速・高圧縮率になる傾向が強い（LZMAより高速なのはstk5のみ）。 |
| | + | ---stk5仕様なら展開ルーチンは1426バイトで書ける。 |
| | + | |
| | + | *** ベンチマーク |
| | + | -tekのそれぞれについての簡単なベンチマークです |
| | + | |
| | + | |zero64k|0x00が65536個並んだだけのファイル。人間の目にはこれはすごく圧縮できそうな感じがする。| |
| | + | |bim2binc|日本語を含むCのソースファイル。| |
| | + | |osaskbmp|16色ビットマップファイル。| |
| | + | |osaskgo|実行ファイル。| |
| | + | |kdun00b|RPGゲームに必要な複数のファイルを収めたディスクイメージ。実行ファイルやデータなどが混在している。| |
| | + | ~ |
| | + | |tek0|上記参照| |
| | + | |stk1|tek1のサブセット版| |
| | + | |stk2|tek2のサブセット版| |
| | + | |stk5|tek5のサブセット版| |
| | + | |tek5|上記参照| |
| | + | |lh7|LHAのlh7形式| |
| | + | |gzip|有名な形式| |
| | + | |bzip2|有名な形式| |
| | + | |LZMA|7-zipの中の形式の一つ かなり良い| |
| | + | |PPMd|7-zipのPPMdの192MBオプション| |
| | + | |LZO|展開速度に特化した形式| |
| | + | |dgc|DGCA 1.06| |
| | + | |paqar|[[paqar 1.3:http://cs.fit.edu/~mmahoney/compression/]]のオプション-5| |
| | + | ---paqarは展開時間がきわめて長く、さらに膨大なワークスペースを要求するために、上記の形式と同列で比較するべきではないと思うが、それぞれのデータがどこまで圧縮できるかを示す指標として導入した。まだ圧縮の余地があるのに圧縮できていない場合を発見するのに役立つ。 |
| | + | ~ |
| | + | -サイズ |
| | + | ||osaskbmp|kdun00b|bim2binc|osaskgo|zero64k| |
| | + | |無圧縮|RIGHT:393334|RIGHT:655360|RIGHT:53792|RIGHT:1973741|RIGHT:65536| |
| | + | |LZO |RIGHT: 8618|RIGHT: 52148|RIGHT:16015|RIGHT:1177820|RIGHT: 422| |
| | + | |stk1 |RIGHT: 7740|RIGHT: 49855|RIGHT:17166|RIGHT:1274931|RIGHT: 27| |
| | + | |stk2 |RIGHT: 7135|RIGHT: 46794|RIGHT:16323|RIGHT:1172344|RIGHT: 29| |
| | + | |lh7 |RIGHT: 6467|RIGHT: 45520|RIGHT:14181|RIGHT:1099064|RIGHT: 117| |
| | + | |tek0 |RIGHT: 6389|RIGHT: 46246|RIGHT:15019|RIGHT:1149662|RIGHT: 28| |
| | + | |gzip |RIGHT: 5687|RIGHT: 42553|RIGHT:13467|RIGHT:1087874|RIGHT: 108| |
| | + | |PPMd |RIGHT: 5609|RIGHT: 39546|RIGHT:11099|RIGHT: 966659|RIGHT: 151| |
| | + | |dgc |RIGHT: 5072|RIGHT: 43216|RIGHT:12624|RIGHT: 986880|RIGHT: 528| |
| | + | |bzip2 |RIGHT: 4906|RIGHT: 47306|RIGHT:12903|RIGHT:1047411|RIGHT: 43| |
| | + | |LZMA |RIGHT: 4236|RIGHT: 34037|RIGHT:12708|RIGHT: 942369|RIGHT: 90| |
| | + | |stk5 |RIGHT: 3860|RIGHT: 33549|RIGHT:12712|RIGHT: 942375|RIGHT: 29| |
| | + | |tek5 |RIGHT: 3669|RIGHT: 32909|RIGHT:12579|RIGHT: 936928|RIGHT: 29| |
| | + | |paqar |RIGHT: 2429|RIGHT: 29157|RIGHT: 9215|RIGHT: 748512|RIGHT: 43| |
| | + | |
| | + | -規格化指数（上記でそれぞれの一位が100になるように規格化しただけのもの） |
| | + | ||osaskbmp|kdun00b|bim2binc|osaskgo|zero64k| |
| | + | |無圧縮|RIGHT:16193|RIGHT: 2248|RIGHT:583.7|RIGHT:263.7|RIGHT:242726| |
| | + | |LZO |RIGHT:354.8|RIGHT:178.9|RIGHT:173.8|RIGHT:157.4|RIGHT: 1563| |
| | + | |stk1 |RIGHT:318.6|RIGHT:171.0|RIGHT:186.3|RIGHT:170.3|RIGHT:100.0| |
| | + | |stk2 |RIGHT:293.7|RIGHT:160.5|RIGHT:177.1|RIGHT:156.6|RIGHT:107.4| |
| | + | |lh7 |RIGHT:266.2|RIGHT:156.1|RIGHT:153.9|RIGHT:146.8|RIGHT:433.3| |
| | + | |tek0 |RIGHT:263.0|RIGHT:158.6|RIGHT:163.0|RIGHT:153.6|RIGHT:103.7| |
| | + | |gzip |RIGHT:234.1|RIGHT:145.9|RIGHT:146.1|RIGHT:145.3|RIGHT:400.0| |
| | + | |PPMd |RIGHT:230.9|RIGHT:135.6|RIGHT:120.4|RIGHT:129.1|RIGHT:559.3| |
| | + | |dgc |RIGHT:208.8|RIGHT:148.2|RIGHT:137.0|RIGHT:131.8|RIGHT: 1956| |
| | + | |bzip2 |RIGHT:202.0|RIGHT:162.2|RIGHT:140.0|RIGHT:139.9|RIGHT:159.3| |
| | + | |LZMA |RIGHT:174.4|RIGHT:116.7|RIGHT:137.9|RIGHT:125.9|RIGHT:333.3| |
| | + | |stk5 |RIGHT:158.9|RIGHT:115.1|RIGHT:137.9|RIGHT:125.9|RIGHT:107.4| |
| | + | |tek5 |RIGHT:151.0|RIGHT:112.9|RIGHT:136.5|RIGHT:125.2|RIGHT:107.4| |
| | + | |paqar |RIGHT:100.0|RIGHT:100.0|RIGHT:100.0|RIGHT:100.0|RIGHT:159.3| |
| | + | |
| | + | --tek5については、[[OSASK:why_sar]]にも圧縮率比較データがあります。 |
| | + | --さらにテスト：[[tek/dump]] |
| | + | |
| | + | -展開速度 |
| | + | --（準備中） |
| | + | |
| | + | *** 解説 |
| | + | -圧縮率比較方法に関する[[K]]の主張。 |
| | + | |
| | + | -一般的には圧縮の比較といえば圧縮率の比較をすると思うが、これはあまりよい指標ではないと考える。上記に挙げた規格化指数でも圧縮率でも、どちらも分母が違うだけであって相対的な比較の際には本質的な違いはないが、しかしどちらがより有用な知識を与えてくれるかという観点では異なる。まずは、以下の2つの印象を比べてほしい。 |
| | + | ~ |
| | + | ---規格化指数 |
| | + | ||osaskbmp|kdun00b|bim2binc|osaskgo|zero64k| |
| | + | |LZO |RIGHT:354.8|RIGHT:178.9|RIGHT:173.8|RIGHT:157.4|RIGHT: 1563| |
| | + | |stk1 |RIGHT:318.6|RIGHT:171.0|RIGHT:186.3|RIGHT:170.3|RIGHT:100.0| |
| | + | |stk2 |RIGHT:293.7|RIGHT:160.5|RIGHT:177.1|RIGHT:156.6|RIGHT:107.4| |
| | + | ~ |
| | + | ---圧縮率 |
| | + | ||osaskbmp|kdun00b|bim2binc|osaskgo|zero64k| |
| | + | |LZO |RIGHT:2.19%|RIGHT:7.96%|RIGHT:29.8%|RIGHT:59.7%|RIGHT:0.644%| |
| | + | |stk1 |RIGHT:1.97%|RIGHT:7.61%|RIGHT:31.9%|RIGHT:64.6%|RIGHT:0.412%| |
| | + | |stk2 |RIGHT:1.81%|RIGHT:7.14%|RIGHT:30.3%|RIGHT:59.4%|RIGHT: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の例は統計的性質が大きく異なるデータが混在した一つのファイルをどれだけうまく圧縮できるかというところを見たいのであえて混ぜてある。それぞれを圧縮して合計するのとは意味が大きく異なることに注意）。 |
| | + | |
| | + | *** ダウンロード |
| | + | -（準備中） |
| | + | |
| | + | |
| | + | *** 課題 |
| | + | -マルチブロックサポートがまだできてない |
| | + | -ECCレコード・リカバリーレコード（エラーチェック＆修復機能）のサポートがまだできてない |
| | + | -フレーズモードのサポートができてない |
| | + | --これができると、たとえば[[OSASK:tek1/comp]]の「おまけ」にある minna.sar の圧縮率が9%くらいよくなる。tek5のbim2bincも136.5→132.8と3%ほど改善する。 |
| | + | -差分モード（補助バッファ）のサポートができてない |
| | + | --これができると、たとえばこめんと欄の http://www.maximumcompression.com/data/bmp.php の圧縮率が、5%くらいよくなる。 |
| | + | -ファイル分割サポートがまだできてない |
| | + | --これはtekではなくsarでのサポートになる可能性もある。 |
| | + | |
| | + | -まともな圧縮ツールがない |
| | + | --bim2binはしょせんOSASKリンカであって、いつまでもそのおまけ機能でごまかすのは難がある。 |
| | + | |
| | + | * こめんと欄 |
| | + | -http://compression.ca/act/ 圧縮率、速度の比較で有名なサイト。比較のテストデータも入手可能。 -- [[名無しさん]] SIZE(10){2004-10-17 (日) 10:07:22} |
| | + | -↑過去にそこのサンプルを使おうと思いましたが、比較のテストデータがまともに入手できたためしがないです。たとえばtextのサンプルを例にとりますが、ページの説明ではサイズが[1344739, 586960, 2988578]のはずなんですが、僕がダウンロードして解凍すると[1344739, 586969, 3005020]になります。textに限らず他のファイルでも同じ傾向で、いつもなぜかちょっと違います。 -- [[K]] SIZE(10){2004-10-17 (日) 12:13:39} |
| | + | -http://www.maximumcompression.com/data/bmp.php こんな比較はどうでしょう？ -- [[名無しさん]] SIZE(10){2004-10-26 (火) 09:24:00} |
| | + | -題材はいいのですが、tekにはこのような写真系画像に向いた拡張が予定されており（差分値を使った圧縮：[[OSASK:tek1/adv2]]）、できればそれができてからやってみたいです。・・・でもまあとりあえず今やっても悪いことはないと思ったのでやってみました。tek5で967384バイトでした。 -- [[K]] SIZE(10){2004-10-26 (火) 12:46:30} |
| | + | -そのページのほかのものと比べるとこんな感じです。太字は僕がテストしたものです。 -- [[K]] SIZE(10){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/ 画像以外の題材（テキスト, EXE）もテストされていますよ。 -- [[名無しさん]] SIZE(10){2004-10-26 (火) 19:11:33} |
| | + | -それはわかっていますが、そんなこといっていたらきりがありません。ここは圧縮比較サイトではなく、tekの紹介ページです。既にここに書いた内容だけで傾向はつかめると思います。徹底比較がしたい人は比較サイトを作ればいいでしょう。 -- [[K]] SIZE(10){2004-10-26 (火) 19:32:55} |
| | + | -徹底比較がしたいのではなくて、テストの参考にこんなのありますよという情報提供のつもりでしたが。どこに書けば良いか分からなかったので、色々な形式との比較があったここに書きました。場違いと判断された場合はコメントごと削除して頂いて結構です。 -- [[名無しさん]] SIZE(10){2004-10-26 (火) 20:34:08} |
| | + | // 場違いだと思いますが、削除するのが嫌いなのであえて残しています。 -- K |
| | + | -前から疑問に思っていたのですが、tekって語源は何かの略でしょうか？どこかに説明があったような気がしないでもないですが、僕には見つけられませんでした。 -- ''ZwergSpitz'' SIZE(10){2004-12-16 (木) 13:21:29} |
| | + | -ご推察のとおりtekは何かの略ですが、それが何の略であるかは今のところ秘密になっています。 -- [[K]] SIZE(10){2004-12-16 (木) 16:39:05} |
| | + | -そうなんですか、なんだか少しだけ気になります（笑） -- ''ZwergSpitz'' SIZE(10){2004-12-16 (木) 18:02:40} |
| | + | -バリエーションのtek5の中にstk5ってのがあるんですけどtek5のことですよね？ -- [[名無しさん]] SIZE(10){2005-03-13 (日) 16:48:45} |
| | + | -tek5はstk5を含みますが、それ以外の高度な形式も含んでいます。 -- [[K]] SIZE(10){2005-03-13 (日) 17:06:30} |
| | + | -それではLZMAより速いのはstk5to -- [[名無しさん]] SIZE(10){2005-03-13 (日) 18:35:59} |
| | + | -↑ごめんなさい打ち間違えました。LZMAより速いのはstk5とtek5ということでいいのでしょうか？ -- [[名無しさん]] SIZE(10){2005-03-13 (日) 18:38:08} |
| | + | -tek系とLZMAを速い順に並べるとこうなります。 stk1 tek1 stk2 tek2 stk5 LZMA tek5 -- [[K]] SIZE(10){2005-06-29 (水) 02:43:04} |
| | + | -このページは、OS-Wikiに置いておくにはちょっと大きすぎるので、近いうちに整理します。このページをトップページ的扱いにして、コンテンツをOSASK-Wikiに移動させます。原則として削除はしません。 -- [[K]] SIZE(10){2005-06-29 (水) 03:21:33} |
| | + | |
| | + | ---- |
| | * こめんと欄 | | * こめんと欄 |
| | #comment | | #comment |
