01 Was ist die Burrows-Wheeler Transformation?

Burrows-Wheeler-Transformation – Wikipedia

Die Burrows-Wheeler-Transformation (BWT) ist ein Verfahren, das in Datenkompressionstechniken wie bzip2 Anwendung findet, dabei allerdings selbst keine Datenkompression durchführt.

Die Transformation wurde von Michael Burrows und David Wheeler 1994 entwickelt.

BWT erzeugt aus einem Block Daten (Eingabe) einen gleich großen Block Daten (Ausgabe) sowie eine kleine Zusatzinformation (einen Index). Die Ausgabe ist eine Permutation der Eingabe, das heißt, die Zeichenhäufigkeit von Ein- und Ausgabe ist gleich, nur die Reihenfolge kann sich ändern.

Da bei der Ausgabe gleiche Zeichen häufiger hintereinander stehen als in der Eingabe lässt sich diese im Allgemeinen besser komprimieren.

Aus den Ausgabedaten und dem Index kann man die Eingabedaten wiederherstellen, also die Transformation umkehren.