Deflate

Deflate (englisch für „die Luft herauslassen“) ist ein Algorithmus zur verlustlosen Datenkompression. Er wurde von Phil Katz für das ZIP-Archivformat entwickelt und im Jahr 1989 der Gemeinfreiheit zugeführt.

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 erfolgversprechender 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 Kibibyte 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 zugunsten der Geschwindigkeit auf eine sehr gute Datenreduktion verzichtet werden. 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.

Komprimierung wird in zwei Schritten erreicht:

1. Finden und Ersetzen von doppelten Zeichenketten mit Verweisen.
2. Ersetzen von Symbolen (Zeichen) durch zum Teil kürzere, nach der Häufigkeit des Auftretens gewichtete Symbole.

Bitstromformat

Ein Deflate-Datenstrom (Stream) besteht aus einer Folge von Blöcken. Jedem Block ist ein 3-Bit-Header vorangestellt:

• 1 Bit: Marker für den letzten Block im Datenstrom:
  • 1: Das ist der letzte Block im Strom.
  • 0: Es folgen noch weitere Blöcke.
• 2 Bits: Kodierungsmethode für diesen Block:
  • 00: ein Literal-Abschnitt, der zwischen 0 und 65.535 Bytes lang ist.
  • 01: ein komprimierter Block, der einen vordefinierten statischen Huffman-Baum verwendet.
  • 10: komprimierter Block, mit eigenem Huffman-Baum.
  • 11: Reserviert, zurzeit nicht verwendet.

Die meisten Blöcke werden mit 10, der dynamic-Huffman-Methode kodiert. Diese erzeugt für jeden Block einen individuell optimierten Huffman-Baum. Anweisungen, den nötigen Huffman-Baum aufzubauen, folgen unmittelbar an den Blockheader.

Eliminierung doppelter Zeichenketten

→ Hauptartikel: LZ77 und LZ78

Wird innerhalb eines zu komprimierenden Blocks eine Folge sich wiederholender Bytes (entspricht einer sich wiederholenden Zeichenkette) gefunden, wird diese mit einer Rückwärtsreferenz ersetzt. Diese zeigt auf ein vorheriges Vorkommen der Zeichenkette. Ein Treffer auf eine vorherige Zeichenkette besteht aus Länge (3 bis 258 Bytes) und einer Distanz (1 bis 32.768 Bytes). Diese Rückwärtsreferenz kann sich über beliebig viele Blöcke erstrecken, muss aber innerhalb der Distanz von 32 KiB innerhalb der bereits dekomprimierten Daten (also innerhalb des sliding window) liegen.

Bitreduktion

→ Hauptartikel: Huffman-Kodierung

Die zweite Phase der Komprimierung besteht aus dem Ersetzen häufig genutzter Symbole (Zeichen) durch kürzere Darstellungsformen und seltenerer Symbole (Zeichen) durch Darstellungsformen, die geringfügig mehr Platz benötigen. Diese Methode der Huffman-Kodierung erzeugt einen präfixlosen Baum mit sich nicht überlappenden Abständen, in dem die Länge jeder Bitfolge umgekehrt proportional zu der Wahrscheinlichkeit des Auftretens des jeweiligen Symbols steht: Je häufiger ein Symbol auftritt, desto kürzer lässt sich dessen Bitfolge zum Kodieren darstellen.

Es wird ein Baum erzeugt, der für 288 Symbole Platz bietet:

• 0 bis 255: repräsentiert ein Literal/Symbol 0 bis 255.
• 256: Ende des Blocks – stoppt die Abarbeitung, wenn es sich um den letzten Block handelt, sonst wird die Verarbeitung mit dem nächsten Block fortgesetzt.
• 257 bis 285: kombiniert mit Extra-Bits einen Treffer mit 3 bis 258 Bytes.
• 286 bis 287: nicht verwendet, reserviert und ungültig, aber trotzdem Teil des Baumes.

Der Trefferlänge folgt immer die Distanz. Abhängig vom Code werden möglicherweise weitere extra Bits gelesen, um die endgültige Distanz zu ermitteln. Der Distanzbaum besteht aus 32 Symbolen:

