Warum sind diese (verlustfreien) Komprimierungsmethoden für viele ähnliche PNG-Bilder ineffektiv?

Ich bin gerade auf folgendes gestoßen: Ich habe mehrere identische Kopien eines PNG-Bildes in einen Ordner gelegt und dann versucht, diesen Ordner mit den folgenden Methoden zu komprimieren:

• tar czf folder.tar.gz folder/
• tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz (Diese Einstellung eignet sich gut für identische Bilder, bei ähnlichen Bildern beträgt der Gewinn jedoch Null.)
• zip -r folder.zip folder/

Als ich die Größe von .tar.gz, überprüfte , .tar.xzstellte .zipich fest, dass es fast dasselbe ist wie das von folder/.
Ich verstehe, dass ein PNG-Bild selbst ein hohes Maß an Komprimierung aufweisen kann und daher nicht weiter komprimiert werden kann. Beim Zusammenführen vieler ähnlicher (in diesem Fall sogar identischer) PNG-Bilder zu einem Archiv und anschließenden Komprimieren des Archivs würde ich jedoch eine deutliche Verringerung der erforderlichen Größe erwarten. Bei identischen Bildern würde ich eine Größe erwarten, die in etwa der Größe eines einzelnen Bildes entspricht.

Schauen Sie sich an, wie Kompressionsalgorithmen funktionieren. Zumindest diejenigen aus der Lempel-Ziv-Familie ( gzip verwendet LZ77 , zipanscheinend meistens auch und xz verwendet LZMA ) komprimieren etwas lokal : Ähnlichkeiten, die weit voneinander entfernt liegen, können nicht identifiziert werden.

Die Details unterscheiden sich zwischen den Methoden, aber die Quintessenz ist, dass der Algorithmus bis zum Erreichen des zweiten Bildes den Anfang des ersten bereits "vergessen" hat. Und so weiter.

Sie können versuchen, die Parameter der Komprimierungsmethode manuell zu ändern. wenn Fenstergröße (LZ77) bzw. Block- / Blockgröße (spätere Methoden) sind mindestens so groß wie zwei Bilder, Sie werden wahrscheinlich eine weitere Komprimierung sehen.

Beachten Sie, dass das oben Genannte nur dann wirklich gilt, wenn Sie identische oder nahezu identische unkomprimierte Bilder haben. Wenn es Unterschiede gibt, sehen komprimierte Bilder im Speicher möglicherweise nicht gleich aus. Ich weiß nicht, wie die PNG-Komprimierung funktioniert. Sie können die hexadezimalen Darstellungen der Bilder, die Sie für freigegebene Teilzeichenfolgen haben, manuell überprüfen.

Beachten Sie auch, dass Sie trotz geänderter Parameter und Redundanz nicht auf die Größe eines Bildes kommen. Größere Wörterbücher bedeuten eine größere Codewortgröße, und selbst wenn zwei Bilder genau identisch sind, müssen Sie möglicherweise das zweite mit mehreren Codewörtern (die in das erste zeigen) codieren.

Warum passiert das? Es gibt tatsächlich zwei verschiedene Effekte geschieht hier:

• Jede Datei wird unabhängig komprimiert. Einige Archivierungsprogramme - einschließlich zip - komprimieren jede Datei unabhängig voneinander, ohne dass Speicherplatz von einer Datei in eine andere vorhanden ist. Mit anderen Worten, jede Datei wird separat komprimiert, und die komprimierten Dateien werden zu einem Archiv zusammengefügt.

