Das Kefk Network Wiki befindet sich im Testbetrieb.

Aus Kefk.

Die Burrows-Wheeler-Transformation (BWT) bezeichnet einen Algorithmus, welcher in Datenkompressionstechniken wie bzip2 Anwendung findet. Er wurde von Michael Burrows und David Wheeler entwickelt.

Verfahren

Wenn eine Zeichenkette durch BWT umgeformt wird, bleiben alle Zeichen erhalten – der Algorithmus verändert lediglich die Anordnung der Zeichen. Kommen in der ursprünglichen Zeichenkette mehrmals identische Zeichenfolgen vor, so wird die erzeugte Kette mehrere Stellen enthalten, an denen sich ein einzelnes Zeichen wiederholt. Dieses Verfahren ist bei einer Kompression nützlich, da es leichter ist, eine Zeichenkette mit mehreren, sich wiederholenden Zeichen durch Techniken wie die Lauflängenkodierung zu komprimieren.

Zum Beispiel wird die folgende Zeichenkette SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES in eine Zeichenkette umgewandelt*, welche aufgrund ihrer sich wiederholenden Zeichen einfacher zu komprimieren ist: TEXYDST.E.XIIXIXXSMPPSS.B...S.EEUSFXDIOIIIIT

Die Transformation erfolgt, indem alle Rotationen des Textes sortiert und anschließend die letzte Spalte genommen wird. Der Text „.ANANAS.“ wird z. B. durch folgende Schritte in „.NNAAA.S“ umgewandelt:

.ANANAS.

.ANANAS.
..ANANAS
S..ANANA
AS..ANAN
NAS..ANA
ANAS..AN
NANAS..A
ANANAS..

ANANAS..
ANAS..AN
AS..ANAN
NANAS..A
NAS..ANA
S..ANANA
.ANANAS.
..ANANAS

.NNAAA.S

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)
   create a list of all possible rotations of s
   let each rotation be one row in a large, square table
   sort the rows of the table alphabetically, treating each row as a string
   return the last (rightmost) column of the table

 function inverseBWT (string s)
   create an empty table with no rows or columns
   repeat length(s) times
       insert s as a new column down the left side of the table
       sort the rows of the table alphabetically
   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 obigen Beispiel Punkte an Start und Ende) auffinden.

Durch eine Reihe von Optimierungen können diese Algorithmen effizienter laufen, ohne die Ausgabe zu ändern. Im BWT-Algorithmus ist es nicht nötig, die Tabelle zu speichern. Jede Reihe der Tabelle kann durch einen einzelnen Zeiger auf die jeweilige Zeichenkette repräsentiert werden. Bei der Umkehrung muss weder die Tabelle gespeichert, noch müssen die mehrfachen Sortierungen durchlaufen werden. Es genügt, die Zeichenkette s einmalig mit einem stabilen Sortierverfahren zu sortieren und zu vermerken, wohin sich jedes Zeichen bewegt hat. Dadurch erhält man eine single-cycle permutation, whose cycle is the output. Ein Zeichen im Algorithmus kann ein Byte, ein Bit oder eine andere passende Größe sein.

Es ist noch nicht einmal nötig, eine Endmarkierung zu besitzen: Stattdessen kann ein Zeiger verwendet werden, der sich „merkt“, wo in der Zeichenkette die Endmarkierung wäre. Auf diese Weise müsste die Ausgabe der BWT sowohl die umgeformte Zeichenkette, als auch den Wert des Zeigers enthalten. Dies bedeutet, dass die BWT ihre Eingabe leicht vergrößert. Die umgekehrte Transformation verkleinert diese jedoch wieder auf ihre Originalgröße: Ihr wird eine Zeichenkette und ein Zeiger übergeben, worauf sie nur eine Zeichenkette liefert.

Eine komplette Beschreibung der Algorithmen kann in Burrows und Wheelers Veröffentlichung oder einer Zahl von Onlinequellen gefunden werden.

Bemerkungen zur Sortierung

Mit einer POSIX-Sortierung erhält man einen leicht anderen String

TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT

statt

TEXYDST.E.XIIXIXXSMPPSS.B...S.EEUSFXDIOIIIIT

ISO 8859 hat komplexe Zuordnungsregeln, ignoriert aber Punkte. Posix-Zuordnung behandelt Punkte wie sonstige Zeichen (z. B. Buchstaben).

Die genaue Art der Sortierung spielt allerdings keine Rolle, so lange die Transformation und die Rücktransformation mit dem gleichen Sortierverfahren arbeiten.

