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 Zahl5555566666633388888888
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 werdenKodierung
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 |