Können Teerdateien die Komprimierung verbessern?

9

Kann das gemeinsame Teern mehrerer Dateien die Komprimierung mit den Standardwerkzeugen verbessern, z. B. gzip, bzip2, xz?

Ich habe lange gedacht, dass dies der Fall ist, habe es aber nie getestet. Wenn wir 2 Kopien derselben 20-MB-Datei mit zufälligen Bytes haben, die zusammen geteert sind, könnte ein cleveres Komprimierungsprogramm, das dies erkennt, den gesamten Tarball auf fast 20 MB komprimieren.

Ich habe gerade dieses Experiment mit gzip, bzip2 und xz versucht, um 1) eine Datei mit zufälligen Bytes, 2) einen Tarball mit zwei Kopien dieser Datei und 3) eine Katze mit zwei Kopien dieser Datei zu komprimieren. In allen Fällen hat die Komprimierung die Dateigröße nicht verringert. Dies wird für Fall 1 erwartet, aber für die Fälle 2 und 3 ist das optimale Ergebnis, dass eine 40-MB-Datei auf fast 20 MB verkleinert werden kann. Das ist eine schwierige Erkenntnis für ein Komprimierungsprogramm, insbesondere weil die Redundanz weit entfernt ist. Ich würde also kein perfektes Ergebnis erwarten, aber ich hatte immer noch gedacht, dass es eine gewisse Komprimierung geben würde.

Prüfung:

dd if=/dev/urandom of=random1.txt bs=1M count=20
cp random1.txt random2.txt
cat random1.txt random2.txt > random_cat.txt
tar -cf randoms.tar random1.txt random2.txt
gzip -k random* &
bzip2 -k random* &
xz -k random* &
wait
du -sh random*

Ergebnis:

20+0 records in
20+0 records out
20971520 bytes (21 MB) copied, 1.40937 s, 14.9 MB/s
[1]   Done                    gzip -k random*
[2]-  Done                    bzip2 -k random*
[3]+  Done                    xz -k random*
20M random1.txt
21M random1.txt.bz2
21M random1.txt.gz
21M random1.txt.xz
20M random2.txt
21M random2.txt.bz2
21M random2.txt.gz
21M random2.txt.xz
40M random_cat.txt
41M random_cat.txt.bz2
41M random_cat.txt.gz
41M random_cat.txt.xz
41M randoms.tar
41M randoms.tar.bz2
41M randoms.tar.gz
41M randoms.tar.xz

Ist das allgemein das, was ich erwarten sollte?

Gibt es hier eine Möglichkeit, die Komprimierung zu verbessern?

Praxeolitisch
quelle
Ihre Testfälle sind schlechte Beispiele. Versuchen Sie, Ihren Test beispielsweise mit einem Verzeichnis von ~ 100 (echten) Textdateien durchzuführen.
lcd047
Warum ist es ein schlechtes Beispiel? Wir wissen genau, was uns erwartet. Eine zufällige Datei kann nicht komprimiert werden und 2 einer zufälligen Datei können in zwei Hälften komprimiert werden.
Praxeolitic
Der "zufällige" Dateiinhalt ist ein Problem. Sie sind inkompressibel. Verwenden Sie zwei verschiedene große Textdateien, um eine bessere Vorstellung zu erhalten. Eine verwandte Idee ist hier "normalisierte Kompressionsdifferenz". Sie können unter ims.cuhk.edu.hk/~cis/2005.4/01.pdf nachsehen, auf welche Probleme Sie bei dieser Art von Tests stoßen können.
Bruce Ediger

Antworten:

11

Sie haben es mit der "Blockgröße" des Kompressors zu tun. Die meisten Komprimierungsprogramme unterteilen die Eingabe in Blöcke und komprimieren jeden Block. Es scheint, dass die bzip-Blockgröße nur bis zu 900 KB beträgt, sodass kein Muster angezeigt wird, dessen Wiederholung länger als 900 KB dauert.

http://www.bzip.org/1.0.3/html/memory-management.html

gzip scheint 32K-Blöcke zu verwenden.