• Kurzzeitgedächtnis. Einige Archivierungsprogramme können Informationen zu einer Datei verwenden, um die nächste Datei besser zu komprimieren. Sie verketten die Dateien effektiv und komprimieren dann das Ergebnis. Das ist eine Verbesserung.

  Siehe auch Nayukis Antwort, um mehr darüber zu erfahren .

  Es gibt jedoch ein zweites Problem. Einige Komprimierungsschemata - einschließlich zip, gzip und bzip2 - haben einen begrenzten Speicher. Sie komprimieren die Daten im laufenden Betrieb und behalten die letzten 32 KB bei, erinnern sich jedoch nicht an Daten, die viel früher in der Datei aufgetreten sind. Mit anderen Worten, sie können keine duplizierten Daten finden, wenn die Duplikate weiter als 32 KB voneinander entfernt sind. Wenn die identischen Dateien kurz sind (kürzer als etwa 32 KB), kann der Komprimierungsalgorithmus die duplizierten Daten entfernen. Wenn die identischen Dateien lang sind, wird der Komprimierungsalgorithmus abgenutzt und wertlos: Er kann keine von ihnen erkennen das Duplikat in Ihren Daten. (Bzip merkt sich die letzten 900 KB an Daten anstelle von 32 KB.)

  Alle Standardkomprimierungsalgorithmen haben eine maximale Speichergröße, ab der sie keine Muster mehr erkennen können. Bei einigen ist diese Anzahl jedoch viel größer als bei anderen. Für Bzip sind es ungefähr 900 KB. Für xz sind es ungefähr 8 MB (mit Standardeinstellungen). Für 7z sind es ungefähr 2 GB. 2 GB sind mehr als ausreichend, um die duplizierten Kopien von PNG-Dateien zu erkennen (die normalerweise viel kleiner als 2 GB sind). Darüber hinaus versucht 7z, Dateien, die sich wahrscheinlich ähneln, im Archiv nebeneinander abzulegen, damit der Kompressor besser funktioniert. Davon weiß Teer nichts.

  Siehe auch Raphaels Antwort und Nayukis Antwort für eine genauere Erklärung dieses Effekts.

Wie dies auf Ihre Einstellung zutrifft. Für Ihr spezielles Beispiel arbeiten Sie mit PNG-Bildern. PNG-Bilder sind selbst komprimiert, sodass Sie sich jede PNG-Datei als eine Folge zufällig aussehender Bytes vorstellen können, ohne Muster oder Duplikate in der Datei. Es gibt nichts, was ein Kompressor ausnutzen könnte, wenn er sich ein einzelnes PNG-Bild ansieht. Wenn Sie versuchen, eine einzelne PNG-Datei zu komprimieren (oder ein zip / tar / ... -Archiv zu erstellen, das nur eine einzige PNG-Datei enthält), wird keine Komprimierung durchgeführt.

Schauen wir uns nun an, was passiert, wenn Sie versuchen, mehrere Kopien derselben PNG-Datei zu speichern:

• Kleine Dateien. Wenn die PNG-Datei sehr klein ist, funktioniert alles außer zip großartig. Zip schlägt spektakulär fehl: Es komprimiert jede Datei unabhängig voneinander, sodass es keine Chance hat, die Redundanz / Duplizierung zwischen den Dateien zu erkennen. Außerdem wird beim Komprimieren jeder PNG-Datei keine Komprimierung erzielt. Die Größe eines Zip-Archivs wird riesig sein. Im Gegensatz dazu ist die Größe eines tar-Archivs (ob mit gzip, bzip2 oder xz komprimiert) und eines 7z-Archivs gering, da im Grunde eine Kopie der Datei gespeichert wird und dann bemerkt wird, dass alle anderen identisch sind - sie profitieren vom Beibehalten des Speichers von einer Datei zur anderen.

• Große Dateien. Wenn die PNG-Datei groß ist, funktioniert nur 7z gut. Vor allem zip scheitert weiterhin spektakulär. Außerdem schlagen tar.zip und tar.bzip2 fehl, da die Größe der Datei größer ist als das Speicherfenster des Kompressors: Da der Kompressor die erste Kopie der Datei sieht, kann er sie nicht verkleinern (da sie bereits komprimiert wurde) ); Zu dem Zeitpunkt, an dem der Anfang der zweiten Kopie der Datei zu sehen beginnt, hat er bereits die Byte-Sequenzen vergessen, die am Anfang der ersten Datei zu sehen sind, und kann keine Verbindung herstellen, dass diese Daten tatsächlich ein Duplikat sind.

  Im Gegensatz dazu eignen sich tar.xz und 7z weiterhin hervorragend für mehrere Kopien einer großen PNG-Datei. Sie haben nicht die Einschränkung "kleine Speichergröße" und können feststellen, dass die zweite Kopie der Datei mit der ersten Kopie identisch ist, sodass sie nicht ein zweites Mal gespeichert werden muss.

Was können Sie dagegen tun? Verwenden Sie 7z. Es verfügt über eine Reihe von Heuristiken, mit denen identische oder ähnliche Dateien erkannt und in diesem Fall sehr gut komprimiert werden können. Sie können lrzip auch mit lzop-Komprimierung betrachten.

Wie soll ich wissen? Ich konnte dies überprüfen, indem ich einige Experimente mit 100 Kopien einer Datei mit zufälligen Bytes versuchte. Ich habe 100 Kopien einer 4-KB-Datei, 100 Kopien einer 1-MB-Datei und 100 Kopien einer 16-MB-Datei ausprobiert. Folgendes habe ich gefunden:

