Burrows-Wheeler Transformation

Kategorisierung:	Kodierungen / buchstabenbasiert
Herkunft / Verwendung:	Dieses Verfahren wurde von Michael Burrows und David Wheeler 1994 entwickelt und sortiert eine Zeichenfolge so um, dass sie besser komprimierbar wird, als auch zum Ursprungstext zurückrechenbar ist, wobei sich nur eine Positionszahl gemerkt werden muss. Die Position wird mit dem Schlüsselzeichen (welches sonst nicht im Text vorkommen darf, z. B. das Pipe-Zeichen) im kodierten Text verankert.

Hinweise zur Eingabe

Die interne Sortierung erfolgt nach ASCII, Leer- und Satzzeichen liegen also vor Buchstaben. Um Kompatibilität zu anderen Sortierreihenfolgen zu gewährleisten, sollten nur Buchstaben (entweder alle groß oder alle klein) benutzt werden.

Auf Leerzeichen sollte verzichtet werden. Es ist gut möglich, dass die am Anfang oder Ende des Codes stehen und so übersehen werden. Besser, es werden Punkte oder Striche als Trennzeichen benutzt.

Ziel der Burrows-Wheeler-Transformation

Eine Art, Datenkompression durchzuführen - also einen Text kleiner zu speichern, als er eigentlich ist - ist es, den Aufbau zu beschreiben. Z. B. könnte man die Zahl 5555566666633388888888 auch mit folgender Beschreibung ausdrücken: 5 mal die 5, 6 mal die 6, 3 mal die 3, 8 mal die 8 oder noch kürzer: 55663388 Und schon hat man jede Menge Platz gespart (wenn man sicher ist, dass nur Ziffern vorkommen und nicht mehr als jeweils 9 hintereinanderstehen).

Für Textdokumnte, also Buchstaben versucht man diese so zu sortieren, dass möglichst viele gleiche hintereinander stehen, um eine solche Beschreibungsweise anwenden zu können. Dabei ist die Crux, dass man auch irgendwie wieder zum Ursprungstext zurückkommen muss. Würde man einfach alles alphabetisch sortieren, hätte man zwar eine schöne Häufung von gleichen Buchstaben hintereinander, käme aber nicht mehr auf den Ursprungstext.

Den Spagat leistet die Burrows-Wheeler-Transformation. Der Code ist zurückrechenbar und stellt eine gewisse Buchstabenhäufung dar.

Aus unserem Beispiel wenn-fliegen-hinter-fliegen-fliegen-fliegen-fliegen-fliegen-nach (64) wird rnnnnnnnnaiiiiiiggggggwt------eeeeee-cllllllhffffffeeeneee-eien|h (65) was man auch beschreiben könnte als rn7ai5g5wt-5e5-cl5hf5e2ne2-eien|h (33) was nur noch etwa die Hälfte ist. Zur Erklärung: Ziffern in der Beschreibung geben an, wie oft das vorherige Zeichen wiederholt wird.

Erklärung des Algorithmus

Dies soll anhand eines Beispieles erklärt werden

Kodierung

HELENE --> NHL|EEE Zuerst wird eine Tabelle erstellt, in der alle Permutationen des Wortes vorkommen:

HELENE *
EHELEN
NEHELE
ENEHEL
LENEHE
ELENEH

Diese wird dann zeilenweise alphabetisch sortiert:

EHELEN 
ELENEH 
ENEHEL 
HELENE *
LENEHE 
NEHELE

Nun werden die jeweils letzten Buchstaben der Zeilen notiert: NHLEEE und an die 4. Stelle ein | eingefügt: NHL|EEE Denn in der 4. Zeile der sortierten Tabelle findet sich unsere Original wieder. Dies müssen wir speichern, um den Code zurückrechnen zu können.

Dekodierung

HELENE <-- NHL|EEE Zuerst wird das Schlüsselzeichen gesucht, sich die Position (4) gemerkt und dann entfernt: NHLEEE Die Buchstaben werden vertikal in die Tabelle geschrieben:

N
H
L
E
E
E

danach wird sie sortiert:

E
E
E
H
L
N

dies wird der Tabelle angehängt:

NE
HE
LE
EH
EL
EN

wieder sortiert

EH
EL
EN
HE
LE
NE

wieder wird die Tabelle durch die letzte Spalte erweitert

NEH
HEL
LEN
EHE
ELE
ENE

sortiert usw., bis die komplette ursprüngliche Tabelle rekonstruiert ist:

EHELEN
ELENEH
ENEHEL
HELENE *
LENEHE
NEHELE

Hier muss nur noch die 4. Zeile genommen werden, welche den Ursprungstext darstellt.

Beispiel

Klartext:	wenn-fliegen-hinter-fliegen-fliegen-fliegen-fliegen-fliegen-nach
Schlüssel:	\| (Pipe-Zeichen)
Kodiert:	rnnnnnnnnaiiiiiiggggggwt------eeeeee-cllllllhffffffeeeneee-eien\|h