Warum funktioniert diese Transformation?

Der Grund, warum diese Transformation funktioniert erschließt sich, wenn man mit etwas Abstand auf den Algorithmus sieht. Dann kann man folgendes beobachten:

• zuerst werden alle Teilstrings der zu kodierenden Zeichenkette erzeugt (die zyklische Betrachtung der Zeichenkette hat dabei nur eine kleine Auswirkung auf das Ergebnis, da der Algorithmus erst bei großen Datenmengen effizient arbeitet)
• diese Teilstrings werden sortiert
• dann wird jeweils das Zeichen vor den sortierten Teilstrings ausgegeben

Zeichen haben vor bestimmten Zeichenketten aber eine gute Vorhersehbarkeit. Z. B wird in einem deutschen Text vor einem großen Buchstaben oft ein Leerzeichen stehen. Genauso ist die Wahrscheinlichkeit für ein ‚q‘ vor einem ‚u‘ viel größer als vor einem ‚w‘. Da aber durch die Sortierung alle Teilstrings mit einem ‚u‘ am Anfang aufeinander folgen, sind auch viele der ‚q‘s an einer Stelle konzentriert in der Ausgabe.

Beispiel

Hier ein Beispiel – „Wikipedia!“

(0) Wikipedia! -> !Wikipedi[a]
(1) ikipedia!W    a!Wikiped[i]
(2) kipedia!Wi    dia!Wikip[e]
(3) ipedia!Wik    edia!Wiki[p]
(4) pedia!Wiki    ia!Wikipe[d]
(5) edia!Wikip    ikipedia![W] <- "Wikipedia!" << "ikipedia!W"
(6) dia!Wikipe    ipedia!Wi[k]
(7) ia!Wikiped    kipedia!W[i]
(8) a!Wikipedi    pedia!Wik[i]
(9) !Wikipedia    Wikipedia[!]

Den Startindex erhält man, in dem man das Original einmal nach links rotiert, und dann in der sortierten Liste nach diesem Eintrag sucht. in diesem Fall Index 5. Enkodiert heißt es also „aiepdWkii!“, 5. Dieser Text hat ein Verhältnis von „!adeikpW“ = 1:1:1:3:1:1:1.

Jetzt müssen wir den Text zum dekodieren sortieren: „aiepdkWkii!“ → „!adeiiikpW“, denn daraus lässt sich der Transformationsvektor errechnen. Man geht jedes Zeichen vom sortierten Text durch, und sucht dieses im Unsortierten. Der Index im unsortierten Text wird im Vektor gesichert, und das Zeichen im unsortierten Text „gelöscht“:

 0   1   2   3   4   5   6   7   8   9
---------------------------------------
 a   i   e   p   d   W   k   i   i  [!]
[!]  a   d   e   i   i   i   k   p   W
---------------------------------------
[9]

 0   1   2   3   4   5   6   7   8   9
---------------------------------------
[a]  i   e   p   d   W   k   i   i
 !  [a]  d   e   i   i   i   k   p   W
---------------------------------------
 9   0

 0   1   2   3   4   5   6   7   8   9
---------------------------------------
     i   e   p  [d]  W   k   i   i
 !   a  [d]  e   i   i   i   k   p   W
---------------------------------------
 9   0  [4]

...

 0   1   2   3   4   5   6   7   8   9
---------------------------------------
                    [W]
 !   a   d   e   i   i   i   k   p  [W]
---------------------------------------
 9   0   4   2   1   7   8   6   3  [5]

Der Transformationsvektor lautet demzufolge „9042178635“.

Startindex I ist 5
L = „aiepdWkii!“
F = „!adeiiikpW“
T = „9042178635“

             I = 5
L(5) = [W] | I = T(5)
L(7) = [i] | I = T(7)
L(6) = [k] | I = T(6)
L(8) = [i] | I = T(8)
L(3) = [p] | I = T(3)
L(2) = [e] | I = T(2)
L(4) = [d] | I = T(4)
L(1) = [i] | I = T(1)
L(0) = [a] | I = T(0)
L(9) = [!]

Decodiert lautet das ganze wieder „Wikipedia!“.

Siehe auch

Move-to-Front

Literatur

• M. Burrows and D. Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994.

Weblinks

• ResearchIndex page for BWT paper at Penn State
• ResearchIndex page for BWT paper at NEC
• BWT paper hosted at DEC
• Article by Mark Nelson on the BWT
• Perl Script

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Burrows-Wheeler-Transformation, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.