BWT: Dekodierung

Die eigentliche Innovation der BWT stellt das Verfahren für die Umkehrung der Transformation dar. Als Ausgangsdaten stehen dafür lediglich die Einträge in der letzten Spalte und die Zeilennummer der Originaldaten in der Enkoder-Matrix zur Verfügung. Außerdem wird für die Dekodierung keine rechenintensive Sortierung der gesamten Matrix benötigt. Damit erfolgt die Dekodierung wesentlich schneller als die Enkodierung.

Prinzip der Dekodierung

Die kodierten Daten enthalten die letzte Spalte (Last) der Enkoder-Matrix, aus der sich die erste Spalte (First) wiederherstellen läßt. Dazu macht man sich den Umstand zunutze, dass die erste Spalte (F) die gleichen Symbole beinhaltet wie die letzte Spalte (L), diese jedoch in sortierter Reihenfolge vorliegen.

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

Die rekonstruierten Spalten (L) und (F) entsprechen den ersten beiden Spalten einer Matrix, die aus der Enkoder-Matrix abgeleitet werden kann. Dazu müsste die Enkoder-Matrix lediglich um eine Spalte nach rechts rotiert werden.

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

Die resultierende "virtuelle" Matrix enthält die gleichen Inhalte wie die Enkoder-Martix, d.h. es besteht eine feste Beziehung zwischen den beiden Matrizen. Für die eigentliche Dekodierung sind beide Matrizen nicht erforderlich, wie später ersichtlich wird. Sie sollen nur die Zusammenhänge verdeutlichen.

Wenn bekannt wäre, welche Zeilenpaare jeweils identische Inhalte aufweisen, so könnten die Originaldaten wiederhergestellt werden. Dazu wird ein Transformationsvektor ermittelt, der für jede Zeile der virtuellen Matrix die jeweils identische Zeile in der Enkoder-Matrix adressiert. Um diese Zuordnung zu finden, werden zwei Eigenschaften ausgenutzt:

Das erste Zeichen einer Zeile in den beiden Matrizen muss gleich sein, d.h. für jedes Zeichen in L muss es jeweils ein identisches Zeichen in F geben.

Sofern mehrere, identische Zeichen in L existieren, sind diese in der Reihenfolge ihres Auftretens einander zugeordnet. Dies resultiert aus dem Sortiervorgang, der beiden Matrizen zugrunde liegt. Wenn in der virtuellen Matrix das erste Zeichen in L gleich ist, so werden nur die restlichen Spalten betrachtet, die identisch mit der sortierten Enkoder-Matrix sind.

Aus diesen Beziehungen ergibt sich der Transformationsvektor T. Die Zuordnungen für das Symbol 'r' sind farblich hervorgehoben.

   Enkoder                Dekoder
   F                   L  L F                    T
0  a a b r a k a d a b r  r a a b r a k a d a b  9
1  a b r a a b r a k a d  d a b r a a b r a k a  7
2  a b r a k a d a b r a  a a b r a k a d a b r  0
3  a d a b r a a b r a k  k a d a b r a a b r a  8
4  a k a d a b r a a b r  r a k a d a b r a a b 10
5  b r a a b r a k a d a  a b r a a b r a k a d  1
6  b r a k a d a b r a a  a b r a k a d a b r a  2
7  d a b r a a b r a k a  a d a b r a a b r a k  3
8  k a d a b r a a b r a  a k a d a b r a a b r  4
9  r a a b r a k a d a b  b r a a b r a k a d a  5
10 r a k a d a b r a a b  b r a k a d a b r a a  6

Über den Transformationsvektor T kann, ausgehend von dem primären Index jeweils auf das vorhergehende Symbol geschlossen werden. Das letzte Symbol wird direkt über den gespeicherten Index adressiert, im Beispiel L(2) = 'a'. Über den zugehörigen Eintrag in T(2) = 0 wird das vorhergehende Symbol L(T(2)) = L(0) = 'r' identifiziert, usw.

Rekonstruktion über den Transformationsvektor:

angeordnet entsprechend des Aufbaus von L:

Zeile  L   T              S
0      r   9  Schritt  2  ra
1      d   7  Schritt  5  dabra
2      a   0  Schritt  1  a
3      k   8  Schritt  7  kadabra
4      r  10  Schritt  9  rakadabra
5      a   1  Schritt  4  abra
6      a   2  Schritt 11  abrakadabra
7      a   3  Schritt  6  adabra
8      a   4  Schritt  8  akadabra
9      b   5  Schritt  3  bra
10     b   6  Schritt 10  brakadabra


angeordnet nach Schritten:

Zeile  L   T              S
2      a   0  Schritt  1  a
0      r   9  Schritt  2  ra
9      b   5  Schritt  3  bra
5      a   1  Schritt  4  abra
1      d   7  Schritt  5  dabra
7      a   3  Schritt  6  adabra
3      k   8  Schritt  7  kadabra
8      a   4  Schritt  8  akadabra
4      r  10  Schritt  9  rakadabra
10     b   6  Schritt 10  brakadabra
6      a   2  Schritt 11  abrakadabra

Um diese Beziehungen herzustellen, ist weder die ursprüngliche, noch die virtuelle Matrix erforderlich. Die Kenntnis von L und F reicht vollkommen aus.

In vergleichbarer Weise lassen sich abweichende Prozeduren definieren, die die Daten in Originalreihenfolge rekonstruieren und nicht mit dem letzten Zeichen beginnen. Das ist beispielsweise mit Hilfe von Änderungen in der Sortierreihenfolge, dem Index und der Abbildungsvorschrift des Transformationsvektors möglich. Am Prinzip des Verfahrens ändert sich dadurch nichts.

 <   ^   >