Ähnliche Dateien effizient komprimieren

11

Ich muss häufig Dateien komprimieren, die einander sehr ähnlich sind.

Derzeit verwende ich 7Zip, das eine 16-GB-Datei mit 8 Kernen mit Ultra-Einstellungen in etwa 35 Minuten auf 1,2 GB komprimiert.

Es scheint mir, dass ein Großteil dieser Zeit für die Berechnung des Wörterbuchs zur Komprimierung aufgewendet wird. Da die Dateien sehr ähnlich sind, ist das tatsächlich verwendete Wörterbuch wahrscheinlich auch ähnlich.

Gibt es ein Windows-basiertes Komprimierungstool (7Zip mit einer mir nicht bekannten Option oder ein anderes Tool), mit dem das Wörterbuch gespeichert und das gespeicherte Wörterbuch für nachfolgende Dateien wiederverwendet werden kann?

Gibt es eine bessere Möglichkeit, das Problem der Beibehaltung eines ähnlichen Komprimierungsverhältnisses wie bei einer deutlich schnelleren Komprimierung anzugehen?

compression Eric J.
quelle

Antworten:

5

Der Lempel-Ziv-Welch- Komprimierungsalgorithmus (LZW) ist von Natur aus rechenintensiv, wobei der Großteil der Arbeit selbst tatsächlich das Wörterbuch berechnet. So funktioniert LZW buchstäblich.

Der Algorithmus selbst fügt einen neuen Wörterbucheintrag für jedes nächste gescannte "Symbol" hinzu, und daher wird während jeder einzelnen Iteration ein neuer Eintrag zum Wörterbuch hinzugefügt. Tatsächlich wird das Wörterbuch zur komprimierten Kopie der Datei und ist somit tatsächlich das einzige, was die LZW-Komprimierung in erster Linie für eine erhebliche Rechenzeit benötigt.

Wenn Sie so etwas wie die Huffman-Codierung verwenden , ist eine Wiederverwendung des Wörterbuchs tatsächlich möglich (auf Kosten einer möglicherweise nicht optimalen Komprimierungsrate / -größe). Die meisten modernen Komprimierungsalgorithmen und -werkzeuge verwenden jedoch den LZW-Algorithmus für Effizienz und Geschwindigkeit (die Huffman-Komprimierung würde zwei Durchgänge über die Daten erfordern [einer zum Generieren des Huffman-Baums / der Huffman-Tabelle, ein anderer zum tatsächlichen Komprimieren der Daten], während LZW in abgeschlossen werden kann ein einziger Durchgang).

Durchbruch
quelle
1
Wäre mit Huffman und einem vordefinierten Wörterbuch nur ein Durchgang erforderlich? Gibt es handelsübliche Huffman-basierte Tools, die gespeicherte Wörterbücher unterstützen?
Eric J.
@EricJ. Ja, mit einem vordefinierten Wörterbuch wäre es eine Single-Pass-Codierung. Ich kenne keine Software, die dies kann, obwohl ich persönlich Programme geschrieben habe, die dies tun. Obwohl ich es noch nicht ausprobiert habe, scheint dieses Tool genau das zu können. Beachten Sie jedoch, dass Sie (im Gegensatz zu LZW) zum Dekodieren eines Huffman-codierten Bitstroms weiterhin das Originalwörterbuch benötigen, um die Daten zu dekomprimieren.
Durchbruch
Basierend auf dem Alter dieses Tools schätze ich, dass es Single-Threaded ist. Ich würde vermuten, dass die Verwendung von 1 Kern anstelle von 8 den Nutzen eines festen Wörterbuchs ausgleichen würde :-( In meinem Szenario ist es möglich, das Wörterbuch am anderen Ende verfügbar zu haben (Übertragung großer Dateien zwischen Rechenzentren).
Eric J.
2

Im Gegensatz zum DEFLATE-Algorithmus verwendet LZMA von 7-Zip standardmäßig eine solide Komprimierung, die die Redundanz zwischen Dateien nutzt. Dies funktioniert mit Standardeinstellungen, solange die Dateien klein genug sind.

Mit den Standardeinstellungen von 2 GB für die Solid Block-Größe wird eine 16-GB-Datei tatsächlich als 8 separate Blöcke komprimiert.

Wie @Breakthorugh bereits sagte, wird das Wörterbuch im laufenden Betrieb generiert. Sie können dies empirisch überprüfen, indem Sie die Größe des Solid-Blocks auf Solid (alle Dateien gleichzeitig komprimieren) und Non-Solid (jede Datei separat komprimieren ) einstellen .

Das Erhöhen der Solid Block-Größe führt tatsächlich zu einer Verlangsamung, kann jedoch zu einem viel besseren Komprimierungsverhältnis führen. Wenn Sie beispielsweise zwei identische Dateien komprimieren, wird das Archiv bei nicht fester Komprimierung fast doppelt so groß.

Dennis
quelle
1
In meinem Fall komprimiere ich die ähnlichen Dateien nacheinander bei verschiedenen Gelegenheiten. In einem bestimmten Archiv befindet sich nur jede 16-GB-Datei.
Eric J.
Ah, OK. Das habe ich falsch interpretiert. Werden die alten Archive gelöscht, wenn das neue erstellt wird? Wenn nein, wäre es zulässig, mehrere Dateien in einem einzigen Archiv zu speichern? Das hilft nicht bei der Komprimierungsgeschwindigkeit, aber je nachdem, wie ähnlich die Dateien tatsächlich sind, kann es beim Verhältnis hilfreich sein.
Dennis
1
Egal, das tut es nicht. Das Aktualisieren eines soliden Archivs dauert viel länger, führt jedoch nicht zu einer besseren Komprimierung.
Dennis