Comment vaincre gzip (ou toute autre compression sans perte)

Question

D'après le principe du pigeonhole, chaque algorithme de compression sans perte peut être "vaincu", c'est-à-dire que pour certaines entrées, il produit des sorties plus longues que l'entrée. Est-il possible de construire explicitement un fichier qui, lorsqu'il est alimenté par ex. gzip ou un autre programme de compression sans perte, conduira à (beaucoup) une plus grande sortie? (Ou, Betters encore, un fichier qui se gonfle ad infinitum sur les compressions suivantes?)

Answer 1

Essayez de compresser le fichier résultant de la commande suivante:

echo a > file.txt 

La compression d'un fichier 2 octets pour résultat d'un 31 octets fichier gzippé!

Answer 2

Un fichier texte contenant 1 octet (par exemple, un caractère comme 'A') est stocké dans 1 octet sur le disque mais winrar le râpe à 94 octets et zippe à 141 octets. Je sais que c'est une sorte de réponse de triche mais cela fonctionne. Je pense que ça va être le plus grand% de différence entre la taille d'origine et la taille "compressée" que vous allez voir. Jetez un oeil à la formule de zipping, ils sont raisonnablement simples, et pour rendre le fichier «compressé» plus grand que l'original, la manière la plus simple est d'éviter toute répétition de données.

Answer 3

Des données aléatoires, ou des données cryptées avec un bon cypher seraient probablement les meilleures.

Mais tout bon packer ne devrait ajouter un surcoût constant, une fois qu'il décide qu'il ne peut pas compresser les données. (@Franc). Pour un temps système fixe, un fichier vide ou un seul caractère donnera le plus grand pourcentage de frais généraux.

Pour emballeurs qui incluent le nom du fichier (par exemple, rar, zip, tar), vous pouvez bien sûr faire juste le nom du fichier vraiment à long :-)

Answer 4

Eh bien, je suppose finalement ça va emboiter étant donné que les motifs de bit répéter, mais je l'ai fait:

touch file 
gzip file -c > file.1 
... 
gzip file.9 -c > file.10 

et a obtenu:

0 bytes: file 
25 bytes: file.1 
45 bytes: file.2 
73 bytes: file.3 
103 bytes: file.4 
122 bytes: file.5 
152 bytes: file.6 
175 bytes: file.7 
205 bytes: file.8 
232 bytes: file.9 
262 bytes: file.10 

Voici les 24.380 fichiers graphiquement (ce qui est vraiment surprenant pour moi, en fait):

alt text http://research.engineering.wustl.edu/~schultzm/images/filesize.png

Je ne m'y attendais pas ce genre de croissance, je voudrais simplement attendre une croissance linéaire car il devrait juste être encapsulant les données existantes dans un en-tête avec un dictionnaire de modèles J'avais l'intention de parcourir 1 000 000 fichiers, mais mon système manquait d'espace disque avant cela.

Si vous souhaitez reproduire, voici le script bash pour générer les fichiers:

#!/bin/bash 

touch file.0 

for ((i=0; i < 20000; i++)); do 
    gzip file.$i -c > file.$(($i+1)) 
done 

wc -c file.* | awk '{print $2 "\t" $1}' | sed 's/file.//' | sort -n > filesizes.txt 

Le filesizes.txt résultant est délimité par des tabulations, fichier triés pour votre utilitaire favori graphique. (Vous devrez supprimer manuellement le champ "total" ou le supprimer.)

Answer 5

Tous ces algorithmes de compression recherchent des données redondantes. Si vous déposez n'a pas ou très moins de redondance dedans (comme une séquence de abac…az, bcbd…bz, cdce…cz, etc.) il est très probable que la production «dégonflée» soit plutôt une inflation.