Wie unterscheiden sich die verschiedenen Komprimierungsstufen von gzip?

Ich versuche zu verstehen, wie verschiedene Komprimierungsstufen (1-9) von gzip sich in der Art und Weise unterscheiden, wie die Codierung implementiert wird.Wie unterscheiden sich die verschiedenen Komprimierungsstufen von gzip?

Ich habe den Zlib C-Quellcode angeschaut und es scheint, dass es damit zu tun hat, wie erschöpfend die Suche nach der längsten übereinstimmenden Zeichenkette ist, aber nach spezifischeren Informationen suchend.

Zum Beispiel ergeben die Ebenen irgendwelche Unterschiede in der Zuordnung von Huffman-Codes?

Quelle

2017-07-04 glupyan

Die Ebenen unterscheiden sich nur darin, wie stark Deflate nach passenden Strings sucht, wie Sie beobachtet haben. Die Huffman-Kodierung erfolgt an einer ausgewählten festen Anzahl von Symbolen (Literale und Länge/Abstand-Paare), wodurch ein "Block" erzeugt wird, wobei diese Zahl durch die Speicherebene und nicht durch die Komprimierungsstufe definiert ist. Die erzeugten Huffman-Codes unterscheiden sich notwendigerweise, da die zu codierenden Symbole unterschiedlich sind. Die Auswahl des Speicherpegels wirkt sich auch auf die Komprimierung aus, da eine größere Anzahl von Symbolen die Kosten der Codebeschreibung für einen Block über mehrere Symbole verteilt. Zu viele Symbole können jedoch eine Anpassung der Huffman-Codes an lokale Änderungen verhindern in der Statistik der Symbole. Der Standard-Speicherlevel ist 8 (was zu 16.383 Symbolen pro Block führt), da Tests zeigten, dass dies eine bessere Komprimierung als Level 9 (32.767 Symbole pro Block) ergab. Ihre Laufleistung kann jedoch variieren.

Quelle

2017-07-04 13:48:53

Danke! Habe ich richtig gedacht, dass, wenn wiederholte Strings eher weiter hinten auftreten (aber innerhalb desselben Blocks), mehr Speicher benötigt wird, um die größere Distanz zu speichern? Wenn beispielsweise der gleiche Grad an (vollständiger) Wiederholung in einer Datei angenommen wird, wenn wiederholte Strings im Durchschnitt 50 Bytes zurück auftreten, ergibt sich ein etwas besseres Kompressionsverhältnis, als wenn wiederholte Strings im Durchschnitt 500 Bytes auftreten würden. Oder ist der Speicher für Entfernungen reserviert? – glupyan

Es dauert mehr Bits für weitere Entfernungen. Ein Abstand von 50 benötigt 4 Bits plus einen Huffman-Code (mindestens ein Bit), während ein Abstand von 500 7 Bits plus einen Huffman-Code benötigt. Die Größe der Huffman-Codes hängt davon ab, wie oft diese Fächer im Vergleich zu den anderen Bins als Entfernungen angezeigt werden. –

Soweit ich mich erinnere, ja, es basiert hauptsächlich auf der Größe des Puffers, den Sie zuweisen werden. Je größer der Puffer, desto besser können Sie komprimieren. Wenn Sie einen Puffer mit einer Größe von etwa input file size × 1.2 zuweisen können, erhalten Sie in den meisten Fällen die bestmögliche Komprimierung mit Huffman.

Der Grund ist, dass die Huffman-Tabelle alle Bytes mit dem bestmöglichen Ergebnis umfasst, wenn Sie einen so großen Puffer haben. Wenn der Algorithmus keinen Pufferspeicher mehr hat, muss er seine Tabelle zurücksetzen (dafür wird ein Code im Stream hinzugefügt), und das bedeutet, dass Sie eine neue Codierungstabelle von Grund auf neu starten, was bedeutet, dass Sie Bytes verlieren, um diese neue Tabelle neu zu gestalten ...

Obwohl es Fälle gibt, in denen das Zurücksetzen nützlich sein kann (dh viele Bytes in der ersten Hälfte auf den Wert X gesetzt sind und dann viele mehr den Wert Y in der zweiten Hälfte haben), ist das selten würde passieren.

Quelle

2017-07-04 01:24:42

Wie unterscheiden sich die verschiedenen Komprimierungsstufen von gzip?

Antwort

Verwandte Themen