• 0 bis 3: Entfernung 1 bis 4
• 4 bis 5: Entfernung 5 bis 8, 1 Extra-Bit
• 6 bis 7: Entfernung 9 bis 16, 2 Extra-Bits
• 8 bis 9: Entfernung 17 bis 32, 3 Extra-Bits
• …
• 26 bis 27: Entfernung 8.193 bis 16.384, 12 Extra-Bits
• 28 bis 29: Entfernung 16.385 bis 32.768, 13 Extra-Bits
• 30 bis 31: nicht verwendet, reserviert und ungültig, aber trotzdem Teil des Baumes.

Man beachte, dass für die Symbole 2 bis 29 die Anzahl der Extra-Bits wie folgt berechnet werden kann: $\left\lfloor {\frac {n}{2}}-1\right\rfloor$.

Deflate64/Enhanced Deflate

Deflate64 ist eine proprietäre Variante des Deflate-Algorithmus. Der zugrundeliegende Mechanismus bleibt unverändert. Einzige Veränderungen sind:

• Erweiterung des Wörterbuchs von 32 KiB auf 64 KiB.
• Erweiterung des Distanzbaums: Die bei Deflate für zukünftige Verwendung reservierten Distanzsymbole 30 und 31 im Distanzbaum werden jetzt mit je 14 Extra-Bits belegt, um Entfernungen von 32 KiB bis 64 KiB adressieren zu können.
• Erweiterung des Symbolbaums: Das Symbol 285 wird um 16 Extra-Bits erweitert. Damit wird die ursprüngliche Limitierung auf 258 Byte hinfällig und es können Sequenzlängen im Bereich von 3 bis 65.538 Bytes adressiert werden.

Im Vergleich zu Deflate verbessert sich bei Deflate64 die Kompressionsrate geringfügig. Gleichzeitig dauert die Komprimierung aber auch etwas länger.

Neben PKZIP und einer Vielzahl kommerzieller Anwendungen unterstützen auch viele Open-Source-Projekte wie zum Beispiel 7-Zip oder Info-ZIP Deflate64.

Zlib unterstützt Deflate64 nicht. Grund ist die zu geringe Gesamtverbesserung und die Entscheidung, Deflate64 als proprietäres Format zu behandeln.

Verwendung

Deflate wird unter anderem in folgenden gebräuchlichen Formaten benutzt:

• im Archivformat ZIP,
• gzip-Dateien,
• dem Bilddateiformat PNG,
• dem Bilddateiformat TIFF,
• in OpenDocument, dem ISO-Standardformat für Office-Dateien,
• dem Portable Document Format (PDF),
• dem Web Open Font Format und
• dem Archivformat CAB.

Es ist das gebräuchliche Verfahren für komprimierte HTTP-Übertragungen, siehe Artikel Hypertext Transfer Protocol, Abschnitt HTTP-Kompression.

Implementierungen

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. Die historische erste Implementierung erfolgte in Phil Katz’ PKZIP. Es existiert eine Vielzahl weiterer Implementierungen in einer Reihe unterschiedlicher Programmiersprachen, namentlich unter anderem in Java, Ada, Pascal, JavaScript und Seed7, oder mit anderen Spezialisierungen. 7-Zip enthält eine eigene Implementierung, die für die Einführung einer stärkeren, rechenintensiveren Kompressionsstufe bekannt wurde. KZIP von Ken Silverman ist eine spezialisierte eigene Implementierung, die auf kleinstmögliche Dateigrößen zielt und einige Zeit als das beste verfügbare Werkzeug für diese Nische galt. Die freie Referenzimplementierung des Zopfli-Algorithmus komprimiert üblicherweise noch kompakter.

Geschichte

Katz implementierte nach Vorbild von LHA den 1982 veröffentlichten Lempel-Ziv-Storer-Szymanski-Algorithmus, der eine Verbesserung gegenüber dem alten Lempel-Ziv-Algorithmus von 1977 darstellte. Deflate wurde 1993 mit Version 2 der Software PKZIP von Phil Katz’ Firma PKWare Inc. eingeführt. Die exakte Spezifikation von Deflate und dem zugehörigen Bitstrom-Format ist im RFC 1951 vom Mai 1996 festgehalten.

Weblinks

• P. Deutsch: RFC 1951 – DEFLATE Compressed Data Format Specification version 1.3. Mai 1996 (englisch).
• Detaillierte Erläuterung des Algorithmus. zlib.net (englisch)
• Beispiel-Implementierung in C sowie Veranschaulichung eines Datenblocks. m-einfalt.de