Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Shannon-Fano

Huffman

Lempel-Ziv (LZ)

arithmetische Kodierung

Run Length Encoding

Burrows-Wheeler (BWT)

Implementationen

Deflate

Basisalgorithmus

Datenstruktur

Huffman-Kodebäume

Daten und Längen

Distanzen

Statisch u. Dynamisch

Deflate64™

Datenformate


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

Deflate: Statische und dynamische Kodebäume


Beide Kodebäume können sowohl statisch aus dem im Kodierer hinterlegten Standardparametern oder dynamisch anhand der jeweiligen Headerdaten gewonnen werden.


Das Deflate-Verfahren benutzt ein spezielles Format um Huffman-Bäume zu speichern. Anstelle von Wahrscheinlichkeiten oder der kompletten Baumstruktur, wird lediglich die Länge der einzelnen Kodes gespeichert. Allerdings erfordert dies zusätzliche Festlegungen, um sicherzustellen, dass alle Applikationen identische Kodebäume erstellen.


Allen Symbolen wird eine feste Reihenfolge zugeordnet, die bei gleicher Kodelänge ausgewertet wird. Niederwertigen Symbolen wird immer der linke Zweig zugeordnet (binär 0).


Symbole mit einer kürzen Kodelänge wird ebenfalls der linke Zweig zugeordnet (binär 0).


Außerdem ist die maximale Kodelänge auf 15 Bit begrenzt. Diese muss angepasst werden, sofern die Wahrscheinlichkeitverteilung einen größeren Wert ergibt. Der minimale Wert ist 0, d.h. dieses Symbol tritt im aktuellen Block gar nicht auf.


Die Informationen über die Kodelängen werden ebenfalls mit Hilfe eines Huffman-Baums kodiert, der statisch in den Kodierern hinterlegt ist. Dieser Kodebaum enthält zusätzlich Steuerzeichen, die Wiederholungen identifizieren. Damit wird eine einfache Lauflängenkodierung (RLE) etabliert.


 <   ^   > 

Deflate Deflate: Kodebaum für Distanzen Deflate64™ (Enhanced Deflate)



Anzeigen:

Informations- und Kodierungstheorie