Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Shannon-Fano

Huffman

Lempel-Ziv (LZ)

arithmetische Kodierung

Run Length Encoding

Burrows-Wheeler (BWT)

Enkodierung

transformierte Daten

Dekodierung

Eigenschaften

Anwendungen

Implementationen

Datenformate


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

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.


 <   ^   > 

adaptive Huffman-Kodierung []

Burrows-Wheeler-Transformation (BWT) BWT: Enkodierung BWT: Dekodierung



Anzeigen:

Informations- und Kodierungstheorie