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 nach Vorbild von LHA den Lempel-Ziv-Storer-Szymanski-Algorithmus, der eine Verbesserung gegenüber dem alten Lempel-Ziv-Algorithmus von 1977 darstellte.
Beschreibung
Bei Deflate handelt es sich um eine Kombination des Lempel-Ziv-Storer-Szymanski-Algorithmus und der Huffman-Kodierung.
LZSS ersetzt dabei Zeichenfolgen, die mehrmals vorkommen. Danach erfolgt eine Entropiekodierung nach Huffman.
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.
Verwendung
Deflate wird unter anderem in folgenden Formaten und Bibliotheken benutzt:
- in dem Archivformat ZIP,
- dem Archivprogramm gzip,
- dem Bilddateiformat PNG,
- dem Bilddateiformat TIFF,
- dem Portable Document Format (PDF) und
- dem Archivformat CAB.
Die freie Programmbibliothek zlib abstrahiert die Benutzung von Deflate für die Verwendung in anderen Programmen. Über 500 Programme benutzen den Algorithmus auf diesem Wege.[1]
Die exakte Spezifikation von Deflate und dem zugehörigen Bitstrom-Format ist im RFC 1951 vom Mai 1996 festgehalten.
Weblinks
- RFC 1951 DEFLATE Compressed Data Format Specification version 1.3 (englisch)