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 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 Verweisen.
  • 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 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 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 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[Bearbeiten]

Deflate64 ist eine proprietäre Variante des Deflate-Algorithmus. Der zugrundeliegende Mechanismus bleibt unverändert.[1]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. Gleichzeit dauert die Komprimierung aber auch etwas länger.

Neben PKZip und einer Vielzahl kommerzieller Anwendungen unterstützen auch viele Open-Source-Projekte wie z. B. 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[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.[2]

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. Binary Essence - Deflate64
  2. http://zlib.net/apps.html