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: Datenstruktur


Deflate gliedert die Daten in Blöcke, denen jeweils eine bestimmte Form der Kodierung zugeordnet werden kann. Diese muss innerhalb des Blockes unverändert bleiben.


Typ Kodierung
unkomprimiert Die Originaldaten werden unverändert übernommen. Der Block wird durch einen Header eingeleitet, der die Blockgröße spezifiziert. Die maximale Größe ist auf 64 KByte begrenzt.
komprimiert
statischer
Huffman-Kode
Die Daten werden nach dem zuvor skizzierten Schema Huffman-kodiert. Dazu wird ein statischer Standardkode verwendet, dessen Struktur sowohl im Enkoder als auch im Dekoder hinterlegt ist. In den eigentlichen Daten sind nur die Kodes enthalten.
komprimiert
dynamischer
Huffman-Kode
Die Daten werden mit einem individuell definierten Huffman-Baum kodiert. Dazu werden bei jedem Block dieses Typs im Header zwei Huffman-Kodes mit übertragen, jeweils einer zur Kodierung von Daten bzw. Längen und ein zweiter für die Kodierung der Distanzen.


Die beiden Datenblöcke, die komprimierte Daten aufnehmen, sind von ihrer Größe her nicht begrenzt. Das Ende des jeweiligen Blocks wird über ein zusätzliches Steuerzeichen signalisiert.


Anordnung, Größe und Wiederholung der Blöcke liegt in der Hand des Enkoders und kann frei gestaltet werden. Deshalb kann die erzielbare Kompressionsrate je nach Enkoder auch bei identischen Ausgangsdaten schwanken.


 <   ^   > 

Deflate Deflate: Basisalgorithmus Deflate: Huffman-Kodebäume



Anzeigen:

Informations- und Kodierungstheorie