Deflate

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 später der Public Domain zugeführt.

Beschreibung[Bearbeiten]

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 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 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.

Bitstromformat[Bearbeiten]

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 bis 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, zur Zeit nicht verwendet.

Die meisten Blöcke werden sicher letztendlich 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.

Komprimierung wird in zwei Schritten erreicht:

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

Eliminierung doppelter Zeichenketten[Bearbeiten]

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–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 liegen, also innerhalb des sliding window liegen.

Bitreduktion[Bearbeiten]

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 der 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–255: repräsentiert ein Literal/Symbol 0–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–285: kombiniert mit Extra-Bits einen Treffer mit 3–258 Bytes.
  • 286–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–3: Entfernung 1–4
  • 4–5: Entfernung 5–8, 1 Extra-Bit
  • 6–7: Entfernung 9–16, 2 Extra-Bits
  • 8–9: Entfernung 17–32, 3 Extra-Bits
  • 26–27: Entfernung 8.193–16.384, 12 Extra-Bits
  • 28–29: Entfernung 16.385–32.768, 13 Extra-Bits
  • 30–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: \lfloor\frac{n}{2}-1\rfloor.

Verwendung[Bearbeiten]

Deflate wird unter anderem in folgenden Formaten und Bibliotheken benutzt:

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]

Geschichte[Bearbeiten]

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[Bearbeiten]

Quellen[Bearbeiten]

  1. http://zlib.net/apps.html