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.