Deflate

Deflate

Deflate (engl. 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.

Inhaltsverzeichnis

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

Verwendung

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

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

  • RFC 1951 DEFLATE Compressed Data Format Specification version 1.3 (englisch)

Quellen

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

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • DEFLATE — redirects here. For other uses, see Deflation (disambiguation). Deflate is a lossless data compression algorithm that uses a combination of the LZ77 algorithm and Huffman coding. It was originally defined by Phil Katz for version 2 of his PKZIP… …   Wikipedia

  • Deflate — est un algorithme de compression de données sans pertes qui couple l algorithme LZ77 et le codage de Huffman. Il fut défini à l origine par Phil Katz pour la version 2 de son archiveur PKZIP, et fut plus tard défini dans la RFC 1951 et autres… …   Wikipédia en Français

  • DEFLATE — DEFLATE  это алгоритм сжатия без потерь, который использует комбинацию алгоритма LZ77 и алгоритма Хаффмана. Изначально он был описан Филом Кацом для 2 й версии своей утилиты для создания архивов PKZIP, который впоследствии был определён в… …   Википедия

  • deflate — de‧flate [ˌdiː fleɪt, ˌdɪ ] verb [intransitive, transitive] ECONOMICS 1. if a government deflates the economy, it reduces the demand for goods and services by raising interest rates and taxes, limiting wage increases, reducing government spending …   Financial and business terms

  • Deflate — Deflate  это алгоритм сжатия без потерь, который использует комбинацию алгоритма LZ77 и алгоритма Хаффмана. Изначально он был описан Филом Кацом для 2 й версии своей утилиты для создания архивов PKZIP, который впоследствии был определён в… …   Википедия

  • deflate — de*flate , v. t. [Pref. de down + L. flare, flatus to blow.] To reduce from an inflated condition; used literally and metaphorically; as, to deflate a tire; to deflate expectations. [1913 Webster +PJC] …   The Collaborative International Dictionary of English

  • deflate — [v1] reduce or cause to contract collapse, decrease, depreciate, depress, devalue, diminish, empty, exhaust, flatten, puncture, shrink, squash, void; concepts 236,247,776 Ant. blow up, expand, inflate deflate [v2] humiliate chasten, cut down to… …   New thesaurus

  • deflate — [dē flāt′, diflāt′] vt., vi. deflated, deflating [ DE + (IN)FLATE] 1. to collapse by letting out air or gas [to deflate a tire] 2. to make or become smaller or less important 3. to cause deflation of (currency, prices, etc.): Opposed to INFLATE …   English World dictionary

  • deflate — index attenuate, browbeat, debunk, decrease, deduct (reduce), demean (make lower), demote, denounce ( …   Law dictionary

  • déflaté — ● déflaté, déflatée adjectif Se dit d une grandeur corrigée de l inflation existante …   Encyclopédie Universelle

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”