究極の圧縮？

どんなファイル長でも固定長に圧縮できる方法を発見したぞ｡
まず入力ファイルをzipなり何なりで圧縮し、そのファイルサイズ、CRCを出力する｡
解凍する場合、(ファイルサイズ)バイトの考えられる全ての組み合わせからCRCの一致するものを抽出
そしてその中からzipとして解凍可能な組み合わせを探す｡結構な精度で元ファイルが復元できると思うが、どうか｡
処理速度？解凍は死ぬほど遅いが圧縮が糞速いからプラマイゼロだろ(藁

979 ：デフォルトの名無しさん：02/08/06 00:32

>>978
解凍に一年ぐらいかかったりしないか？（藁

980 ：デフォルトの名無しさん：02/08/06 00:37

>>978
作ってみるわ。まっとれ

981 ：逝って良しの１：02/08/06 00:45

アフォか！
解凍可能な組み合わせが天文学的な数になるに決まってるだろ！

982 ：978：02/08/06 00:57

>>979
まあ並列演算の得意そうな量子コンピュータに期待｡

>>980
ｶｺｲｲ

>>981
そう言われればそうなんだが、うーむ｡
長さnの任意のビット列が正常なzipフォーマットになる確率は相当低いし……
とはいえ候補の数も膨大だからな……
まー複数でたら最終的にはファイル内容からユーザが判断するって事で

983 ：デフォルトの名無しさん：02/08/06 01:29

とりあえず、元データのチェックサム取っといて、
解凍後のデータのチェックサムと比較すれば、
解凍後の候補はかなり絞れるゾ、とか言ってみるﾃｽﾄ

984 ：デフォルトの名無しさん：02/08/06 01:48

てかこれ、ガロア体かなんか使ってうまく実装できねえか？
時間なんか気にしなければ、だけど

985 ：デフォルトの名無しさん：02/08/06 01:52

チェックサムが2バイトとして、候補が1/65536になるだけ、4バイトでも
　1/4294967296に出来るだけ。
それに対して、1KBytesのデータでも元データの候補は
2^(8*1024)だから、1.0907481356194159294629842447338e+2466
1MBytesだと、2^(8*1024*1024)で……、Windows付属の電卓では
計算できねぇよぉ。

候補の数を 1/4294967296 に絞っても焼け石に水。
この程度の事ではエントリピーの壁は超えられない。

計算ミスがあれば突っ込んでね。

986 ：デフォルトの名無しさん：02/08/06 02:57

http://www5e.biglobe.ne.jp/~trakoala/r3/R3_temp.swf?inputStr=%8B%86%8B%C9%82%CC%88%B3%8F%6B%81%49

↑ちょっと気に入った

987 ：978：02/08/06 04:26

>>985
(´Д｀)確かに……
冷静に計算したらそりゃそうだわな｡
でも、解凍候補が複数存在する(どれが本物かは判断不能)アルゴリズムなら
結構情報量削れる気がすんだよなあ｡

小ネタ
圧縮関数：
与えられたデータから1引く｡
例： 1011→1010
全ビット0の場合： 0000→111

解凍関数：与えられたデータに1足す｡つまり上の逆｡

こいつを使えば、n回目に圧縮したサイズ≧n+1回目に圧縮したサイズ、となる｡
どんなデータでも最終的に0ビットまで圧縮してくれるという優れもの｡藁
当然可逆｡こりゃ凄えや！

988 ：985：02/08/06 04:30

エントリピーって、なんだよ。エントロピーだろ。

欝だ、寝よう。

989 ：デフォルトの名無しさん：02/08/06 04:41

>>987
n はどうすんの？

990 ：デフォルトの名無しさん：02/08/06 04:45

0ビットになったら、複数存在する解凍候補は全てのファイルですか。
面白いね。

991 ：デフォルトの名無しさん：02/08/06 05:08

nが元ファイルと同サイズに

992 ：デフォルトの名無しさん：02/08/06 08:23

>>991
ﾜﾗﾀ

993 ：デフォルトの名無しさん：02/08/06 09:52

>>978
ファイルサイズ・ＣＲＣのほかに先頭・中間・末尾の数バイトを取得して記憶しておく。
これならさらに絞り込めるかも？