Fixpunkt auf einem heutzutage weit verbreiteten Komprimierungsalgorithmus

Question

Ich frage mich, ob es einen Kompressionsalgorithmus gibt, der heute allgemein verwendet wird, der einen festen Punkt enthält, d. H. Eine Identitätsdatei.

Um zu erklären, rufen wir C : byte[] -> byte[] eine Funktion, die den Komprimierungsalgorithmus darstellt. Ich möchte wissen, wenn es eine Datei f so dass

C(f) = f

Das (und was es ist, wenn es möglich ist, in angemessener Zeit zu bestimmen) ist, eine Datei, die, wenn sie durch einen geeigneten Druck, weithin bekannte Kompressionsalgorithmen, die heutzutage allgemein verwendet werden, werden sich selbst als Ergebnis produzieren.

Kennen Sie ein solches Phänomen?

Answer 1

Ja! Dies ist eine Variante des Problems quine.

1. Ein Beispiel, das gzip verwendet: http://groups.google.com/group/comp.compression/browse_thread/thread/c57c322e15c782aa/350d9fb166fdf11f

2. Ein Beispiel, das zip/unzip verwendet: http://www.steike.com/code/useless/zip-file-quine/

Answer 2

Warnung: Eher pedantisch Antwort.

Es gibt viele Fälle, in denen D (f) = f ist (D ist als Dekompression definiert). Die Komprimierung ist jedoch nicht so genau definiert. Für die meisten Komprimierungsalgorithmen ergeben verschiedene Implementierungen des Komprimierungsalgorithmus unterschiedliche Ausgabedateien (mit unterschiedlichen Größen). Betrachten Sie zwei Programme, 1 und 2. Für volle Interoperabilität ist es notwendig, dass D1 (F) für alle gültigen F gleich D2 (F) sein muss. Ebenso ist es notwendig, dass D2 (C2 (f)) == D2 (C1 (F)) == D1 (C1 (F)) == D1 (C2 (F)), für alle gültigen F. Es ist jedoch völlig unnötig, dass C1 (F) == C2 (F), und das ist tatsächlich selten der Fall.

Also, Sie sind unwahrscheinlich, wenn Sie solche Quines tatsächlich komprimieren, um mit der gleichen Datei zu enden, es sei denn, Sie verwenden das gleiche Programm, um es zu generieren (was unwahrscheinlich ist, da solche Quines sind) meist handgefertigt, wobei C (F) nie getestet wird.

Während es möglich ist (tatsächlich, trivial!), Ein Programm zu erzeugen, für das C (F) == F für einige F, neigen die meisten Leute dazu, stattdessen als den gut definierten Fall zu zeigen, wo D (F) == F (seit D1 (F) == D2 (F) für alle gültigen, kompatiblen Dekomprimierung des Formats von F, unter der Annahme, dass F gültig ist).

Also gibt es wahrscheinlich Fälle, in denen C (F) == F, aber im Allgemeinen ist dies die falsche Frage, und Sie sollten stattdessen Fälle fragen, wo D (F) == F ... welche anderen Leute Wer hat die Frage beantwortet?