# Burrows-Wheeler-Transformation

Die Burrows-Wheeler-Transformation (BWT) ist ein Algorithmus, der in Datenkompressionstechniken wie bzip2 Anwendung findet, dabei allerdings selbst keine Datenkompression durchführt. Die Transformation wurde von Michael Burrows und David Wheeler 1994 am DEC Systems Research Center (SRC) in Palo Alto entwickelt und basiert auf einer nicht veröffentlichten Transformation von Wheeler aus dem Jahr 1983.

## Eigenschaften

Die BWT ist eine umkehrbare Transformation, die aus einem Block von Eingabedaten einen gleich großen Block Ausgabedaten sowie eine wenige Bit große Zusatzinformation (einen Index) erzeugt. 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. Die Ausgabe lässt sich im Allgemeinen besser komprimieren, da gleiche Zeichen häufiger hintereinander stehen als in der Eingabe. Aus den Ausgabedaten und dem Index kann man die Eingabedaten wiederherstellen, also die Transformation umkehren.
Die Burrows-Wheeler-Transformation hängt von einer Reihe von Parametern ab:
* Der verwendete Zeichenvorrat: In den meisten Fällen wird die BWT auf Bytes mit 8 Bit angewendet.
* Die Zeichen müssen eine festgelegte Reihenfolge haben, also vollständig geordnet sein.
* Der Index, der als Ausgabe der BWT entsteht, kann 1-basiert oder 0-basiert sein.
Für die Vorwärts- und Rückwärtstransformationen müssen diese Parameter gleich sein.

## Vorwärtstransformation

Eingabe:
* die zu codierenden Daten
Ausgabe:
* die codierten Daten
* ein Index
Zuerst werden alle möglichen Rotationen der zu codierenden Daten erzeugt, indem jeweils ein Zeichen vom Ende der Daten an den Anfang verschoben wird. Alle diese Rotationen werden in eine Tabelle geschrieben. Diese Tabelle wird lexikographisch sortiert. Die jeweils letzten Zeichen jeder Zeile ergeben – von oben nach unten gelesen – den codierten Text. Der Index ist die Nummer der Zeile, in der die zu codierenden Daten in der Tabelle vorkommen.

### Prinzip

Die Effizienz der Burrows-Wheeler-Transformation beruht auf der Tatsache, dass in jeder Sprache bestimmte Wortteile / Silben üblicherweise nur mit einigen wenigen Buchstaben begonnen werden (z. B. (g)eg-angen, (g)eg-en, …). Durch die Sortierung der oben beschriebenen Tabelle werden solche Wortbestandteile gehäufelt. Da nun die letzte Spalte der Tabelle jeweils das Zeichen davor beinhaltet, häufen sich in der Ausgabe des Algorithmus stückchenweise eben immer die Zeichen, die das jeweilige Wort- / Textsegment am wahrscheinlichsten beginnen.
Zur Veranschaulichung dieses Effektes wird im Folgenden der Ausschnitt aus der sortierten Tabelle des transformierten Wikipedia-Artikels "Nebel" gezeigt (das erste Zeichen ist dabei immer die letzte Spalte der Tabelle, d. h. die Ausgabe):

### Beispielcode

Beispielcode in Lua:

### Optimierungsmöglichkeiten

Es ist nicht nötig, die gesamte Tabelle zu speichern, da alle Zeilen den gleichen Text beinhalten, nur an unterschiedlichen Stellen anfangen. Es reicht daher, den Text nur ein einziges Mal zu speichern. Jede Tabellenzeile besteht dann nur noch aus einem Zeiger auf den Start der Zeichenkette. Je größer der zu transformierende Datenblock wird, desto mehr lohnt sich diese Optimierung. Wenn man zum Beispiel 500 Kilobyte transformiert und jede Tabellenzeile für sich speichert, braucht man 500 000 Zeilen à 500.000 Byte, also 250 Gigabyte, nur um die Tabelle im Speicher unterzubringen. Benutzt man jedoch Zeiger, braucht man nur einmal 500.000 Byte für den Text und pro Zeile 4 Byte für den Zeiger (bei 32-Bit-Speicheradressen), also zusammen 2,5 Megabyte.

