Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Shannon-Fano

Huffman

Lempel-Ziv (LZ)

arithmetische Kodierung

Run Length Encoding

Burrows-Wheeler (BWT)

Enkodierung

transformierte Daten

Dekodierung

Eigenschaften

Anwendungen

Implementationen

Datenformate


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

Burrows-Wheeler-Transformation (BWT)


Die BWT ist nach Michael Burrows und David J. Wheeler benannt, die dieses Verfahren 1994 in ihrem Artikel "A Block-sorting Lossless Data Compression Algorithm" publiziert haben. Der zugrund liegende Algorithmus ist von David J. Wheeler 1983 entwickelt worden.


Prinzip des Algorithmus


Die Ausgangsdaten werden blockweise in eine bestimmte Form übertragen und anschließend sortiert. Als Ergebnis entstehen Daten, in denen sich häufig auftretende Symbolkombinationen in Wiederholungen widerspiegeln.


Beispiel: transformierte Textdaten


Fischers·Fritze·fischte·frische·Fische.·Frische
·Fische·fischte·Fischers·Fritze.

                v
  ——————————————————————————————
  Burrows-Wheeler-Transformation
  ——————————————————————————————
                v

eeeee.esseesssssssshhthzthzhh··..·······ccccccc
crrFFFFffrrFfFFeerriiiiiiiihhiit


Beide Datenblöcke bestehen aus identischen Symbolen, nur die Anordnung differiert. Die transformierten Daten lassen sich jedoch wesentlich besser komprimieren, z.B. durch einen adaptiven Huffman-Kode oder mittels arithmetischer Kodierung.


Die Anzahl von Symbolen erhöht sich dabei geringfügig, da zusätzlich noch Informationen hinterlegt werden müssen, die zur Wiederherstellung der Ausgangsdaten erforderlich sind.


In der realen Anwendung ist die Anzahl von Symbolen in einem Block jedoch sehr groß und der zusätzliche Aufwand sehr gering. Eine typische Blockgröße beträgt 900 KByte.


 <   ^   > 

Huffman-Kodierung [Huffman-Kodierung]

adaptive Huffman-Kodierung [adaptive Huffman-Kodierung]

arithmetische Kodierung [arithmetische Kodierung]

Kompressionsverfahren Run Length Encoding (RLE) BWT: Enkodierung



Anzeigen:

Informations- und Kodierungstheorie