Burrows-Wheeler-Transformation (BWT)

Sortierst du alle zyklischen Rotationen eines Texts, landen alle Rotationen mit demselben Suffix nebeneinander. Die letzte Spalte — das Zeichen direkt vor jedem sortierten Präfix — sammelt Zeichen, die im Originaltext alle demselben Kontext vorausgingen. Wiederholte Muster bedeuten, dass viele Rotationen ein gemeinsames Suffix teilen, sodass dasselbe vorausgehende Zeichen viele Male hintereinander in der letzten Spalte erscheint. Genau diese Runs nutzen RLE und Move-to-Front-Codierung aus. Die Transformation ist verlustfrei, weil die erste Spalte F (sortierte BWT) und die letzte Spalte L (die BWT selbst) zusammen eine vollständige Zuordnung — das LF-Mapping — codieren, mit der du den Originaltext allein aus diesen beiden Spalten und dem Key Zeichen für Zeichen rekonstruieren kannst.

Für sich genommen macht die BWT den Text nicht kleiner: Die Ausgabe hat genau dieselbe Länge und dieselben Zeichen, nur in anderer Reihenfolge. Ihre eigentliche Aufgabe ist ein umkehrbarer Vorbereitungsschritt, der gleiche Zeichen zusammenrückt, damit es die nachfolgenden Kompressoren — Move-to-Front, Lauflängenkodierung, dann Huffman- oder arithmetische Kodierung — leicht haben. Die Erkenntnis: Der Gewinn liegt nicht in der Größe der BWT-Ausgabe, sondern darin, wie viel besser komprimierbar sie wird.

Eine Kompressionsidee wurde still und leise zu einem Eckpfeiler der Genomik. Verpackt in eine Struktur namens FM-Index erlaubt die BWT, ein kurzes DNA-Fragment in einem 3 Milliarden Buchstaben langen menschlichen Genom zu suchen, während dieses Genom nur wenige Gigabyte belegt. Aligner wie Bowtie und BWA — der Burrows-Wheeler Aligner — bauen darauf auf, sodass ein Kompressionstrick von 1994 heute den täglichen Abgleich von Millionen Sequenzierungs-Reads trägt.