klog/essay079

OSASK-WikiのKの落書きの過去ログ

• 本家：OSA:K
  • 過去ログにコメントしたい人も、本家のこめんと欄に突っ込んでください。
    • そのうちKによって下のこめんと欄に移動しますので。

圧縮能力の評価方法

• (2004.11.14-2004.11.22)
• 世間では、圧縮能力の比較方法として、無圧縮サイズに対する割合で示したものがほとんどですが、これがナンセンスだということはZ:tekの「解説」に既に書きました。それで僕は、それぞれの圧縮後のサイズを、もっとも小さくできた圧縮サイズで除した、圧縮指標を導入して分析を進めてきました。
• 先ほど、もっと役に立ちそうな指標を思いついたので、これを説明・検討してみたいと思います。

• 僕の提唱した圧縮指標は明らかに世間一般の表現方法よりも有用でしたが、それでも不満な点がありました。例としてZ:tekの表から一部を持って来たものを挙げます。

  	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

• これを見ると、確かにstk2ではosaskbmpを限界圧縮サイズの約3倍にまで小さくできているということは分かります。一方、osaskgoに関しては1.6倍程度だということも分かります。
• でも、これだけでは分からないこともあります。たとえばstk2はbmpが得意なのでしょうか、不得意なのでしょうか？そういうことを論じるには本来は他の圧縮形式ではどうなっているのかをみなければいけません。でも、そういう比較をしないでもある程度のことが分かったらいいのではないかと思いました。
• 293.7と156.6ということを単純に比較すれば、なんとなくosaskgoのほうが得意なのかと思ってしまうところですが、そもそもosaskgoは無圧縮でも263.7であって、そういう比較では不十分だと分かります。
• そこでこんな指標を考えました。

  指標B = ln((参考サイズ - 限界サイズ) / (圧縮サイズ - 限界サイズ))

• 考え方はこうです。まず、どれだけ小さくなったのかではなく、どれだけ無駄を削ったのか、ということを中心に考えることにしました。そこで参考サイズというものが出てきます。これは適当に決めていいのですが、まあ目安としては一番圧縮率の悪いものを選びます（無圧縮を選んでも構わないですが）。これを基準にして、その比そのものではなく自然対数をとることにしました。これは極端に大きな数や極端に小さな数が出るのを避けて、見通しをよくするためです。
  • 自然対数なので0.7の差は、比では約2倍の差になります。たとえばもし1.4の差があれば、無駄を1/4に削減できているということです。
• 早速この考えで、表を作ってみました。

  	osaskbmp	kdun00b	bim2binc	osaskgo	zero64k	min.
  無圧縮	-4.146	-3.305	-1.724	-0.845	-4.873
  stk1	0.153	0.105	0.000	0.000	[inf]	0.000
  LZO	0.000	0.000	0.156	0.204	0.238	0.000
  stk2	0.274	0.265	0.112	0.217	5.523	0.112
  bzip2	0.916	0.236	0.768	0.566	3.444	0.236
  tek0	0.447	0.297	0.315	0.272	6.217	0.272
  lh7	0.427	0.340	0.471	0.407	1.717	0.340
  gzip	0.642	0.540	0.626	0.439	1.822	0.439
  dgc	0.851	0.492	0.847	0.792	0.000	0.492
  PPMd	0.666	0.794	1.440	0.881	1.396	0.666
  stk5	1.464	1.656	0.821	0.999	5.523	0.821
  LZMA	1.231	1.550	0.823	0.999	2.073	0.823
  tek5	1.608	1.813	0.860	1.027	5.523	0.860
  paqar	[inf]	[inf]	[inf]	[inf]	3.444	[inf]

  • min.はzero64k以外の最小値。これをもとにソートしてある。
