Wie gzip (oder andere verlustfreie Komprimierung) zu besiegen ist

Question

Durch Schublade Prinzip kann jeder verlustfreie Kompression Algorithmus "besiegt" werden, d. H. Für einige Eingänge erzeugt es Ausgänge, die länger als die Eingabe sind. Ist es möglich, explizit eine Datei zu konstruieren, die, wenn sie z. Gzip oder andere verlustfreie Komprimierungsprogramm, wird (viel) größere Ausgabe führen? (Oder, betters, noch eine Datei, die ad infinitum bei der nachfolgenden Kompressionen aufbläst?)

Answer 1

versuchen, die Datei auf gzip, die aus dem folgenden Befehl führt:

echo a > file.txt 

Die Kompression einer 2 Bytes-Datei einer Folge 31 Byte Datei gezippt!

Answer 2

Eine Textdatei mit 1 Byte (z. B. ein Zeichen wie 'A') wird in 1 Byte auf der Festplatte gespeichert, winrar rar es jedoch auf 94 Byte und Reißverschlüsse auf 141 Byte.

Ich weiß, es ist eine Art Cheat-Antwort, aber es funktioniert. Ich denke, es ist der größte Unterschied zwischen der Originalgröße und der "komprimierten" Größe, die Sie sehen werden.

Werfen Sie einen Blick auf die Formel für Zipping, sie sind relativ einfach, und um "komprimierte" Datei größer als das Original zu machen, ist die einfachste Möglichkeit, um sich wiederholende Daten zu vermeiden.

Answer 3

Zufällige Daten oder Daten, die mit einem guten cypher verschlüsselt sind, wären wahrscheinlich am besten.

Aber jeder gute Packer sollte nur konstanten Overhead hinzufügen, sobald er entscheidet, dass es die Daten nicht komprimieren kann. (@Frank). Für einen festen Overhead ergibt eine leere Datei oder ein einzelnes Zeichen den größten prozentualen Overhead.

Für Packer, der den Dateinamen (zB rar, zip, tar), man kann natürlich enthalten nur den Dateinamen machen wirklich lange :-)

Answer 4

Nun, ich werde es schließlich annehmen würde max out da die Bitmuster wiederholen, aber ich habe gerade:

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

Und bekam:

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 

Hier sind 24.380 Dateien grafisch (dies ist wirklich überraschend für mich, tatsächlich):

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

ich nicht diese Art von Wachstum erwartet wurde, würde ich die lineare Wachstum nur erwarten, da es sollte nur mit einem Wörterbuch, um die vorhandenen Daten in einem Header wird Einkapseln von Muster. Ich beabsichtigte, 1.000.000 Dateien zu durchsuchen, aber meinem System ging schon viel Speicherplatz aus.

Wenn Sie hier reproduzieren wollen, ist der Bash-Skript, um die Dateien zu erzeugen:

#!/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 

Das resultierende filesizes.txt ist eine Tab-separierte, sortierte Datei für Ihr Lieblingsgraphikprogramm. (Sie müssen das Feld "total" manuell entfernen oder es wegskriptieren.)

Answer 5

Alle diese Komprimierungsalgorithmen suchen nach redundanten Daten. Wenn die Datei keine oder sehr wenig Redundanz enthält (wie eine Sequenz von abac…az, bcbd…bz, cdce…cz usw.)) Es ist sehr wahrscheinlich, dass die "deflationierte" Produktion eher eine Inflation ist.