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


 <   ^   > 

Burrows-Wheeler-Transformation (BWT) Burrows-Wheeler-Transformation (BWT) BWT: Eigenschaften der transformierten Daten



Anzeigen:

Informations- und Kodierungstheorie