• これによるとtek5はbim2bincが苦手だということがよく分かります。逆にkdun00bが得意だということも分かります。今までの指標（指標A）だとosaskbmpのほうが改良の余地ありだったのですが、それよりもbim2bincのほうこそ改良の余地があるのでしょう（なお既に改善案はあって、それを使うと0.96くらいには改善しそうです）。
• OSA:why_sarページの表も指標Bで整理してみました。

  	sar+stk1	lzh	zip	yz2	tar.bz2	tar.gz	dgc	PPMd	rar	cab	LZMA	sar	paq
  osat45i	0.000	0.348	0.475	0.114	0.145	0.510	0.387	0.427	0.556	0.620	0.917	1.065	[inf]
  sartol0g	0.000	0.107	0.144	0.134	0.396	0.306	0.558	1.211	0.748	0.573	0.783	0.911	[inf]
  make46	0.441	0.000	0.097	0.801	0.700	0.162	1.211	1.729	1.070	1.047	1.304	1.352	[inf]
  min.	0.000	0.000	0.097	0.114	0.145	0.162	0.387	0.427	0.556	0.573	0.783	0.911	[inf]

  • ここにはstk1やLZOが入っていないので上記と比べると全体的にスコアが低めです。
    • それだとかえって比較しにくいと思ったので、stk1を追加しました。
    • sar+stk1のサイズ： osat45i:559696, sartol0g:48250, make46:342168
• おまけ：なぜベスト値でも平均値でもなく、ワースト値で評価するのか？
  • ベストを使わない理由は簡単です。特定の傾向に特化したアルゴリズムを作っていいのなら、圧縮率を高めるのはやさしくなるからです。極端なことをいえば、展開ツール側に巨大な辞書（というか無圧縮データ？）を持たせておき、アーカイブではその辞書番号だけを入れたような、ひどい圧縮ソフトだって作れます。これは特定の数種のファイルだけを数バイトに圧縮可能ですが、こんなものをベスト値として評価すれば、これは最高のスコアを出すでしょう。
    • 他には、オールゼロのファイルに対しては、ファイルサイズのみ記録し、中身は記録しない、とか。これだとオールゼロのファイルに対してはものすごい圧縮率になる。
  • 平均値を使わない理由はこうです。平均を取るとしたら、どういうテストデータで平均を取るべきなのかが問題になります（テストデータの選び方で順位が大きく変わる）。
  • これらに対し、ワースト値は簡単です。いろんなデータを食わせてみて、ベストを探すのは非常に難しいですし（たいていベスト値が出せるのはかなり傾向が限定されているので）、平均値だとテストデータを追加するたびに全部計算しなおしですが、適当に試していれば簡単にワースト値（厳密な最悪値ではないにしても、それに近いもの）は見つかります。テストデータを追加しても、順位に影響するほどワースト値が更新されるものはめったにありません。
• おまけ2：切り替え戦略について
  • 7-zipでは、LZMAとPPMdをセレクトして使えるようになっています（他の形式もいくつか選べます）。これは非常にかしこい戦略であるように見えます。というのは、PPMdが不得意なものではLZMAがよいスコアを出しているからです。
  • こういう手法を肯定的に考えると、ワーストをフォローして不得意分野を改善していくよりも、ベストを磨いて得意分野に特化するほうが、良さそうに思えてきます。というのは、もし得意分野があればこのような切り替え法の中の一つのメソッドとして生き残れますが、得意分野がなければ、たとえ全体的に安定していて不得意な部分がなくても、切り替え法の一部としては採用されないからです。
  • しかしそれは誤解です。得意分野を磨き始めると、どんどん得意分野は狭くなり、汎用的なデータをカバーできなくなります。そうなればなるほど、たくさんのメソッドを切り替える必要が出てくる上に、それらがどうしても取りこぼしてしまう分野の救済のために、結局はワースト底上げ型のようなものが必要になるのです。
  • また切り替え型には別の問題もあります。切り替え型は柔軟性にかけるので、アルゴリズム融合型には勝てません。たとえばあるデータがあって、前半はLZMA向き、後半はPPMd向きだったとしましょう（こういうデータはtarなどでファイルをアーカイブするとか、EXEにリソースファイルを組み込んだりすると容易に出現する）。これを切り替えアルゴリズムで圧縮すると、どちらのアルゴリズムを選ぶにしても、ぱっとしない圧縮率にしかなりません（半分はうまく圧縮できるが、残り半分がうまく圧縮できないため）。一方、LZMAのアルゴリズムにPPMd的な考えを導入したアルゴリズムを新規に作った場合、このアルゴリズムならそういう混在データに対しても、おそらく個別に得意なほうで圧縮したものの総和くらいには圧縮できるでしょう（もちろん、PPMdにLZMA的な考えを導入してもよい）。うまくいけば相乗効果で、さらによくなることだってありえます。