Size of file      Size of compressed archive (with 100 copies)
                  zip  tar.gz  tar.bz2  tar.xz    7z
         4KB    414KB     8KB     10KB     5KB    5KB
         1MB    101MB   101MB    101MB     1MB    2MB
        16MB    1.6G    1.6GB    1.6GB   1.6GB  401MB

Wie Sie sehen, ist zip schrecklich, egal wie klein Ihre Datei ist. 7z und xz sind beide gut, wenn Ihre Bilder nicht zu groß sind (xz ist jedoch zerbrechlich und hängt von der Reihenfolge ab, in der die Bilder im Archiv abgelegt werden, wenn Sie einige Duplikate und einige Nicht-Duplikate zusammengemischt haben). 7z ist verdammt gut, auch für große Dateien.

Verweise. Dies wird auch in einer Reihe von Beiträgen bei Super User gut erklärt. Schau mal:

• Warum beseitigt die Gzip-Komprimierung keine doppelten Datenblöcke?
• Warum kann Zip eine einzelne Datei kleiner als mehrere Dateien mit demselben Inhalt komprimieren?
• Komprimieren vieler ähnlich großer Dateien
• Komprimieren Sie ähnliche Dateien effizient
• Gibt es ein Komprimierungs- oder Archivierungsprogramm für Windows, das auch die Deduplizierung ausführt?
• Effizienteres Dateikomprimierungsprogramm für viele identische Dateien?

Beachten Sie zunächst, dass das PNG-Bildformat im Grunde rohe RGB-Pixel (mit etwas Lichtfilterung) sind, die durch das DEFLATE-Komprimierungsformat übertragen werden. Im Allgemeinen werden komprimierte Dateien (PNG, JPEG, MP3 usw.) nicht erneut komprimiert. Aus praktischen Gründen können wir Ihre PNG-Datei für den Rest des Experiments als inkomprimierbare Zufallsdaten behandeln.

Beachten Sie zweitens, dass die Formate ZIP und gzip auch den Codec DEFLATE verwenden. (Dies würde erklären, warum das Komprimieren im Vergleich zum Komprimieren einer einzelnen Datei im Wesentlichen dieselbe Ausgabegröße erzeugt.)

Gestatten Sie mir nun, jeden Testfall einzeln zu kommentieren:

• tar czf folder.tar.gz folder/

  Dadurch wird eine (unkomprimierte) TAR-Datei erstellt, in der alle identischen PNG-Dateien (mit einer kleinen Menge an Metadaten und Auffüllungen) verknüpft sind. Dann wird diese einzelne Datei durch den gzip-Kompressor gesendet, um eine komprimierte Ausgabedatei zu erstellen.

  Leider unterstützt das DEFLATE-Format nur ein LZ77-Wörterbuchfenster mit 32768 Bytes. Auch wenn die TAR sich wiederholende Daten enthält, kann sich der DEFLATE-Kompressor bei einer PNG-Datei von mehr als 32 KiB die Daten nicht weit genug zurückerinnern, um die Tatsache auszunutzen, dass sich identische Daten wiederholen.

  Wenn Sie dieses Experiment beispielsweise mit einer 20-KB-PNG-Datei wiederholen, die zehnmal dupliziert wurde, erhalten Sie höchstwahrscheinlich eine gzip-Datei, die nur etwas größer als 20 KB ist.

• tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz

  Dadurch wird wie zuvor eine TAR-Datei erstellt und anschließend das xz-Format und der LZMA / LZMA2-Kompressor verwendet. Ich konnte in dieser Situation keine Informationen über LZMA finden, aber von 7-Zip für Windows weiß ich, dass es große Wörterbuchfenstergrößen (z. B. 64 MiB) unterstützen kann. Möglicherweise haben Sie suboptimale Einstellungen verwendet und der LZMA-Codec konnte die TAR-Datei möglicherweise auf die Größe einer PNG-Datei reduzieren.

• zip -r folder.zip folder/

  Das ZIP-Format unterstützt keine "soliden" Archive. Das heißt, jede Datei wird unabhängig komprimiert. Wir gingen davon aus, dass jede Datei inkomprimierbar ist. Daher kann die Tatsache, dass jede Datei identisch ist, nicht ausgenutzt werden, und die ZIP-Datei ist so groß wie die direkte Verkettung aller Dateien.

Das Problem ist, dass (die meisten) Komprimierungsschemata das Wissen über Ihre Daten nicht haben. Selbst wenn Sie Ihre PNGs in Bitmaps dekomprimieren und im Tarball komprimieren, erhalten Sie keine (wesentlich) kleineren Ergebnisse.

