Deflate

Deflate ist ein Algorithmus zur verlustlosen Datenkompression. Er wurde von Phil Katz für das ZIP-Archivformat entwickelt und später der Public Domain zugeführt. Katz implementierte den Lempel-Ziv-Storer-Szymanski-Algorithmus, der eine Verbesserung gegenüber dem alten Lempel-Ziv-Algorithmus von 1977 darstellte (siehe LZ77-Datenkompression).

Bei Deflate handelt es sich um eine Kombination der Algorithmen LZ77 und Huffman-Kodierung.

LZ77 komprimiert dabei Zeichenfolgen, die mehrmals vorkommen. Danach komprimiert die Huffman-Kodierung das Resultat durch eine Entropiekodierung.

Es gibt eine Reihe von Parametern für Deflate, mit denen man Ausführungsgeschwindigkeit und Reduktionsrate beeinflussen kann:

Fenstergröße. Je größer das Datenfenster definiert wird, in dem Deflate nach bereits vorhandenen Zeichenketten sucht, desto erfolgsversprechender ist das Auffinden einer solchen Kette, aber desto länger braucht der Algorithmus auch zur Ausführung. Als Voreinstellung für die Fenstergröße werden meist 32 Kilobyte verwendet.
Suchintensität. Der Algorithmus kann das bereits erwähnte Fenster mehr oder weniger ausführlich durchsuchen. Wenn es etwa eher auf schnelle Ausführung ankommt, kann so auf eine sehr gute Datenreduktion verzichtet werden zugunsten der Geschwindigkeit. Im Programm gzip kann diese Eigenschaft über die Parameter -1 bis -9 vorgegeben werden: -1 ist am schnellsten, -9 ist am ausführlichsten.
Huffmantabellen. Diese können für die vorliegenden Daten ermittelt werden, oder es können Tabellen vorgegeben werden. Letzteres spart etwas Zeit, erzielt aber eventuell eine weniger gute Datenreduktion.

Deflate wird unter anderem in folgenden Formaten und Bibliotheken benutzt:

Die exakte Spezifikation von Deflate und dem zugehörigen Bitstrom-Format ist im RFC 1951 vom Mai 1996 festgehalten.

Gourt Home::Gourt :: Deflate