DEFLATIEREN

Deflate ist ein Datenkomprimierungsalgorithmus, der eine Kombination des LZ77-Algorithmus und der Huffman-Codierung verwendet. Er wurde ursprünglich von Phil Katz für Version 2 seines PKZIP-Archivierungswerkzeugs definiert und später in RFC 1951 spezifiziert. Der ursprüngliche Algorithmus, wie er von Katz entwickelt wurde, wurde als PKWARE patentiert und an PKWARE übertragen. Es wird allgemein angenommen, dass Deflate in einer Weise implementiert werden kann, die nicht durch Patente abgedeckt ist. Dies hat zu seiner weit verbreiteten Verwendung geführt, zum Beispiel in gzip-komprimierten Dateien, PNG-Bilddateien und dem ZIP-Dateiformat, für das Katz es ursprünglich entworfen hat. Stream-Format Ein Deflate-Stream besteht aus einer Reihe von Blöcken. Jedem Block ist ein 3-Bit-Header vorangestellt: Die meisten Blöcke werden mit der Methode codice_5, der “dynamischen Huffman” -Codierung, codiert, wodurch ein optimierter Huffman-Baum für jeden Datenblock individuell erstellt wird. Anweisungen zum Erzeugen des erforderlichen Huffman-Baums folgen unmittelbar auf den Blockkopf. Die Komprimierung erfolgt in zwei Schritten. Doppelte Saitenbeseitigung. Wenn in komprimierten Blöcken eine doppelte Reihe von Bytes entdeckt wird (eine wiederholte Zeichenfolge), wird eine Rückwärtsreferenz eingefügt, die stattdessen mit der vorherigen Position dieser identischen Zeichenfolge verknüpft wird. Eine verschlüsselte Übereinstimmung mit einer früheren Zeichenfolge besteht aus einer Länge (3 bis 258 Bytes) und einer Entfernung (1 bis 32,768 Bytes). Relative Rückverweise können für eine beliebige Anzahl von Blöcken erstellt werden, solange der Abstand innerhalb der letzten 32 kB der dekodierten unkomprimierten Daten (als “Schiebefenster” bezeichnet) angezeigt wird. Bit-Reduktion Die zweite Kompressionsstufe besteht darin, häufig verwendete Symbole durch kürzere Darstellungen und weniger häufig verwendete Symbole durch längere Darstellungen zu ersetzen. Die verwendete Methode ist die Huffman-Codierung, die einen nicht fixierten Baum von nicht überlappenden Intervallen erzeugt, wobei die Länge jeder Sequenz umgekehrt proportional zu der Wahrscheinlichkeit ist, dass dieses Symbol codiert werden muss. Je wahrscheinlicher ein Symbol codiert werden muss, desto kürzer ist seine Bitfolge. Es wird ein Baum erstellt, der Platz für 288 Symbole enthält: Auf einen Übereinstimmungslängencode folgt immer ein Entfernungscode. Basierend auf dem gelesenen Entfernungscode können weitere “zusätzliche” Bits gelesen werden, um die endgültige Entfernung zu erzeugen. Der Entfernungsbaum enthält Platz für 32 Symbole: Beachten Sie, dass für die Übereinstimmungsentfernungssymbole 2–29 die Anzahl der zusätzlichen Bits als Formel_1 berechnet werden kann. Encoder / Kompressor Während der Komprimierungsphase wählt der “Encoder” die Zeit, die für die Suche nach übereinstimmenden Zeichenketten benötigt wird. Die zlib / gzip-Referenzimplementierung ermöglicht es dem Benutzer, aus einer gleitenden Skala des wahrscheinlichen resultierenden Komprimierungsniveaus im Vergleich zur Codiergeschwindigkeit zu wählen. Die Optionen reichen von codice_8 (versuchen Sie nicht, zu komprimieren, nur unkomprimiert zu speichern) bis zu codice_9, das die maximale Kapazität der Referenzimplementierung in zlib / gzip darstellt. Es wurden andere Deflate-Encoder produziert, die alle einen kompatiblen Bitstrom erzeugen, der von jedem vorhandenen Deflate-Decoder dekomprimiert werden kann. Unterschiedliche Implementierungen erzeugen wahrscheinlich Variationen im endgültig erzeugten codierten Bitstrom. Bei Nicht-Zlib-Versionen eines Encoders lag der Fokus normalerweise auf der Erzeugung eines effizienteren komprimierten und kleineren codierten Streams. Deflate64 / Enhanced Deflate. Deflate64, von PKWare angegeben, ist eine proprietäre Variante der Deflate-Prozedur. Die fundamentalen Mechanismen bleiben gleich. Was sich geändert hat, ist die Zunahme der Wörterbuchgröße von 32 kB auf 64 kB, die Hinzufügung von 14 Bits zu den Entfernungscodes, so dass sie einen Bereich von 64 kB adressieren können, und der Längencode wurde um 16 Bits erweitert, sodass er die Länge von 3 bis 65538 Bytes. Dies führt dazu, dass Deflate64 ein etwas höheres Kompressionsverhältnis und eine etwas geringere Kompressionszeit als Deflate aufweist. Mehrere freie und / oder Open Source-Projekte unterstützen Deflate64, wie z. B. 7-Zip, während andere, wie zlib, aufgrund der proprietären Natur des Verfahrens und der sehr geringen Leistungssteigerung gegenüber Deflate nicht. Deflate in neuer Software verwenden. Implementierungen von Deflate sind in vielen Sprachen frei verfügbar. C-Programme verwenden normalerweise die zlib-Bibliothek (unter der alten BSD-Lizenz ohne Werbeklausel). Programme, die mit den Borland-Dialekten von Pascal geschrieben wurden, können paszlib verwenden1}

Leave a Comment