2009-08-20 7 views
6

Mi chiedevo se esiste un algoritmo di compressione, in uso comune oggi, che contiene un punto fisso, vale a dire, un file di identità.Punto fisso su un algoritmo di compressione ampiamente usato al giorno d'oggi

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?

risposta

4
+0

Cool! A proposito, hai una copia dell'articolo dal secondo link? Il ragazzo ha detto che l'ha perso ... mi piacerebbe davvero leggerlo! Grazie per la risposta! –

+0

@Bruno Reis: Siamo spiacenti, ho paura di no. –

+0

Neat. È interessante notare che sebbene la decompressione del primo risultato si produca da sé, la sua compressione no. La risposta di Brian lo spiega, ovviamente. –

3

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.

+0

Brian, hai assolutamente ragione! Avrei dovuto fare la domanda opposta. Grazie per la tua risposta! –