FC2ブログ

データ圧縮について、思うところ

まずは基本。可逆圧縮において全てのファイルのサイズを縮小する方法はない。
 f:N->Nを圧縮関数、log:N(>0)->N(>0)をサイズを計算する関数
 for all n log(n)>log(f(n))であるならば
 log(n),log(f(n)),log(f(f(n))),...は無限降下列となる。
 これはlogの定義に反する。

さらに、可逆圧縮においてファイルのサイズが減少しないファイルは無限個ある。
証明はこちら 

んでさ、そうするとある程度のラインで圧縮をあきらめる必要がある。
例えばテキストファイルを圧縮するなら
 バイナリファイルのサイズは圧縮できないことにして、
 そいつらが占めてた場所に順序よくテキストファイルを当てれば
 それで圧縮にはなるわけだ。

Zipなどの汎用の圧縮フォーマットでは
大雑把に言えば、そのファイルに現れる記号に
 別の記号を当てはめた上で
 近くに同じ記号列があればその記号列を書くよりは短い新たな記号で
 代用する、といった感じで圧縮をする。

これは人間が使用する記号に偏りがあることであったり、
画像などにおけるある点とその周辺の点は色が似ていたり、
また文章のなかで同じ単語をなんども使用したりすることを
うまく表していると言える。

ようは無茶を承知で言えば
圧縮とは自然を人工に落とし込む作業で
圧縮されたファイルがどれだけ「反自然」であるかが圧縮率。

「反自然」って何かな。一様な乱数とか?
違う、ランダム性だ。ランダム性と圧縮かぁ。
効率的なものではなくて理論的なものとしては
面白い研究対象かもしれないねぇ。
関連記事

コメントの投稿

非公開コメント

a8
最近の記事
月別アーカイブ
ブログ内検索
グリムス
フリーエリア
リンク
RSSフィード