### Beispiel

Eingabe:
* Zu codierende Daten: „.ANANAS.“
    Zuerst werden alle Rotationen erzeugt und in eine Tabelle geschrieben:
    Dann wird diese Tabelle alphabetisch sortiert.
    (Bei diesem Beispielalphabet wird der Punkt am Ende einsortiert, bei einer Sortierung auf der Basis des ASCII-Codes wird der Punkt vor dem A einsortiert.)
    Die jeweils letzten Zeichen jeder Zeile werden hintereinandergeschrieben und ergeben den Ausgabetext.
    Der Eingabetext kommt in der 7. Zeile vor, deshalb ist der Index 7.
Ausgabe:
* Codierte Daten: „.NNAAA.S“
* Index: 7

## Rücktransformation

Eingabe:
* codierter Text
* ein Index
Ausgabe:
* uncodierter Text
Für die Rücktransformation gibt es mehrere Verfahren, die im Folgenden erläutert werden. Wenn man nur den codierten Text als Eingabe hat, kann man die Reihenfolge der Zeichen im uncodierten Text bestimmen. Das lässt aber immer noch so viele Möglichkeiten, wie der Text Zeichen hat. Damit die Umkehrung eindeutig wird, braucht man daher noch eine Zahl, die angibt, an welcher Stelle des codierten Textes der uncodierte anfängt. Diese Zahl kann aus dem Index berechnet werden.

### Originalverfahren

Um den Text zurückzutransformieren, wird der Text mit einem stabilen Sortierverfahren sortiert, und beim Sortieren wird darauf geachtet, welches Zeichen an welcher Position landet. Dadurch erhält man eine Zuordnung zwischen der codierten Position (in der letzten Zeile der Codierungstabelle) und der sortierten Position (in der ersten Zeile der Codierungstabelle). Diese Zuordnung ist eine Permutation mit nur einem Zyklus, das heißt, wenn man bei einer bestimmten Position anfängt, die Permutation zu durchlaufen, erreicht man alle Elemente einmal und landet erst dann wieder bei dieser Position. Genau das wird auch bei der Rücktransformation gemacht, denn bei diesem Durchlauf kommt man an allen Zeichen des Textes vorbei, in der Reihenfolge, wie sie vor der Vorwärtstransformation angeordnet waren. Dadurch, dass man beim Index anfängt, erhält man die Zeichen in genau der Reihenfolge, wie sie vor der Vorwärtstransformation angeordnet waren.

#### Beispielcode

Beispielcode in Lua:

#### Beispiel

Die Daten (Text: „a!iepdWkii“, Index: 2) sollen zurücktransformiert werden. Die Sortierreihenfolge ist: Ausrufezeichen, Großbuchstaben, Kleinbuchstaben (wie in ASCII).
Die Daten werden mit einem stabilen Sortierverfahren sortiert, und beim Sortieren wird darauf geachtet, welches Zeichen an welcher Position landet.
| codierter Text | a | ! | i | e | p | d | W | k | i | i |
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| sortierter Text | ! | W | a | d | e | i | i | i | k | p |
| sortierte Position | 2 | 7 | 1 | 6 | 4 | 3 | 9 | 10 | 8 | 5 |
Beispiel: Im codierten Text stand das große "W" an Position 7, nach dem Sortieren steht es an Position 2, zusammen mit der Information, dass es von Position 7 kommt. Das stabile Sortierverfahren ist wichtig, um die Reihenfolge der is nicht durcheinanderzubringen. In Zeile 2 stehen sie an den Positionen 3, 9 und 10, und in genau dieser Reihenfolge stehen sie auch in Zeile 3.
Die Zeile codierter Text wird nun nicht mehr benötigt. Um den Text zurückzutransformieren, fängt man bei dem Index, also 2, an. An Position 2 steht im sortierten Text ein W. Die Position des nächsten Zeichens ergibt sich aus der Zeile sortierte Position, also 7. Dort steht ein i, und es geht bei Position 9 weiter. Dort steht ein k, dann kommt 8 (i), 10 (p), 5 (e), 4 (d), 6 (i), 3 (a), 1 (!), 2 (der Index). Der Ursprungstext war also „Wikipedia!“.

