Burrows Wheeler Transformation

Die Idee des von Burrows und Wheeler 1994 vorgeschlagenen Kompressionsverfahrens besteht darin, durch (spezielles) Sortieren des zu codierenden Textes eine Folge zu erhalten, die viel mehr Struktur als der Urtext enthält und somit effizient (mit Hilfe irgendeines anderen Verfahrens) verschlüsselbar ist. Um weiterhin verlustfrei zu übertragen, muss neben dem sortierten Text noch Zusatzinformation gesendet werden.

1 Aufwand

Der Aufwand BWT-basierter Kompression ist (mindestens) quadratisch.

2 Naiver Ansatz

Der folgende Pseudocode gibt ein (allerdings ineffizientes) Beispiel, wie die BWT und ihre Umkehrung zu berechnen ist. Es wird davon ausgegangen, dass es ein Sonderzeichen 'EOF' als Endmarkierung gibt, welches den Text abschließt, nirgendwo anders im Text vorkommt und während der Sortierung ignoriert wird.

function BWT (string s)
  1. create a list of all possible rotations of s
  2. let each rotation be one row in a large, square table
  3. sort the rows of the table alphabetically, treating each row as a string
  4. return the last (rightmost) column of the table

function inverseBWT (string s)
  1. create an empty table with no rows or columns
  2. repeat length(s) times
  3. insert s as a new column down the left side of the table
  4. sort the rows of the table alphabetically
  5. return the row that ends with the 'EOF' character
Das Bemerkenswerte ist nicht etwa, dass der Algorithmus eine einfache kodierte Ausgabe erzeugt – eine Reihe trivialer Operationen würde dies ebenfalls tun. Das Bemerkenswerte ist, dass der Algorithmus umkehrbar ist, der Originaltext also nur aus den Daten der letzten Spalte rekonstruierbar ist.

Zur Umkehrung wird dieselbe Tabelle wie oben verwendet, jedoch werden alle Spalten mit Ausnahme der letzten gelöscht. Durch die letzte Spalte sind alle Zeichen des Textes bekannt. Um die erste Spalte wiederherzustellen genügt es also, diese erneut zu sortieren. Die letzte vor die erste Spalte gesetzt, ergeben sich alle Zeichenpaare des Originaltextes. Sortiert man diese Liste, so ergeben sich die erste und zweite Spalte. Wiederholt man diese Schritte, so lässt sich die komplette Tabelle rekonstruieren. Anschließend lässt sich die Zeile mit dem Originaltext unter Kenntnis der Endmarkierungen (im folgenden Beispiel Punkte an Start und Ende) auffinden.

3 Beispiel

4 Applet

alt="Your browser understands the <APPLET> tag but isn't running the applet, for some reason." Your browser is completely ignoring the <APPLET> tag! Das Beispiel-Applet

Das Applet soll veranschaulichen, wie der oben genannte Algorithus abläuft.

Handhabung des Applets:

  1. 1. Setzen Sie den EingabeText
  2. 2. Encodieren Sie den eingegeben Text durch drücken des Buttons "Encode"
  3. 3. Die Einzelschritte der Encodierung werden im "Step" Fenster erscheinen
  4. 4. Decodieren Sie den eingegeben Text durch drücken des Buttons "Encode"
  5. 5. Die Einzelschritte der Decodierung werden im "Step" Fenster erscheinen
  6. 6. Sie können jederzeit das Applet durch drücken des Buttons "Reset" zurücksetzten

 

 

Entwickelt von Nadine Hassis und Rene Worzischek im Rahmen der Datenkommpressionsvorlesung der Universität Tübingen,2007.

Quellcode HTML & Java-Source.