Point fixe sur un algorithme de compression largement utilisé de nos jours

Question

Je me demandais s'il existait un algorithme de compression, couramment utilisé aujourd'hui, qui contient un point fixe, c'est-à-dire un fichier d'identité. Pour expliquer, appelons C : byte[] -> byte[] une fonction qui représente l'algorithme de compression. Je veux savoir s'il existe (et ce qu'elle est, s'il est possible de déterminer dans un délai raisonnable) un fichier f tel que

C(f) = f

C'est un fichier qui, lorsqu'il est comprimé par un récipient approprié, algorithme de compression largement répandu dans l'utilisation courante de nos jours, se produira comme le résultat.

Connaissez-vous un tel phénomène?

Answer 1

Oui! Ceci est une variante du problème quine.

1. Un exemple qui utilise gzip: http://groups.google.com/group/comp.compression/browse_thread/thread/c57c322e15c782aa/350d9fb166fdf11f

2. Un exemple qui utilise zip/unzip: http://www.steike.com/code/useless/zip-file-quine/

Answer 2

Avertissement: réponse plutôt pédant.

Il existe de nombreux cas où D (f) = f (D étant défini comme décompression). Cependant, la compression n'est pas définie avec autant de précision. Pour la plupart des algorithmes de compression, différentes implémentations de l'algorithme de compression donneront différents fichiers de sortie (de tailles variables). Considérons deux programmes, 1 et 2. Pour une interopérabilité totale, il faut que D1 (F) soit égal à D2 (F) pour tout F. valide. De même, il faut que D2 (C2 (f)) == D2 (C1 (F)) == D1 (C1 (F)) == D1 (C2 (F)), pour tout F. valide Cependant, il est totalement inutile que C1 (F) == C2 (F), et c'est rarement l'affaire. Il est donc peu probable que, si vous compressez réellement de telles quines, vous finissiez avec le même fichier, à moins que vous n'utilisiez le même programme pour le générer (ce qui est peu probable, car de telles quines sont habituellement fabriqué à la main, avec C (F) jamais même testé).

Bien qu'il soit possible (en fait, trivial!) De produire un programme pour lequel C (F) == F pour certains F, la plupart des gens tendent à indiquer comme quines le cas le plus bien défini où D (F) == F (puisque D1 (F) == D2 (F) pour toute décompression valide et compatible du format de F, en supposant que F est valide). Donc, il y a des cas possibles où C (F) == F, mais généralement c'est la mauvaise question à poser, et vous devriez plutôt demander des cas où D (F) == F ... quelles autres personnes qui a répondu à la question ont fourni.