6

今日一般的に使用されている、固定小数点、つまり ID ファイルを含む圧縮アルゴリズムがあるかどうか疑問に思っていました。

C : byte[] -> byte[]説明するために、圧縮アルゴリズムを表す関数を呼び出してみましょう。f次のようなファイルが存在するかどうか (妥当な時間内に特定できる場合は、それが何であるか) を知りたいです。

C(f) = f

つまり、現在一般的に使用されている適切で広く知られている圧縮アルゴリズムによって圧縮されると、結果としてそれ自体が生成されるファイルです。

このような現象をご存知ですか？

4

2 に答える 2

4

はい！これはクワイン問題の変種です。

  1. gzipを使用する例: http://groups.google.com/group/comp.compression/browse_thread/thread/c57c322e15c782aa/350d9fb166fdf11f

  2. zip/unzipを使用する例: http://www.steike.com/code/useless/zip-file-quine/

于 2009-08-20T13:24:49.863 に答える
3

警告: やや衒学的な回答です。

Ｄ（ｆ）＝ｆ（Ｄは減圧と定義）の場合が多い。ただし、圧縮はそれほど正確に定義されていません。ほとんどの圧縮アルゴリズムでは、圧縮アルゴリズムの実装が異なると、(サイズが異なる) 異なる出力ファイルが生成されます。2 つのプログラム 1 と 2 を考えてみましょう。完全な相互運用性のためには、すべての有効な F に対して D1(F) が D2(F) と等しくなければなりません。同様に、D2(C2(f)) == D2(C1( F)) == D1(C1(F)) == D1(C2(F))、すべての有効な F. ただし、C1(F) == C2(F) はまったく不要であり、これは実際にはめったにありません。ケース。

そのため、そのようなクインを実際に圧縮したとしても、それを生成するために使用されたのと同じプログラムを使用しない限り、同じファイルになる可能性はほとんどありません (そのようなクインは通常手作りであるため、そうはなりません)。 、C(F) がテストされることさえありません)。

いくつかの F に対して C(F) == F となるプログラムを作成することは可能ですが (実際、些細なことです!)、ほとんどの人は代わりに、D(F) == F であるより明確に定義されたケースを quines として指摘する傾向があります。 (F が有効であると仮定すると、F のフォーマットのすべての有効で互換性のある解凍に対して D1(F)==D2(F) であるため)。

したがって、C(F) == F である可能性がありますが、一般的にこれは間違った質問であり、代わりに D(F) == F である場合を尋ねる必要があります...どの他の人がその質問に答えましたか?提供しています。

于 2009-08-20T13:47:49.197 に答える