Punto fijo en un algoritmo de compresión ampliamente utilizado hoy en día

Question

Me preguntaba si existe un algoritmo de compresión, de uso común hoy en día, que contiene un punto fijo, es decir, un archivo de identidad.

Para explicar, llamemos al C : byte[] -> byte[] una función que representa el algoritmo de compresión. Quiero saber si existe (y lo que es, si es posible determinar en un tiempo razonable) un archivo f tal que

C(f) = f

Es decir, un archivo que, cuando se comprime mediante un adecuado, algoritmo de compresión ampliamente conocido en uso común hoy en día, se producirá a sí mismo como resultado.

¿Conoces este fenómeno?

Answer 1

Sí! Esta es una variante del problema quine.

1. un ejemplo que utiliza gzip: http://groups.google.com/group/comp.compression/browse_thread/thread/c57c322e15c782aa/350d9fb166fdf11f

2. un ejemplo que utiliza zip/unzip: http://www.steike.com/code/useless/zip-file-quine/

Answer 2

Advertencia: respuesta bastante pedante.

Hay muchos casos en los que D (f) = f (D se define como descompresión). Sin embargo, la compresión no se define con tanta precisión. Para la mayoría de los algoritmos de compresión, diferentes implementaciones del algoritmo de compresión proporcionarán diferentes archivos de salida (de diferentes tamaños). Considere dos programas, 1 y 2. Para una interoperabilidad completa, es necesario que D1 (F) sea igual a D2 (F) para todos los F. válidos. De manera similar, es necesario que D2 (C2 (f)) == D2 (C1 (F)) == D1 (C1 (F)) == D1 (C2 (F)), para todas las F. válidas. Sin embargo, es totalmente innecesario que C1 (F) == C2 (F), y esto de hecho es raramente el caso.

Por lo tanto, es poco probable que, si realmente comprime tales quines, termine con el mismo archivo, a menos que use el mismo programa para generarlo (lo que es poco probable, ya que tales quines son usualmente hecho a mano, con C (F) que nunca se está probando).

Si bien es posible (¡de hecho, trivial!) Producir un programa para el cual C (F) == F para algunos F, la mayoría de la gente tiende a señalar como quines el caso más bien definido donde D (F) == F (desde D1 (F) == D2 (F) para todas las descompresiones válidas y compatibles del formato de F, suponiendo que F es válido).

Por lo tanto, hay casos en los que C (F) == F, pero generalmente esta es la pregunta incorrecta, y en su lugar debería pedir casos donde D (F) == F ... qué otras personas quien ha respondido la pregunta ha proporcionado.