Burrows-Wheeler Transform
Die Burrows-Wheeler-Transformation (BWT) sortiert alle zyklischen Rotationen eines Textes und nimmt die letzte Spalte, um ähnliche Zeichen zu clustern und die Daten für die nachfolgende Kompression vorzubereiten.
Zweck
Sie ist eine umkehrbare Transformation, die Text in eine besser komprimierbare Form bringt (ähnliche Zeichen gebündelt) und die erste Stufe der bzip2-Pipeline ist.
Mechanismus
Die Matrix aller zyklischen Rotationen des Textes wird aufgebaut, die Zeilen sortiert und die letzte Spalte als BWT-Ausgabe genommen, wobei der Index der Originalzeile notiert wird. Die Rücktransformation stellt den Text über die LF-Abbildung und diesen Index wieder her.
Anwendungsfälle
- Vortransformation in der bzip2-Kompression
- Genomsequenzanalyse
- Aufbau von Volltextindizes