Mit xz hast du aber Glück! Von der Manpage:

   Preset   DictSize   CompCPU   CompMem   DecMem
     -0     256 KiB       0        3 MiB    1 MiB
     -1       1 MiB       1        9 MiB    2 MiB
     -2       2 MiB       2       17 MiB    3 MiB
     -3       4 MiB       3       32 MiB    5 MiB
     -4       4 MiB       4       48 MiB    5 MiB
     -5       8 MiB       5       94 MiB    9 MiB
     -6       8 MiB       6       94 MiB    9 MiB
     -7      16 MiB       6      186 MiB   17 MiB
     -8      32 MiB       6      370 MiB   33 MiB
     -9      64 MiB       6      674 MiB   65 MiB

"xz -8" findet also bis zu 32 MB Muster und "xz -9" bis zu 64 MB Muster. Aber Vorsicht, wie viel RAM benötigt wird, um die Komprimierung durchzuführen (und zu dekomprimieren) ...

Daten
quelle
1
Ja, xz -8 schrumpft den Tarball und die Katze im Test auf 21M.
Praxeolitic
1
Es steckt mehr dahinter als nur die Blockgröße. Aber die ganze Geschichte kann nicht in ein paar Absätzen über SE erklärt werden.
lcd047
1
@Praxeolitic Ein Kurs zur Datenkomprimierung könnte helfen.
lcd047
1
@ lcd047 Komprimierung ist ein großes Thema, aber die Frage hier war einfach "Warum hat diese Komprimierung nicht stattgefunden?"
Datumess
1
Ich denke auch, dass es nützlich ist zu wissen, dass "-9" bei den meisten Befehlszeilen-Kompressoren nicht "mehr Mühe geben, Muster zu finden" bedeutet, sondern "größere Musterräume berücksichtigen".
Datumess
2

Der von Ihnen ausgewählte zufällige Dateiinhalt ist kein gutes Beispiel - die komprimierten Tarfiles sind größer als die Originale. Sie sehen dasselbe bei Dateien in bereits komprimierten Formaten (z. B. viele Bild- / Audio- / Videoformate).

Das Zusammenstellen mehrerer Dateien mit komprimierbarem Inhalt führt jedoch in der Regel zu einer geringeren Gesamtgröße der Tarfiles als das separate Tarieren, insbesondere wenn die Inhalte ähnlich sind (z. B. Protokolldateien aus demselben Programm). Der Grund dafür ist, dass einige der Komprimierungsoffsetdaten pro Datei (wie Musterarrays für einige Komprimierungsalgorithmen) von allen Dateien in derselben Tarfile gemeinsam genutzt werden können.

Dan Cornilescu
quelle
@kos Dies hängt vom verwendeten Algorithmus und den Daten ab. Die genannten 33% sind für einen ganz besonderen Fall. Mit gzip und bzip2 habe ich 1000 zufällig generierte 1-MB-Dateien gemessen, was einer Steigerung von <1% für jede Datei entspricht.
Jofel
2

Wie bereits angegeben:

  1. Die Verwendung von Zufallsdateien ist nicht gut, da sie bereits die maximale "Informationsentropie" enthalten und daher nicht komprimiert werden.
  2. Sie müssen viele Dateien für einen fairen Vergleich packen .

Ein besserer Testfall könnte folgender sein:

cd /var/tmp
tar -zcf test1.tar /usr
tar -cf test2.tar /usr
gzip test2.tar
ls -h

(Hinweis: Ich hoffe, es gibt keine Reittiere unter /usr!)

Sie können tar -jcfstattdessen für die xz-Komprimierung verwenden.

Wenn nun test2.tar.gzkleiner als test1.tar.gz ist, ist der Test erfolgreich (dh Teerdateien, dann ist das Komprimieren besser als das Komprimieren und dann das Teern). Ich vermute, es wird für viele (dh Tausende) Dateien sein. Der Nachteil ist, dass die Ausführung möglicherweise länger dauert und viel mehr Speicherplatz benötigt, da zuerst die gesamte TAR-Datei erstellt und dann komprimiert werden muss. Aus diesem Grund wird stattdessen häufig die erste Methode verwendet, da jede Datei im laufenden Betrieb komprimiert wird, auch wenn sie möglicherweise keinen so kleinen Tarball enthält.

In unserer Offsite-Sicherung sichern wir beispielsweise normalerweise 4.000.000 Dateien mit einer Gesamtgröße von 2 TB. Die erste Methode ist also viel schneller und erfordert keine zusätzlichen 2 TB Festplatte.

Quazza
quelle
Nicht -zkomprimieren das Archiv (dh der Teer)? Normalerweise czfendet der Ausgabedateiname mit .tar.gz, um dies hervorzuheben.
Jari Keinänen