Bei vielen ähnlichen Bildern wäre ein geeignetes Komprimierungsschema ein Videocodec.

Mit verlustfreier Codierung sollten Sie fast das perfekte Komprimierungsergebnis erzielen, das Sie erwarten.

Wenn Sie es testen möchten, verwenden Sie Folgendes:

ffmpeg -i img%03d.png -c:v libx264 -c:v libx264 -profile:v high444 -crf 0 out.mp4

https://trac.ffmpeg.org/wiki/Create%20a%20video%20slideshow%20from%20images

PNG ist die Kombination von Filter + LZ77 + Huffman (die Kombination von LZ77 + Huffman heißt Deflate) in dieser Reihenfolge:

Schritt 1) ​​Wenn sich der Filter von None unterscheidet, wird der Wert der Pixel durch den Unterschied zu den benachbarten Pixeln ersetzt (weitere Informationen finden Sie unter http://www.libpng.org/pub/png/book/chapter09.html ). . Dies erhöht die Komprimierung von Bildern mit Farbverläufen (so wird ... 4 5 6 7 zu ... 1 1 1) und kann in Bereichen mit derselben Farbe hilfreich sein (... 3 3 3 5 5 5 5 5 wird 0) 0 0 2 0 0 0 0 0). Standardmäßig sind Filter in 24-Bit-Bildern aktiviert und in 8-Bit-Bildern mit einer Palette deaktiviert.

Schritt 2) Die Daten werden mit LZ77 komprimiert, das wiederholte (Übereinstimmungs-) Zeichenfolgen von Bytes durch ein Tupel ersetzt, das den Abstand zur Übereinstimmung und die Länge der Übereinstimmung enthält.

Schritt 3) Das Ergebnis von Schritt 2 wird mit Huffman-Code codiert, der Symbole fester Länge durch Codes variabler Länge ersetzt. Je häufiger das Symbol ist, desto kürzer ist der Code.

Es gibt mehrere Probleme:

Eine kleine Änderung, die nur wenige Pixel betrifft, führt zu Änderungen der Ergebnisse aus den drei Schritten der PNG-Komprimierung:

1) Der gefilterte Wert benachbarter Pixel ändert sich (abhängig vom verwendeten Filter). Dadurch werden die Auswirkungen kleiner Änderungen verstärkt.

2) Die Änderung bedeutet, dass die Übereinstimmungen mit diesem Bereich unterschiedlich sind. Das Ändern von 333333 in 333533 führt beispielsweise dazu, dass ein anderes Vorkommen von 333333 nicht mehr übereinstimmt, sodass eine andere Übereinstimmung mit 333333 mit einer anderen Entfernung oder dieselbe Übereinstimmung mit einer kürzeren Länge und dann eine weitere Übereinstimmung für die letzten 3 Bytes ausgewählt wird. An sich wird das die Ergebnisse sehr verändern.

3) Das größte Problem ist in Schritt 3. Der Huffman-Code verwendet eine variable Anzahl von Bits, sodass selbst eine kleine Änderung dazu führt, dass alles, was folgt, nicht mehr ausgerichtet wird. AFAIK Die meisten Komprimierungsalgorithmen können keine Übereinstimmungen erkennen, die nicht byteausgerichtet sind, sodass die Komprimierung der bereits komprimierten Daten, die auf die Änderung folgen, verhindert (oder zumindest stark reduziert wird), es sei denn, der Komprimierer kann Übereinstimmungen erkennen, die nicht byteausgerichtet sind.

Die anderen Fragen werden bereits in anderen Antworten behandelt:

4) Gzip verwendet denselben Deflate-Algorithmus mit einem 32-KB-Wörterbuch. Wenn die PNG-Dateien also größer als 32 KB sind, werden die Übereinstimmungen nicht erkannt, auch wenn sie identisch sind. Bzip2 ist in dieser Hinsicht besser, da es einen Block von 900 KB verwendet. XZ verwendet LZMA, wobei IIRC ein 4-MB-Wörterbuch in der Standardkomprimierungsstufe hat. 5) Das Zip-Format verwendet keine feste Komprimierung, sodass ähnliche oder identische Dateien nicht besser komprimiert werden.

Vielleicht werden Kompressoren aus der PAQ- oder PPMD-Familie besser komprimiert, aber wenn Sie viele ähnliche Bilddateien komprimieren müssen, können Sie drei Ansätze in Betracht ziehen:

