Aufgabe vollständig gelöst
-
Die Burrows-Wheeler-Transformation von "banana$" mit allen sieben sortierten Rotationen 5 Schritte
Bestimmen Sie die Burrows-Wheeler-Transformation von "banana$" und entscheiden Sie anschließend, ob etwas komprimiert wurde. Dies ist der Schritt BWT-Ausgabe: Sentinel-Zeichen angehängt, alle sieben Rotationen sortiert, letzte Spalte abgelesen.
-
Das Sentinel-Zeichen wird angehängt, bevor irgendetwas anderes geschieht. Da $ vor jedem Buchstaben einsortiert wird und genau einmal vorkommt, können zwei Rotationen niemals als gleich verglichen werden, sodass die Sortierung ein einziges, eindeutiges Ergebnis hat.
-
Die lexikographische Sortierung der Rotationen ist die einzige Arbeit, die die Transformation verrichtet. Liest man die sieben Zeilen von oben nach unten, fällt auf, dass die Sortierung die Zeichenkette danach gruppiert hat, was nach der jeweiligen Position steht.
-
Das letzte Zeichen einer Rotation ist das Zeichen, das im Original unmittelbar vor ihrem ersten Zeichen steht. Deshalb erzeugt die Sortierung Läufe: Die Zeilen 1 und 2 beginnen beide mit 'a' und enden beide mit 'n', da beiden dieser a's ein n in banana vorausgeht. Der Schlüssel ist die Zeilennummer des Originals, und ohne ihn kann die Transformation nicht rückgängig gemacht werden.
-
Bisher wurde nichts komprimiert, und es hätte auch nichts komprimiert werden können — die Ausgabe ist eine Permutation der Eingabe, dieselben sieben Zeichen in einer anderen Reihenfolge. Was sich geändert hat, ist die Laufstruktur, und das ist das Einzige, was sich geändert hat.
-
RLE berechnet zwei Byte pro Lauf, sodass fünf Läufe zehn Byte gegenüber einer Sieben-Byte-Eingabe kosten. Die Schwelle zur Rentabilität verschiebt sich nie: Die Anzahl der Läufe muss unter der Hälfte der Länge liegen, was hier drei oder weniger bedeutet.
Antwort
Das Bedienfeld zeigt annb$aa mit key = 4, eine durchschnittliche Lauflänge von 1,4 Zeichen, 10 Byte RLE und einen Wert von 0,70× an. Die Transformation hat genau das getan, was sie verspricht — sie hat die durchschnittliche Lauflänge um 40% gesteigert, ohne ein einziges Zeichen anzurühren —, und dennoch hat die Pipeline verloren, da sieben Zeichen nicht genug Text sind, damit dieser Gewinn zwei Byte pro Lauf deckt. Verdoppelt man das Wort, kippt die Rechnung. "bananabanana$" hat dreizehn Zeichen und seine Transformation lautet annnnbba$aaaa: sechs Läufe statt fünf, während sich die Länge nahezu verdoppelt hat, was 12 Byte gegenüber 13 und einen Wert von 1,08× ergibt. Das ist das entscheidende Argument für die BWT — die Anzahl der Läufe wird davon bestimmt, wie viele verschiedene Kontexte der Text hat, nicht davon, wie lang er ist. Je länger der Block ist, desto mehr zahlt sie sich aus, weshalb bzip2 Blöcke von bis zu 900 kB statt einzelner Wörter transformiert.
-
Lernpfad
Kompression von Hand
Quellen (3)
- Insight blocks 1 and 2 — the transform itself: M. Burrows and D. J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm." Digital Systems Research Center, Research Report 124, 1994.
- Insight block 3 — the aligners it turned into: B. Langmead, C. Trapnell, M. Pop and S. L. Salzberg, "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome." Genome Biology 10, R25, 2009.
- And the one the block names outright: H. Li and R. Durbin, "Fast and accurate short read alignment with Burrows–Wheeler transform." Bioinformatics 25(14), 1754–1760, 2009.