Burrows-Wheeler-Transformation (bwt)

Definition - Was bedeutet Burrows-Wheeler-Transformation (BWT)?

Die Burrows-Wheeler-Transformation (BWT) ist ein Algorithmus, der Datenblöcke wie Zeichenfolgen in Läufe ähnlicher Zeichen umordnet. Nach der Transformation enthält der Ausgabeblock dieselben exakten Datenelemente, bevor er gestartet wurde, unterscheidet sich jedoch in der Reihenfolge. Die Art des Algorithmus neigt dazu, ähnliche Zeichen nebeneinander zu setzen, wodurch die resultierende Datenreihenfolge leichter zu komprimieren ist. Daher wird es in vielen Komprimierungsalgorithmen verwendet.

Technische.me erklärt Burrows-Wheeler Transform (BWT)

Der Burrows-Wheeler-Transformationsalgorithmus ist ein relativ neuer Algorithmus, der 1994 von Michael Burrows und David Wheeler erfunden wurde und auf einer unveröffentlichten Transformation basiert, die Wheeler 1983 entdeckt hat und die in ihrem Artikel „A Block-Sorting Lossless Data Compression Algorithm“ veröffentlicht wurde.

Im einfachsten Fall nimmt BWT einen Datenblock wie eine Zeichenfolge, fügt ein EOF-Zeichen hinzu und sortiert dann alle Umdrehungen dieser Zeichenfolge in lexikografische Reihenfolge. Der folgende Pseudocode oder die folgenden Schritte veranschaulichen den Algorithmus:

  1. Erstellen Sie eine Tabelle mit Zeilen, die alle möglichen Rotationen der Zeichenfolge in einem Inkrement darstellen.
  2. Sortieren Sie alle Zeilen alphabetisch.
  3. Geben Sie die letzte Spalte der Tabelle aus.

Zum Beispiel: das Wort "Banane"; Wenn Sie ein EOF-Zeichen hinzufügen, wird es zu „Banana $“. Dann wenden wir den Algorithmus an:

1. Erstellen Sie eine Tabelle mit Zeilen, die alle möglichen Rotationen darstellen:

Banane $
anana $ b
nana $ ba
ana $ ban
na $ ich
ein $ Banan
$ Banane

2. Sortieren Sie die Zeilen alphabetisch / lexikografisch anhand der ersten Spalte:

$ Banane
ein $ Banan
ana $ ban
anana $ b
Banane $
nana $ ba
na $ ich

3. Geben Sie die letzte Spalte als BWT-Ausgabe zurück: annb $ aa

Die resultierende Zeichenfolge ist einfacher zu komprimieren, da wiederholte Zeichen nebeneinander angeordnet sind. Es müssen jedoch zusätzliche Daten mit den transformierten Daten gespeichert werden, damit eine umgekehrte Transformation durchgeführt werden kann. Obwohl die resultierenden transformierten Daten größer als ihre ursprüngliche Form sind, wird ihre Komprimierbarkeitseigenschaft um ein Vielfaches erhöht, was sie im Wesentlichen zu einer „freien“ Methode zur Verbesserung der Effizienz von Komprimierungsmethoden macht.