#### Ausführlicheres Beispiel

Der Text „.NNAAA.S“ soll zurücktransformiert werden. In der sortierten Tabelle stand er in Zeile 7.
Aus diesen Daten lässt sich schrittweise die komplette sortierte Matrix rekonstruieren, und wenn das fertig ist, findet man in Zeile 7 den ursprünglichen Text.
Die erste Spalte der Matrix lässt sich ganz einfach rekonstruieren, denn sie enthält alle Zeichen des Textes, bloß sortiert:
Wenn man sich jetzt überlegt, dass in allen Zeilen der gleiche Text steht, nur rotiert, kann man nach und nach die Matrix vervollständigen. Zur besseren Übersicht kann man die letzte Spalte noch einmal vor die erste Spalte schreiben.
Man sieht jetzt, dass auf einen "." entweder ein "A" folgt (Zeile 1) oder ein weiterer "." (Zeile 7). Diese beiden Zeichen müssen also in Zeile 7 und 8 an der Stelle 2 (mit Fragezeichen markiert) stehen. Da, wie schon gesagt, die Matrix sortiert ist und das erste Zeichen in diesen Zeilen gleich ist, muss das "A" in Zeile 7 stehen und der Punkt in Zeile 8. Genauso verfährt man mit den anderen Zeichen: Man sucht alle Nachfolgezeichen, sortiert sie, und trägt sie von oben nach unten in die Zeilen ein, die mit diesem Zeichen aufhören. Damit erhält man die Spalte 2.
* Auf "A" folgen "N", "N" und "S", die kommen in Zeile 1, 2 und 3.
* Auf "N" folgen "A" und "A", die kommen in Zeile 4 und 5.
* Auf "S" folgt ".", der kommt in Zeile 6.
* Auf "." folgen "A" und ".", die kommen in Zeile 7 und 8.
Für die weiteren Spalten funktioniert dieses Verfahren leider nicht mehr. (Beispiel: Die Nachfolger von "A" sind "N", "N" und "S", und wenn man die von oben nach unten in die Zeilen, die mit "A" aufhören, einträgt, steht in Zeile 7 auf einmal ".AS____.", und das kann nicht stimmen.) Aber durch scharfes Hinsehen kann man erkennen, dass irgendwo in dem Wort die Zeichenfolge "S.." vorkommt (Zeile 8). Und es gibt nur eine Möglichkeit, diese Zeichenfolge fortzusetzen, nämlich mit "..A" (Zeile 7). Dann kommt ".AN" (Zeile 1), und nun gibt es das nächste Problem: Es könnte entweder Zeile 4 oder Zeile 5 kommen, denn beide enthalten die Zeichen "ANA". Aber auch für dieses Problem gibt es eine Lösung.
Wenn man sich beim Rekonstruieren der Spalte 2 merkt, aus welcher Zeile die Zeichen kommen und in welche sie eingesetzt werden, erhält man folgende Tabelle:
| Spalte 2 in Zeile … | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| … kommt aus Zeile … | 4 | 5 | 6 | 2 | 3 | 8 | 1 | 7 |
Diese Tabelle passt erstaunlich gut zu den Nachfolgern, die man durch scharfes Hinsehen ermitteln kann. Denn der Nachfolger von Zeile 8 ist Zeile 7, der Nachfolger von 7 ist 1, und das ist in der Tabelle genauso. Die Tabelle liefert auch die Antwort auf das Problem mit der Mehrdeutigkeit. Die richtige Reihenfolge der Zeilen kann man jetzt aus der Tabelle ablesen, indem man mit der 7 beginnt (das ist die Zeilennummer, in der der ursprüngliche Text stand) und die Zahl aus der unteren Zeile aufschreibt. Dann sucht man diese Zahl in der oberen Zeile und so weiter. Damit erhält man die Reihenfolge 1, 4, 2, 5, 3, 6, 8, 7.
Im letzten Schritt schaut man für jede dieser Zahlen nach, was in der letzten Spalte der entsprechenden Zeile steht. In Zeile 1 ist das ein ".", in Zeile 4 ein "A", in Zeile 2 ein "N", und wenn man alle diese Zeichen aneinanderhängt, erhält man den Text ".ANANAS.".

