Inhaltsverzeichnis:
- Definition - Was bedeutet Burrows-Wheeler-Transformation (BWT)?
- Techopedia erklärt die Burrows-Wheeler-Transformation (BWT)
Definition - Was bedeutet Burrows-Wheeler-Transformation (BWT)?
Die Burrows-Wheeler-Transformation (BWT) ist ein Algorithmus, der Datenblöcke, z. B. Zeichenfolgen, in Läufe mit ähnlichen 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 tendiert dazu, ähnliche Zeichen nebeneinander zu platzieren, wodurch die resultierende Datenreihenfolge leichter komprimiert werden kann. Daher wird es in vielen Komprimierungsalgorithmen verwendet.
Techopedia erklärt die Burrows-Wheeler-Transformation (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 in seinem Artikel „A Block-Sorting Lossless Data Compression Algorithm“ entdeckte.
Im einfachsten Fall nimmt BWT einen Datenblock wie eine Zeichenfolge, fügt ein EOF-Zeichen hinzu und sortiert dann alle Drehungen dieser Zeichenfolge in lexikografischer Reihenfolge. Der folgende Pseudocode oder die folgenden Schritte veranschaulichen den Algorithmus:
- Erstellen Sie eine Tabelle mit Zeilen, die alle möglichen Rotationen der Zeichenfolge in Schritten von einem Schritt darstellen.
- Alle Zeilen alphabetisch sortieren.
- Die letzte Spalte der Tabelle ausgeben.
Zum Beispiel: das Wort "Banane"; Durch Hinzufügen eines EOF-Zeichens wird es in "banana $" umgewandelt. 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 $ bana
ein $ banan
$ Banane
2. Sortieren Sie die Zeilen alphabetisch / lexikografisch nach der ersten Spalte:
$ Banane
ein $ banan
ana $ ban
anana $ b
Banane $
nana $ ba
na $ bana
3. Geben Sie die letzte Spalte als BWT-Ausgabe zurück: annb $ aa
Die resultierende Zeichenfolge lässt sich leichter komprimieren, da sich wiederholende Zeichen nebeneinander befinden. Es müssen jedoch zusätzliche Daten mit den transformierten Daten gespeichert werden, damit eine Rücktransformation 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 Komprimiermethoden macht.
