====== 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 [[wp>DEFLATE]] statt, das von [[wp>Phil Katz]] 1989 für sein DOS Tool [[wp>PKZIP]] entwickelt wurde. 

===== Funktionsweise =====


{{ :faecher:informatik:oberstufe:codierung:zip:zip.drawio.png |}}

Die Eingabedaten werden zunächst mit einem Vorläufer des LZW-Verfahrens bearbeitet ([[wp>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 [[http://www.infinitepartitions.com/art001.html|ausführliche Erläuterung findet sich hier]] ({{ :faecher:informatik:oberstufe:codierung:zip:zip.pdf |}}).

DEFLATE findet sich unter anderem in folgenden Programmen wieder: 

  * PKZIP: Ursprüngliche Implementation, implementiert von [[wp>Phil Katz]] als Teil von [[wp>PKZip]]
  * zlib: Standars Referenzimplementation, aufgrund der FOSS Lizenz findetr sich die [[wp>zlib]] in zahlreichen Anwendungen wieder. 
  * [[wp>zlib-ng]]: Schnellerer Fork der zlib, verwendet besondere Fähigkeiten moderner CPUs.
  * Crypto++: Enthält eine Public Domain Implementation in C++. 
  * [[wp>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 [[wp>Simon Tatham]].
  * [[wp>Zopfli]]: Eine C Implementation unter der Apache License von Google. Erreicht höchste Kompressionsraten auf Kosten der CPU Last.