Michael Burrows

Die Burrows-Wheeler-Transformation (BWT) ist ein Algorithmus, der in Datenkompressionstechniken wie bzip2 Anwendung findet, dabei allerdings selbst keine Datenkompression durchführt. Er wurde von Michael Burrows und David Wheeler entwickelt.

Eigenschaften

Die BWT ist ein Algorithmus, der aus einem Block Daten (Eingabe) einen gleichgroßen Block Daten (Ausgabe) sowie eine kleine 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 Sortierreihenfolge der Zeichen ist relativ egal, solange die Zeichen vollständig geordnet sind.
• Der Index, der als Ausgabe der BWT entsteht, kann 1-basiert oder 0-basiert sein.

Wichtig ist, dass für die Vorwärts- und Rückwärtstransformationen diese Parameter gleich sind.

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 Anfang der Daten an das Ende 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.

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, 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 sortiert.

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

Anmerkungen:

• Die Sortierreihenfolge ist hier so gewählt, dass der Punkt hinter den Buchstaben einsortiert wird.
• In dem Ausgabetext kommen gleiche Zeichen öfter hintereinander vor als im Eingabetext.

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

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 1 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.

1. Führe die folgenden Schritte aus, bis die Tabelle voll ist:
   1. Der codierte Text wird zeichenweise senkrecht in die letzte Spalte der Tabelle geschrieben.
   2. Die Tabelle wird dann um eine Position nach rechts rotiert, so dass die letzte Spalte zur ersten Spalte wird.
   3. Dann wird die Tabelle sortiert.
2. 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 in Lua

function BWT_rueckwaerts(text, index)
  local len = string.len(text)
 
  -- Am Anfang ist die Tabelle leer
  local tabelle = {}
  for i = 1, len do
    tabelle[i] = ""
  end
 
  for n = 1, len do
    -- Codierten Text zeichenweise vor die erste Spalte setzen
    for i = 1, len do
      tabelle[i] = string.sub(text, i, i) .. tabelle[i]
    end
 
    -- Tabelle sortieren
    for i = 1, len do
      for j = i + 1, len do
        if tabelle[i] > tabelle[j] then
          tabelle[i], tabelle[j] = tabelle[j], tabelle[i]
        end
      end
    end
  end
 
  return tabelle[index]
end

Siehe auch

• Move to front, ein Kompressionsverfahren, das häufig nach der Burrows-Wheeler-Transformation eingesetzt wird.

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
• Ausführliche Beschreibung der BWT