Punto fisso su un algoritmo di compressione ampiamente usato al giorno d'oggi

Question

Mi chiedevo se esiste un algoritmo di compressione, in uso comune oggi, che contiene un punto fisso, vale a dire, un file di identità.

Per spiegare, chiamiamolo C : byte[] -> byte[] una funzione che rappresenta l'algoritmo di compressione. Voglio sapere se esiste (e che cosa è, se è possibile determinare in tempi ragionevoli) un file f tale che

C(f) = f

Che è, un file che, se compresso da un adeguato, Algoritmo di compressione ampiamente noto in uso oggigiorno, produrrà se stesso come risultato.

Sei a conoscenza di un tale fenomeno?

Answer 1

Sì! Questa è una variante del problema quine.

1. Un esempio che utilizza gzip: http://groups.google.com/group/comp.compression/browse_thread/thread/c57c322e15c782aa/350d9fb166fdf11f

2. Un esempio che utilizza zip/unzip: http://www.steike.com/code/useless/zip-file-quine/

Answer 2

Attenzione: risposta piuttosto pedante.

ci sono molti casi in cui D (f) = f (D essendo definito come decompressione). Tuttavia, la compressione non è definita con precisione. Per la maggior parte degli algoritmi di compressione, diverse implementazioni dell'algoritmo di compressione daranno file di output diversi (di dimensioni diverse). Consideriamo due programmi, 1 e 2. Per la piena interoperabilità, è necessario che D1 (F) debba essere uguale a D2 (F) per tutti i F. validi. Allo stesso modo, è necessario D2 (C2 (f)) == D2 (C1 (F)) == D1 (C1 (F)) == D1 (C2 (F)), per tutti i F. validi. Tuttavia è totalmente inutile che C1 (F) == C2 (F), e questo è di fatto raramente il caso.

Quindi, è improbabile che, se si comprimono effettivamente tali quine, per finire con lo stesso file, a meno che non si usi lo stesso programma per farlo è stato usato per generarlo (il che è improbabile, dal momento che tali quine sono di solito fatto a mano, con C (F) che non è mai stato testato).

Mentre è possibile (anzi, banale!) Produrre un programma per il quale C (F) == F per alcuni F, la maggior parte delle persone tende invece a indicare come quine il caso più definito in cui D (F) == F (poiché D1 (F) == D2 (F) per tutte le decompressioni valide e compatibili del formato di F, supponendo che F sia valido).

Quindi, ci sono probabilmente casi in cui C (F) == F, ma generalmente questa è la domanda sbagliata da porre, e dovresti invece chiedere casi in cui D (F) == F ... quali altre persone chi ha risposto alla domanda hanno fornito.