Kompression: Von ZLIB bis LZMA

Ach die liebe ZLIB … nichts kommt ohne sie aus und immer noch hat sie den Speichermanager mit im Schlepptau um auch noch unter DOS mit 64 KByte auszukommen.

Die deflate Kompressionsmethode zählt zu den ältesten und am weit verbreitesten und ist die Basis des GZIP und ZIP Formats.

Da sie als OpenSource zur Verfügung gestellt wird, wird sie auch intern in vielen Produkten benutzt um Datenmengen zu verkleinern.

Doch im Laufe der Zeit wurden neuere Algorithmen entwickelt, die durchaus mit der alten ZLIB in Konkurrenz treten.

ZLIB, dein Freund und Helfer

Kompressionsalgorithmen gibt es viele, doch nicht alle sind frei zugänglich. Die ZLIB vereint ihren freien Zugang mit einer vernünftigen API und das waren schon vor über 10 Jahren die Gründe, diese Bibliothek einzusetzen.

Das Komprimieren läuft nach folgendem Schema ab

  1. Ein z_stream Struktur wird mit deflateInit2() initialisiert
  2. Wir stellen einen Eingabe- (unkomprimiert) und einen Ausgabe-Puffer (komprimiert) bereit
  3. In einer Schleife arbeiten wir folgenden Schritte ab:
    1. Wir lesen Daten aus der (unkomprimierten) Quelle Daten und schreiben sie in dein Eingabe-Puffer
    2. z_stream.avail_in wird auf Anzahl der verfügbaren Eingabe-Bytes gesetzt
    3. z_stream.next_in zeigt auf das erste Byte des Eingabe-Puffers
    4. z_stream.avail_out wird auf die Größe des Ausgabe-Puffers gesetzt
    5. z_stream.next_out zeigt auf das erste Byte im Ausgabe-Puffer
    6. Die Funktion deflate() mit `Z_NO_FLUSH wird aufgerufen, welche Daten aus dem Eingabe-Puffer liest und komprimierte Ergebnisse im Ausgabepuffer ablegt.
    7. Immer wenn z_stream.avail_in 0 wird, muss der Eingabe-Puffer aus der Quelle neu befüllt werden
    8. Den Ausgabe-Puffer kann man
      • entweder nach jedem Aufruf von deflate() in eine Datei schreiben und zurücksetzen
      • oder man wartet bis z_stream.avail_out 0 wird und schreibt dann den ganzen Block und setzt danach den Puffer wieder zurück.
    9. Wenn keine Eingabe Daten mehr vorhanden sind, folgen finale Aufrufe von deflate() mit Z_FINISH bis Z_STREAM_END zurückkommt.
  4. Mit deflateEnd() werden letzte Ressourcen freigegeben und parallel können die Quell- und Ziel-Dateien bzw. Quell- und Ziel-Ressourcen geschlossen werden.

Und das Dekomprimieren funktioniert ganz genau so, außer dass man hier die Funktionen inflateInit2(), inflate() und inflateEnd() nutzt.

So etwas nenne ich ein fast perfekte C-API. Der Anwender kann die Puffergrößen so große oder klein bestimmen wie er will und der Vorgang bietet durch seine iterative Art in jeder Umgebung die Möglichkeit Fortschrittswerte zwischendurch auszurechnen.

Im GATE Framework wird die ZLIB Implementierung durch eine gate_stream_t gekapselt. Ein Encoder-Stream stülpt sich bei der Erzeugung über einen Ausgabe-Stream.
Dann schaufelt man Daten aus einem Eingabe-Stream in den Encoder, der intern komprimiert und das Ergebnis an den Ausgabe-Stream weiterleitet.

Dekompression funktioniert auch so, nur wird hier der Decoder über den Eingabe-Stream gestülpt und beim Übertragen der Daten vom Decoder-Stream in den Ausgabe-Stream werden intern die Daten vom Eingabe-Stream gelesen, dekomprimiert und als Klartext nach außen geleitet.

Kurz gesagt: Ich bin ZLIB Fan.

Und wenn man ein paar Parameter in den Initialisierungsfunktionen setzt, bekommt man nicht nur die Rohdaten heraus, sondern das GZIP Format. Man kann also sagen GZIP = Header + deflate().

BZIP2

BZIP2 ist eine andere Kompressionsform, die oft ein bisschen bessere Ergebnisse liefert als die ZLIB, dafür braucht sie aber durchschnittlich wesentlich mehr Rechenkraft. Ein großer Vorteil ist, dass sie die ZLIB-API nachahmt und damit genau so wie ihr Vorbild funktioniert. Die Funktionen heißen dann einfach BZ2_bzCompressInit, BZ2_bzCompress, BZ2_bzCompressEnd bzw. BZ2_bzDecompressInit(), BZ2_bzDecompress, BZ2_bzDecompressEnd.

minizip

Wer das ZLIB-Source Paket genau ansieht, findet dort im contrib Ordner ein paar Dateien unter dem Namen minizip. Diese Bibliothek nutzt die ZLIB um klassische ZIP Dateien zu erzeugen, denn während GZIP und BZIP2 Dateien eigentlich nur eine einzige Datei beinhalten können, lässt das ZIP-Format mehrere Dateien mit Verzeichnisstruktur zu. Die einzelnen Dateien werden quasi hintereinander mit ein paar Header in die Datei gelegt. Man kann übrigens auch festlegen, dass die ZIP Datei nicht mit deflate() komprimiert, sondern mit BZIP2.

LZMA

Das OpenSource-Tool 7zip ist seit langem mein bevorzugtes Kompressionswerkzeug. Es beherrscht nämlich nicht nur eine Vielzahl von anderen Kompressionsroutinen (GZIP, BZIP, ACE, RAR, …), sondern legt auch noch sein eigenes “7zip” Format bei.

Die interne Kompression heißt LZMA bzw. LZMA2 und ist tatsächlich im Durchschnitt noch mal um einiges stärker in der Kompression im Vergleich zu den Vorgängern.

Und nachdem das LZMA-SDK als public domain ebenso frei verfügbar ist, können wir damit sehr einfach XZ Dateien erzeugen.
*.XZ Dateien sind das Äquivalent zu *.GZ, während
*.7Z Dateien das Äquivalent zu *.ZIP Dateien sind.

Daher ist das XZ Format (mit LZMA2) heute eine Alternative für das GZIP Format (mit deflate).

Die API ist leider nur halb so schön die jene der ZLIB. Denn das Dekomprimieren funktionert ähnlich wie oben geschildert und ist damit schön, doch die Kompression erfordert das Bereitstellen der Daten per Callback. Das bedeutet, dass die Kompression innerhalb einer blockierenden Funktion stattfindet … und das ist … naja, nicht so optimal.

However. Die Ergebnisse können sich sehen lassen und vor allem lassen sich die produzierten Datein problemlos auch mit 7zip oder anderen Tool nutzen.

Fazit

Für normale Kompressionanforderungen ist die ZLIB mein Favorit, vor allem weil sie mit wenig CPU und RAM-Bedarf sehr gute Ergebnisse bringt.

Wer aber mit vielen und großen Datenmengen arbeiten muss freut sich über jedes ersparte Byte und hier führt kein Weg an LZMA2 bzw. XZ vorbei. Der Speicherbedarf wie auch die CPU Nutzung ist oft ein Vielfaches im Vergleich zur ZLIB, doch das Ergebnis kann bis zu einem Drittel kleiner sein … Vor daher: Einfach genial!

Ach ja, die BZIP2 geht etwas unter und ich nutze sie nur als Support zum Lesen solcher Dateien … aber da sie qualitativ zwischen ZLIB und LZMA liegt und oft gleich viele Ressourcen wie LZMA aufbraucht, nutze ich sie nie zum Erzeugen neuer Dateien.

Und wer Daten mit anderen Menschen austauschen will, sollte bei ZIP (mit deflate) bleiben.
Denn dieses Format kann nun wirklich fast jedes Tool und OS lesen.


Wenn sich eine triviale Erkenntnis mit Dummheit in der Interpretation paart, dann gibt es in der Regel Kollateralschäden in der Anwendung.
frei zitiert nach A. Van der Bellen
... also dann paaren wir mal eine komplexe Erkenntnis mit Klugheit in der Interpretation!