imported>SchlurcherBot: Bot: http → https

2026-04-20T03:31:07Z

Bot: http → https

Neue Seite

'''Deflate''' ({{enS}} für „die Luft herauslassen“) ist ein [[Algorithmus]] zur verlustlosen [[Datenkompression]]. Er wurde von [[Phil Katz]] für das [[ZIP-Dateiformat|ZIP]]-Archivformat entwickelt und im Jahr 1989<ref>{{Internetquelle |url=https://brianlivingston.com/eweek/article2/0,4149,1257562,00.html |titel=PKZip Must Open Up |abruf=2023-12-13}}</ref> 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 [[David A. Huffman|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 [[Byte#Binärpräfixe|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:
# 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.

== 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:
** <code>1</code>: Das ist der letzte Block im Strom.
** <code>0</code>: Es folgen noch weitere Blöcke.
* 2 Bits: Kodierungsmethode für diesen Block:
** <code>00</code>: ein Literal-Abschnitt, der zwischen 0 und 65.535 Bytes lang ist.
** <code>01</code>: ein komprimierter Block, der einen vordefinierten statischen Huffman-Baum verwendet.
** <code>10</code>: komprimierter Block, mit eigenem Huffman-Baum.
** <code>11</code>: Reserviert, zurzeit nicht verwendet.

Die meisten Blöcke werden mit <code>10</code>, 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|LZ78}}

Wird innerhalb eines zu komprimierenden Blocks eine Folge sich wiederholender Bytes (entspricht einer sich wiederholenden Zeichenkette) gefunden, wird diese mit einer Rückwärts[[Referenz (Programmierung)|referenz]] 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[[Kibibyte| 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: <math>\left \lfloor\frac{n}{2}-1 \right \rfloor</math>.

=== Deflate64/Enhanced Deflate ===
Deflate64 ist eine proprietäre Variante des Deflate-Algorithmus. Der zugrundeliegende Mechanismus bleibt unverändert.<ref>{{Webarchiv |url=http://binaryessence.com/dct/imp/en000225.htm |text=Binary Essence – Deflate64 |wayback=20150207095225}}</ref> 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-Dateiformat|ZIP]],
* [[gzip]]-Dateien,
* dem Bilddateiformat [[Portable Network Graphics|PNG]],
* dem Bilddateiformat [[Tagged Image File Format|TIFF]],
* in [[OpenDocument]], dem ISO-Standardformat für Office-Dateien,
* dem [[Portable Document Format]] (PDF),
* dem [[Web Open Font Format]] und
* dem Archivformat [[CAB (Dateiformat)|CAB]].

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

=== Implementierungen ===
Die [[Freie Software|freie]] Programmbibliothek [[zlib]] abstrahiert die Benutzung von Deflate für die Verwendung in anderen Programmen. Über 500 Programme benutzen den Algorithmus auf diesem Wege.<ref>[https://zlib.net/apps.html zlib.net]</ref> 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,<ref>[http://www.jcraft.com/jzlib/ jcraft.com]</ref> Ada,<ref>[https://unzip-ada.sourceforge.net/ unzip-ada.sourceforge.net]</ref> Pascal,<ref>[https://www.seekxl.de/blog/the-nomssi-viewer/ seekxl.de]</ref> JavaScript<ref>[https://github.com/nodeca/pako github.com]</ref><ref>[http://gildas-lormeau.github.com/zip.js gildas-lormeau.github.com]/</ref> und Seed7,<ref>[https://seed7.sourceforge.net/libraries/deflate.htm seed7.sourceforge.net]</ref> 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 (Kompressionsprogramm)|LHA]] den 1982 veröffentlichten [[Lempel-Ziv-Storer-Szymanski-Algorithmus]], der eine Verbesserung gegenüber dem alten [[LZ77|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 <nowiki>RFC 1951</nowiki><ref>{{RFC-Internet |RFC=1951 |Titel=DEFLATE Compressed Data Format Specification version 1.3 |Datum=1996-05 |Autor=P. Deutsch}}</ref> vom Mai 1996 festgehalten.

== Weblinks ==
* {{RFC-Internet |Autor=P. Deutsch |RFC=1951 |Titel=DEFLATE Compressed Data Format Specification version 1.3 |Datum=1996-05}}
* [https://zlib.net/feldspar.html Detaillierte Erläuterung des Algorithmus.] zlib.net (englisch)
* [https://m-einfalt.de/?deflate Beispiel-Implementierung in C++ sowie Veranschaulichung eines Datenblocks.] m-einfalt.de

== Einzelnachweise ==
<references />

[[Kategorie:Freie Datenkompressionssoftware]]
[[Kategorie:Kompressionsalgorithmus]]

Deflate - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https