1) Speichern Sie die Bilder unkomprimiert (mit PNG -0 oder in einem Format ohne Komprimierung) und komprimieren Sie sie mit einem Kompressor mit einem großen Wörterbuch oder Blockgröße. (LZMA wird gut funktionieren)

2) Eine andere Option wäre, die Filter beizubehalten, aber die Deflate-Komprimierung aus den PNGs zu entfernen. Dies kann beispielsweise mit dem Dienstprogramm ( AdvDef ) erfolgen. Dann komprimieren Sie die resultierenden unkomprimierten PNGs. Nach der Dekomprimierung können Sie das unkomprimierte PNG beibehalten oder mit AdvDef erneut komprimieren (dies wird jedoch einige Zeit dauern).

Sie müssen beide Ansätze testen, um festzustellen, welche Komprimierung am stärksten ist.

3) Die letzte Option wäre das Konvertieren der PNG-Bilder in ein Video, das Komprimieren mit einem verlustfreien Videokomprimierer wie x264 lossless (wobei besonders auf das richtige Farbformat geachtet wird) und das Extrahieren der Frames in einzelne PNG-Bilder. Das geht mit ffmpeg. Sie müssten auch die Zuordnung zwischen der Bildnummer und dem ursprünglichen Namen beibehalten.

Das wäre der komplexeste Ansatz, aber wenn die PNGs alle Teil einer Animation sind, ist dies möglicherweise der effektivste. Sie benötigen jedoch ein Videoformat, das Transparenz unterstützt, wenn Sie es benötigen.

Bearbeiten: Es gibt auch MNG-Format, würde es nicht oft verwendet.

Wenn Sie über spezielle Datensätze verfügen, verwenden Sie spezielle Algorithmen und keine Mehrzweckwerkzeuge.

Die Antwort ist, dass Ihre gewählte verlustfreie Komprimierung nicht für das gemacht wird, was Sie tun. Niemand erwartet von Ihnen, dass Sie dasselbe Bild zweimal komprimieren, und selbst wenn Sie dies (aus Versehen) tun, würde das Vergleichen mit allen vorherigen Eingaben Ihren Algorithmus zu O (n ^ 2) machen (vielleicht ein bisschen besser, aber der naive Ansatz wäre mindestens n ^ 2).

Die meisten Ihrer Komprimierungsprogramme, die Sie in O (n) getestet haben, sind schneller als das optimale Komprimierungsverhältnis. Niemand möchte seinen Computer 5 Stunden lang laufen lassen, nur um ein paar MB zu sparen, besonders heutzutage. Bei größeren Eingaben wird alles über O (n) zu einem Laufzeitproblem.

Ein weiteres Problem ist RAM. Sie können zu keinem Zeitpunkt auf jeden Teil Ihrer Eingabe zugreifen, wenn die Eingabe groß genug ist. Selbst wenn man dies nicht beachtet, wollen die meisten Leute nicht ihren gesamten RAM oder ihre CPU aufgeben, nur um etwas zu komprimieren.

Wenn Sie Muster in Ihren Dateien haben, die Sie komprimieren möchten, müssen Sie manuelle Operationen an ihnen durchführen, Ihre eigene Komprimierung schreiben oder möglicherweise eine Komprimierung vom Typ "Archiv" (Nano) verwenden. Eine Komprimierung für die Langzeitlagerung, die für den täglichen Gebrauch zu langsam ist.

Eine weitere Option wäre möglicherweise eine verlustfreie Videokomprimierung.

Das PNG-Dateiformat verwendet den DEFLATE-Komprimierungsalgorithmus bereits intern. Dies ist der gleiche Algorithmus wie er von xz, gzip und zip verwendet wird - nur in einigen Variationen.tar.gzund und tar.xznutzen Sie die Ähnlichkeit zwischen Dateien, die zipnicht.

Tatsächlich führen Sie also eine DEFLATE-Komprimierung über DEFLATE-komprimierte Dateien durch - aus diesem Grund behalten die Dateien fast die ursprüngliche Größe bei.

Das bzip2Programm (auch ein verwandter Algorithmus) ist besser, wenn es um (fast) identische Dateien geht.

# for i in $(seq 4); do cp test.png test$i.png; done
# tar -cjf archive.tar.bz2 *.png
# ls -l
-rw-r--r-- 1 abcde users  43813 15. Jul 08:45 test.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:45 test1.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test2.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test3.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test4.png
-rw-r--r-- 1 abcde users  68115 15. Jul 08:47 archive.tar.bz2