> bwt | transformieren | komprimieren <

// Burrows-Wheeler-Transformation – reversible Texttransformation zur Verbesserung der Kompression

EINGABE 0 Zeichen

Rotationsmatrix anzeigen

EOF-Markierung ($) hinzufügen

AUSGABE 0 Zeichen

>> Funktionen

[REVERSIBLE]

Vollständig reversibel

Verlustfreie Transformation, die exakt rückgängig gemacht werden kann.

[CLUSTERING]

Zeichenclustering

Gruppiert ähnliche Zeichen, damit nachfolgende Kodierer besser komprimieren können.

[BZIP2]

Kern von bzip2

Grundlage vieler bzip2-ähnlicher Kompressionsverfahren.

>> Technische Infos

Funktionsweise von BWT

Die Burrows-Wheeler-Transformation erzeugt alle zyklischen Rotationen der Eingabezeichenkette, sortiert diese lexikografisch und gibt die letzte Spalte der sortierten Matrix zusammen mit dem Index der ursprünglichen Zeichenkette aus. Dadurch werden ähnliche Zeichen gruppiert, was sich hervorragend mit RLE, Move-to-Front und anderen Entropiecodierern komprimieren lässt.

BWT-Beispiel

Input: "banana$"

Rotations:
0: banana$
1: anana$b
2: nana$ba
3: ana$ban
4: na$bana
5: a$banan
6: $banana

Sorted:
0: $banana
1: a$banan
2: ana$ban
3: anana$b
4: banana$
5: na$bana
6: nana$ba

Last column: annb$aa
Original index: 4

Output: annb$aa|4

Warum BWT verwenden

Verbessert die Komprimierbarkeit von Daten
Komplett reversibel
Gruppiert ähnliche Kontexte
Grundlage des bzip2-Kompressionsalgorithmus
Effektives Preprocessing für andere Kodierer

>> Häufige Fragen

Was ist die Burrows-Wheeler-Transformation?

Die Burrows-Wheeler-Transformation (BWT) ist ein reversibler Algorithmus, der eine Zeichenkette so umordnet, dass lange Läufe ähnlicher Zeichen entstehen. Sie wurde 1994 von Michael Burrows und David Wheeler vorgestellt und wird in Kompressoren wie bzip2 als Vorbereitungsschritt eingesetzt, um bessere Kompressionsraten zu erzielen.

Warum verbessert BWT die Kompression?

BWT bringt Zeichen zusammen, die in ähnlichen Kontexten auftreten. In der Ausgabe erscheinen viele gleiche Symbole hintereinander, was sich besonders gut mit Lauflängencodierung, Move-to-Front und Entropiecodierung wie Huffman komprimieren lässt.

Was ist das EOF-Zeichen?

Das EOF-Zeichen (End Of File), meist das Symbol '$' oder ein anderes eindeutiges Zeichen, sorgt dafür, dass alle Rotationen eindeutig sind und der Index der ursprünglichen Zeichenkette bestimmt werden kann. Ohne EOF hätten manche Eingaben keine eindeutige Darstellung. Beim Inversen wird das EOF-Zeichen wieder entfernt.

Ist BWT selbst ein Kompressionsverfahren?

Nein. BWT komprimiert nicht direkt, sondern transformiert Daten, damit sie sich besser komprimieren lassen. In Schemata wie bzip2 wird BWT typischerweise mit Move-to-Front, RLE und Huffman-Codierung kombiniert.