BWT
BWT ist die Abkürzung für die Burrows-Wheeler-Transformation, die Text in eine Form bringt, in der ähnliche Zeichen zusammenliegen; sie ist die erste Stufe von bzip2.
Zweck
Ein umkehrbarer Vorverarbeitungsschritt, der die nachfolgende Kompression verbessert, indem identische Zeichen gebündelt werden, sodass RLE und Entropiekodierung besser arbeiten.
Mechanismus
Die sortierte Matrix aller zyklischen Rotationen wird aufgebaut, die letzte Spalte entnommen und die ursprüngliche Zeilennummer vermerkt. Die Rücktransformation stellt über die LF-Abbildung aus letzter Spalte und Zeilennummer den Originaltext wieder her.
Anwendungsfälle
- bzip2-Kompression
- Genom-Alignment
- Volltextindizierung