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

Question

Je me demandais s'il y a un algorithme de compression, d'usage courant aujourd'hui, qui contient un point fixe, à savoir un fichier d'identité.

Pour expliquer, nous allons appeler 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 f de fichier tel que

C(f) = f

C'est un fichier qui, lorsqu'il est comprimé par un algorithme de compression approprié, largement connu dans l'usage commun de nos jours, va se produire à la suite.

Connaissez-vous un tel phénomène?

Answer 1

Oui! Ceci est une variante sur le problème Quine .

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

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

Answer 2

Attention:. Réponse plutôt pédant

Il y a beaucoup de cas où D (f) = f (D étant définie comme la décompression). Cependant, la compression est pas définie avec précision. Pour la plupart des algorithmes de compression, différentes implémentations de l'algorithme de compression donneront des fichiers de sortie (de différentes tailles). Considérons deux programmes, 1 et 2. Pour une interopérabilité, il est nécessaire que D1 (F) doit être égale à D2 (F) pour tout F. valide De même, il est nécessaire que D2 (C2 (f)) == D2 (C1 ( F)) == D1 (C1 (F)) == D1 (C2 (F)), pour tous valides F. Cependant, il est totalement inutile que C1 (F) == C2 (F), ce qui est rarement en fait le cas.

Alors, il est peu probable, si vous compressez ces Quines, de se retrouver avec le même fichier, sauf si vous utilisez le même programme pour le faire qui a été utilisé pour générer (ce qui est peu probable, étant donné que ces quines sont généralement fabriqué à la main, avec C (F) jamais testé).

Bien qu'il soit possible (en effet, trivial!) Pour produire un programme pour lequel C (F) == F pour certains F, la plupart des gens ont tendance à pointer au lieu comme Quines le cas plus bien défini où D (F) == F (depuis D1 (F) == D2 (F) pour tout décompression valide, compatible au format de F, en supposant que F est valide).

Alors, il y a des cas probables où C (F) == F, mais en général c'est la mauvaise question à poser, et vous devriez plutôt demander des cas où D (F) == F ... que d'autres personnes qui répondu à la question ont fourni.