BWT: Eigenschaften der transformierten Daten

Durch die BWT gewonnen Daten bestehen zwar aus den gleichen Symbolen, ihre Anordnung ist jedoch durch die charakteristischen Eigenschaften der Originaldaten bestimmt. Die nachfolgenden Beispiele sollen dies verdeutlichen.

Bedingt durch die Rotation der Originaldaten, stellen die transformierten Symbole jeweils die Vorgänger der Daten in der ersten Spalte dar.

   a b r a k a d a b r a

   a a b r a k a d a b r    ra
   a b r a a b r a k a d    da
   a b r a k a d a b r a    aa
   a d a b r a a b r a k    ka
   a k a d a b r a a b r    ra
   b r a a b r a k a d a    ab
   b r a k a d a b r a a    ab
   d a b r a a b r a k a    ad
   k a d a b r a a b r a    ak
   r a a b r a k a d a b    br
   r a k a d a b r a a b    br

Dadurch wird der Zusammenhang abgebildet, in dem bestimmte Zeichen auftreten. Im Beispiel sind nacheinander alle Zeichen enthalten, die einem 'a' vorausgehen {'r', 'd', 'a', 'k', 'r'}. Dieser Zusammenhang wird im nachfolgenden Beispiel noch deutlicher.

Auf der linken Seite werden Daten transformiert, die aus drei aufeinanderfolgenden Sequenzen ("abcd") bestehen. Folglich geht einem 'a' immer ein 'd' voraus, einem 'b' immer ein 'a', usw. Die Ausgangsdaten im rechten Beispiel enthalten im Gegensatz dazu keine redundanten Anordnungen.

a b c d a b c d a b c d   a b c d a a c c b d d b

a b c d a b c d a b c d   a a c c b d d b a b c d
a b c d a b c d a b c d   a b c d a a c c b d d b
a b c d a b c d a b c d   a c c b d d b a b c d a
b c d a b c d a b c d a   b a b c d a a c c b d d
b c d a b c d a b c d a   b c d a a c c b d d b a
b c d a b c d a b c d a   b d d b a b c d a a c c
c d a b c d a b c d a b   c b d d b a b c d a a c
c d a b c d a b c d a b   c c b d d b a b c d a a
c d a b c d a b c d a b   c d a a c c b d d b a b
d a b c d a b c d a b c   d a a c c b d d b a b c
d a b c d a b c d a b c   d b a b c d a a c c b d
d a b c d a b c d a b c   d d b a b c d a a c c b

Gleichartige Symbolkombinationen führen nach der Burrows-Wheeler-Transformation zu Wiederholungen in den transformierten Daten. Die daraus entstehende Redundanz läßt sich mit einfachen statistischen Kodes ausnutzen, die in hohen Maße auf derartige Änderungen in der Symbolverteilung reagieren, z.B. der adaptiven Huffman-Kodierung.