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.Ursprüngliche Veröffentlichung: M. Burrows, D. Wheeler: A block sorting lossless data compression algorithm. Technical Report 124. Digital Equipment Corporation, 1994 (PDF; 108 kB)
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):
D - ie Tröpfchendurchmesser innerhalb eines N D - ie Unterscheidung von Nebeln in bestimmte d - ie Verfügbarkeit von Wasserdampf und zum d - ie die Luft enthalten kann, ohne dass Kon w - ie die vor allem thermischen Oberflächene s - ie häufig in Richtung von Siedlungsräumen D - ie höchste Nebelhäufigkeit zeigt sich dab w - ie in Auftriebsbereichen der Fall. Die wa s - ie jedoch auch stark zwischen den einzeln d - ie maximale Wasserdampfmenge, die die Luf d - ie ohne bestehende Oberflächen nicht mögl . - ... . - ... . - ... l - ichen Nebeldichte führen, man spricht von l - ichen Nebelhäufigkeit erhöht ist bzw. man l - ichen Skalenbereiche können dabei stark s l - ichen Ursachen und wird im Abschnitt Nebe e - ichen der Fall. Die wahrgenommene Nebelhä l - icher Ursachen den Taupunkt erreicht. Die e - icher einschätzt. Auch die räumlichen Ska n - icht allzu häufig geschieht. Wenn Nebel b n - icht möglich ist. So kann dann auch vor a
Beispielcode Beispielcode in Lua: function BWT_vorwaerts(text) local len = string.len(text)
-- Tabelle mit allen Rotationen des Textes erzeugen local matrix = {} for i = 1, len do matrix[i] = string.sub(text, i) .. string.sub(text, 1, i - 1) end
-- Tabelle sortieren for i = 1, len do for j = i + 1, len do if matrix[i] > matrix[j] then matrix[i], matrix[j] = matrix[j], matrix[i] end end end
-- Aus jeder Zeile das letzte Zeichen nehmen local codiert = "" local index = -1 for i = 1, len do codiert = codiert .. string.sub(matrix[i], -1) if matrix[i] == text then index = i end end
return codiert, index end
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: 1: .ANANAS. 2: ..ANANAS 3: S..ANANA 4: AS..ANAN 5: NAS..ANA 6: ANAS..AN 7: NANAS..A 8: ANANAS..
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.)
1: ANANAS.. 2: ANAS..AN 3: AS..ANAN 4: NANAS..A 5: NAS..ANA 6: S..ANANA 7: .ANANAS. 8: ..ANANAS
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: function BWT_rueckwaerts(text, index) local len = string.len(text)
-- Zeichen mit zugehörigen Positionen in einer Tabelle speichern local tabelle = {} for i = 1, len do tabelle[i] = { position = i, zeichen = string.sub(text, i, i) } end
-- Diese Tabelle nach den Zeichen sortieren. Wichtig ist hier, -- ein ''stabiles'' Sortierverfahren einzusetzen. for i = 1, len - 1 do for j = 1, len - 1 do if tabelle[j].zeichen > tabelle[j + 1].zeichen then tabelle[j], tabelle[j + 1] = tabelle[j + 1], tabelle[j] end end end
-- Beim Index beginnend einmal durch die Tabelle -- wandern und dabei alle Zeichen aufsammeln. local decodiert = "" local idx = index for i = 1, len do decodiert = decodiert .. tabelle[idx].zeichen idx = tabelle[idx].position end
return decodiert end
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:
1: A______. 2: A______N 3: A______N 4: N______A 5: N______A 6: S______A 7: .______. 8: .______S
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.
8│12345678 ────┼──────── 1: .│A______. 2: N│A______N 3: N│A______N 4: A│N______A 5: A│N______A 6: A│S______A 7: .│.?_____. 8: S│.?_____S
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.
8│12345678 ────┼──────── 1: .│AN_____. 2: N│AN_____N 3: N│AS_____N 4: A│NA_____A 5: A│NA_____A 6: A│S._____A 7: .│.A_____. 8: S│.._____S