WikiDer > Burrows-Wheeler-Transformation
Das Burrows-Wheeler-Transformation (unten auch abgekürzt als BWT) ist ein Transformation von einer Schnur zu einer Form, in der es einfacher ist zu Kompresse ist. Die bekannteste Anwendung der Burrows-Wheeler-Transformation ist das Programm bzip2.
Die Burrows-Wheeler-Transformation ändert die Reihenfolge der Zeichen in einer Zeichenfolge, die Zeichen selbst bleiben unverändert. Nach der BWT werden viele Zeichen aneinander grenzen, so dass zum Beispiel die RLEAlgorithmus besser angewendet werden kann. Um eine gute Komprimierung zu erzielen, muss die Zeichenfolge mindestens einige Kilobyte groß sein.
Die Burrows-Wheeler-Transformation wurde 1983 von . erfunden David Wheeler und veröffentlicht von M. Burrows und David Wheeler im Jahr 1994.
Algorithmus
Angenommen, wir haben eine Zeichenfolge darin Alphabet [a-z]* ist "orange". Um eine BWT anzuwenden, schreiben wir das Wort um eine Position untereinander gedreht:
orange orangesorange orangesorangesorangesorangesorangesorangesorangesorangesorangesorange |
Dann sortieren wir die 11 Strings, die wir jetzt haben. Die Sortierung nach Alphabet ist offensichtlich, also machen wir das hier, aber im Prinzip spielt es keine Rolle, ob wir beim Rückgängigmachen dieselbe Sortierung verwenden:
orangesorangesorangesorangesorangesorangesorangesorangesorangesorangesorangesorangesorange |
Die erste Spalte in dieser sortierten Matrix wir nennen F, die letzte Spalte L. Die Burrows-Wheeler-Transformation einer Zeichenkette besteht aus der Spalte L plus der vertikalen Position des Originaltextes in der Matrix, in unserem Fall ist dies zufällig die Position 11. Die BWT unserer Zeichenfolge ist daher:
11 | nsapseipaal |
Das Bemerkenswerte an der Burrows-Wheeler-Transformation ist, dass sie reversibel ist; eine Sortierung rückgängig zu machen ist, gelinde gesagt, bemerkenswert. Dies funktioniert jedoch.
Beachten Sie, dass Sie F erhalten können, wenn Sie L kennen, indem Sie L sortieren. Aus diesen beiden Strings können wir einen Transformationsvektor T ableiten; wir suchen nach jedem Zeichen in L, an welcher Stelle es in F vorkommt:
| l | f | T |
|---|---|---|
nsapseipaal | aaaeilnppss | 7101811459236 |
Wir können jetzt die ursprüngliche Zeichenfolge wie folgt wiederherstellen:
- Wir beginnen mit dem Index des BWT (das war die Position des Originaltextes im sortierten Array). In diesem Fall war es eine 11.
- Das 11. Zeichen von L ist a l. Wir betrachten Position 11 in T. Es gibt eine 6.
- Das 6. Zeichen von L ist a e. An Position 6 in T ist eine 4.
- Das 4. Zeichen von L ist a p. An Position 4 in T ist eine 8.
- Das 8. Zeichen von L ist a p. An Position 8 in T ist eine 9.
- Das 9. Zeichen von L ist a ein. An Position 9 in T ist eine 2.
- Das 2. Zeichen von L ist a so. An Position 2 in T ist eine 10.
- Das 10. Zeichen von L ist a ein. An Position 10 in T ist eine 3.
- Das 3. Zeichen von L ist a ein. An Position 3 in T ist eine 1.
- Das 1. Zeichen von L ist a nein. An Position 1 in T ist eine 7.
- Das 7. Zeichen von L ist a ich. An Position 7 in T ist eine 5.
- Das 5. Zeichen von L ist a so. An Position 5 in T ist eine 11. Wir stoppen, weil die 11 dem Index entspricht, mit dem wir begonnen haben.
Nachdem wir unser vorläufiges Ergebnis (nämlich "leppasaanis") invertiert haben, erhalten wir unsere ursprüngliche Zeichenfolge "orange".
Arbeitsprinzip
Das Ziel von BWT ist es, den Text so umzuordnen, dass Sie viele Buchstabenwiederholungen erhalten. Der transformierte Text ist immer noch so lang wie das Original, lässt sich aber leichter komprimieren. Bestimmte Kompressionsalgorithmen funktionieren besser bei Texten mit vielen Buchstabenwiederholungen.
Die Funktionsweise von BWT basiert darauf, dass in einer natürlichen Sprache bestimmte Buchstabenkombinationen häufiger vorkommen als andere. Die Transformation sortiert die Buchstaben nach der Buchstabenfolge, die ihnen folgt. Zum Beispiel die ich in sichnaasappel wird nach dem String "naasap..." sortiert. Im Niederländischen folgt beispielsweise oft ein „h“. Daher werden die Buchstaben 'c' in einem niederländischen Text nach einer BWT-Transformation oft aufeinander folgen. Je länger der Text, desto stärker der Effekt. Wenn das Wort 'Orange' in einer Veröffentlichung des Gemüsehändlerverbandes 10 Mal vorkommt, finden Sie alle s dieses Wortes nacheinander im umgewandelten Text.