BWT: Enkodierung

Die Transformation erfolgt über eine Matrix, in der die Ausgangsdaten blockweise angeordnet werden. In der ersten Zeile werden die Originaldaten in unveränderter Weise hinterlegt. Alle nachfolgenden Zeilen stellen eine linkssgerichtete Rotation der jeweilig vorhergehenden Zeile dar:

Matix für "abrakadabra":

      0 1 2 3 4 5 6 7 8 9 10

   0  a b r a k a d a b r a a
       / / / / / / / / / / /
   1  b r a k a d a b r a a
   2  r a k a d a b r a a b
   3  a k a d a b r a a b r
   4  k a d a b r a a b r a
   5  a d a b r a a b r a k
   6  d a b r a a b r a k a
   7  a b r a a b r a k a d
   8  b r a a b r a k a d a
   9  r a a b r a k a d a b
  10  a a b r a k a d a b r

Anschließend wird diese Matrix "lexikographisch" sortiert, d.h. in der bei Lexika gebräuchlichen Reihenfolge. Das höchstwertige Zeichen wird in diesem Beispiel durch die erste Spalte repräsentiert:

      0 1 2 3 4 5 6 7 8 9 10

   0  a a b r a k a d a b r
   1  a b r a a b r a k a d
   2  a b r a k a d a b r a
   3  a d a b r a a b r a k
   4  a k a d a b r a a b r
   5  b r a a b r a k a d a
   6  b r a k a d a b r a a
   7  d a b r a a b r a k a
   8  k a d a b r a a b r a
   9  r a a b r a k a d a b
  10  r a k a d a b r a a b

Gespeichert wird nun die letzte Spalte der Matrix und die Information, in welcher Zeile sich die Originaldaten befinden, in diesem Beispiel in der Zeile 2. Als Ergebnis der Burrows-Wheeler-Transformation liegen folgende Daten vor:

      r d a k r a a a a b b 2

Die BWT existiert in verschiedenen Varianten, die geringfügig voneinander abweichen, aber vom Prinzip her identisch sind. Hier wird der Algorithmus in Anlehnung an die Original-Publikation von Michael Burrows und David Wheeler beschrieben.

 <   ^   >