### Alternatives Verfahren

Dieses Verfahren ist rechenaufwändiger als das Originalverfahren und deshalb eher zur Demonstration geeignet als zur Umsetzung in Computerprogrammen. Es basiert auf der Idee, ausgehend von dem codierten Text, der in der Tabelle der Vorwärtstransformation in der letzten Spalte stand, alle anderen Spalten schrittweise zu rekonstruieren. Wenn dieses Ziel erreicht ist, kann man in der Zeile, die der Index angibt, den zurückcodierten Text ablesen.
* Führe die folgenden Schritte aus, bis die Tabelle voll ist:
** Der codierte Text wird zeichenweise senkrecht in die letzte Spalte der Tabelle geschrieben.
** Die Tabelle wird dann um eine Position nach rechts rotiert, so dass die letzte Spalte zur ersten Spalte wird.
** Dann wird die Tabelle sortiert.
* Der Text in der Zeile Index ist der gesuchte, zurückcodierte Text.

#### Erläuterung

Die Tabelle, die bei der Vorwärtstransformation benutzt wird, hat eine wichtige Eigenschaft, die bei dieser Rückwärtstransformation ausgenutzt wird: Die Zeichen der letzten Spalte (und auch jeder anderen) kommen mit der gleichen Häufigkeit in der ersten Spalte der Tabelle vor, bloß sortiert. Das heißt, wenn die erste Spalte nicht bekannt ist, aber eine beliebige andere, kann man die erste Spalte daraus konstruieren.
Nach dem Füllen der letzten Spalte (Schritt 1.1) entspricht der bereits ausgefüllte Teil der Tabelle derjenigen, die auch schon für die Vorwärtstransformation benutzt wurde. Durch das Rotieren und anschließende Sortieren (Schritte 1.2 und 1.3) werden die vorderen Spalten der Tabelle korrekt ausgefüllt, da die Tabelle für die Vorwärtstransformation genauso sortiert war. Durch das Rotieren (Schritt 1.2) wird die letzte Spalte wieder frei, so dass sie wieder gefüllt werden kann, und zwar mit Daten, die zu den schon ausgefüllten vorderen Spalten passen.

#### Beispielcode

Beispielcode in Lua:

## Laufzeit

Der Algorithmus zum Berechnen der Burrows-Wheeler-Transformation erzeugt die gesamte Matrix und benötigt die Laufzeit $O(n^{2}\cdot \log(n))$ zum Sortieren von $n$ Zeichenketten (jede der zyklischen Rotationen), wobei jeder Vergleich die Laufzeit $O(n)$ benötigt. Tatsächlich können wir die BWT aus dem Suffix-Array einer Zeichenkette in $O(n)$ Zeit berechnen. Das liegt daran, dass das Suffix-Array und die Zeichenkette des BWT sehr eng miteinander verbunden sind. Das Suffix-Array wird durch Sortieren aller Suffixe der Zeichenkette erzeugt.
Betrachten wir die Matrix $M_{S}$, wobei aber in jeder Zeile die Zeichen nach dem $ gelöscht wurden. Jede Zeile in dieser neuen Matrix stellt ein Suffix von $S$ dar, und sie sind noch immer in sortierter Reihenfolge, weil vor jedem Zeichen ein $ kommt. Das Suffix-Array von $S$ besteht also aus den Indexen der Suffixe in der Reihenfolge, in der sie in der Matrix $M_{S}$ erscheinen. Betrachten wir die Zeile $i$ der Matrix $M_{S}$. Das Suffix in dieser Zeile wird durch $SA[i]$ angegeben, wobei $SA$ das Suffix-Array von $S$ ist. Das Zeichen mit Index $i$ ist dasjenige, das direkt vor diesem Suffix steht, nämlich $S[SA[i]-1]$. Daher kann die Burrows-Wheeler-Transformation wie folgt berechnet werden: