Zip-Kompression/DEFLATE

Um unsere Übersicht zu den verlustfreien Kompressionsverahren abzuschließen, hier noch einige Informationen zum weit verbreiteten Zip-Format, das in unterschiedlichen Detailimplementationen in zahlreichen Programmen zum Einsatz kommt.

Die Kompression in den meisten Zip-Programmen finden mit DEFLATE statt, das von Phil Katz 1989 für sein DOS Tool PKZIP entwickelt wurde.

Funktionsweise

Die Eingabedaten werden zunächst mit einem Vorläufer des LZW-Verfahrens bearbeitet (LZ77)). LZ77 Funktioniert in Teilen ähnlich wie LZW, führt jedoch kein Wörterbuch sondern verweist auf frühere Vorkommen identischer Bitmuster. Das Ergebnis dieser Kompression wird dann mit einer Huffman-Codierung weiter verkleinert, einige Implementationen schließen zuletzt noch eine Lauflängencodierung an.

Eine sehr ausführliche Erläuterung findet sich hier (zip.pdf).

DEFLATE findet sich unter anderem in folgenden Programmen wieder:

PKZIP: Ursprüngliche Implementation, implementiert von Phil Katz als Teil von PKZip

zlib: Standars Referenzimplementation, aufgrund der FOSS Lizenz findetr sich die zlib in zahlreichen Anwendungen wieder.

zlib-ng: Schnellerer Fork der zlib, verwendet besondere Fähigkeiten moderner CPUs.

Crypto++: Enthält eine Public Domain Implementation in C++.

7-Zip: Geschrieben von Igor Pavlov in C++ steht diese Implementation unter einer freien Lizenz und erreich eine bessere Kompression als zlib, allerdings auf Kosten der Geschwindigkeit.

PuTTY implementiert in sshzlib.c DEFLATE unter einer MIT Lizenz (Autor Simon Tatham.

Zopfli: Eine C Implementation unter der Apache License von Google. Erreicht höchste Kompressionsraten auf Kosten der CPU Last.