Exercise 2.13: Inverse Burrows-Wheeler Transformation

• Return to book

Die Burrows–Wheeler–Transformation – abgekürzt BWT – bewirkt eine blockweise Sortierung der Zeichen eines Textes mit dem Ziel, den Text für die effiziente Datenkomprimierung mit Hilfe einer Lauflängencodierung oder einer Entropiecodierung aufzubereiten.

• Zunächst wird aus einem Block der Länge $N$ eine $N×N$–Matrix erzeugt, wobei sich jede Zeile dieser ersten BWT–Matrix aus der Vorgängerzeile durch zyklische Linksverschiebung ergibt.

• Danach wird die Matrix lexikografisch (ohne Sonderzeichen: alphabetisch) sortiert. Das Ergebnis der BWT ist die letzte Zeile der neuen BWT–Matrix, die so genannte L–Spalte.

• Weiter wird in dieser Aufgabe auf die F–Spalte (von „First”, erste Zeile der BWT–Matrix) Bezug genommen, die man für die inverse Burrows–Wheeler–Transformation benötigt ⇒ Rekonstruktion des Originaltextes aus der L–Spalte (von „Last”, Letzte Zeile der BWT–Matrix) .

• Für die inverse BWT benötigt man ferner den so genannten Primärindex $I$. Dieser gibt diejenige Zeile der BWT–Matrix an, in welcher der Algorithmus gestartet werden muss.

Die Grafik zeigt das Ergebnis einer BWT, genauer gesagt deren L–Spalte. Aus dieser soll der Originaltext entsprechend der Beschreibung auf der Theorieseite Burrows–Wheeler–Transformation rekonstruiert werden, wobei in Teilaufgabe (2) von Primärindex $I = 7$ und in Teilaufgabe (3) von $I = 0$ auszugehen ist.

Hinweise:

• Die Aufgabe gehört zum Kapitel Weitere Quellencodierverfahren.
• Insbesondere wird Bezug genommen auf die Seite Burrows–Wheeler–Transformation.
• Weitere Informationen finden Sie in den beiden nachfolgend genannten Veröffentlichungen:

  Abel, J.: Verlustlose Datenkompression auf Grundlage der Burrows-Wheeler-Transformation.
      In: PIK - Praxis der Informationsverarbeitung und Kommunikation, no. 3, vol. 26, S. 140-144, Sept. 2003.

  Abel, J.: Grundlagen des Burrows-Wheeler-Kompressionsalgorithmus.
      In: Informatik Forschung & Entwicklung, no. 2, vol. 18, S. 80-87, Jan. 2004.

Fragebogen

1

Wie lautet die zur vorgegebenen L–Spalte zugehörige F–Spalte?

	SEINMEINDEIN,
	NIIINEEEDSMN,
	DEEEIIIMNNNS.

2

Wie lautet das Ergebnis der Rekonstruktion mit dem Primärindex $I = 7$?

	MEINDEINSEIN,
	DEINSEINMEIN,
	NIESNIEDNIEM.

3

Was passiert, wenn bei der Rekonstruktion (BWT–Rücktransformation) vom falschen Primärindex $I = 0$ ausgegangen wird?

	Es ergibt sich der Originaltext, von hinten nach vorne gelesen.
	Das Ergebnis ist eine zyklische Vertauschung des Originals.

4

Warum ist die Burrows–Wheeler–Transformierte hinsichtlich einer späteren Datenkomprimierung besser geeignet als das Original?

	Es ergeben sich günstigere Zeichenhäufigkeiten.
	Alle Zeichen sind lexikografisch sortiert.
	Gleiche Zeichen folgen in der BWT öfter aufeinander.

Musterlösung

Solution

(1)  Richtig ist der Lösungsvorschlag 3:

• Man bezeichnet die erste Spalte der BWT–Matrix auch als F–Spalte und die letzte Spalte als L–Spalte (von „First” bzw. „Last”).
• Weitergegeben zur nächsten Codierstufe wird nur die L–Spalte.
• Die F–Spalte, die zur Rücktransformation ebenfalls benötigt wird, ergibt sich aus der L–Spalte durch lexikografisches Sortieren.

(2)  Richtig ist der Lösungsvorschlag 1: MEINDEINSEIN, wie aus der linken Darstellung der folgenden Grafik hervorgeht. Beachten Sie, dass die obersten Zeile jeweils für die Zeilennummer I = 0 steht. Zur Erklärung:

• Man beginnt die Decodierung mit der Zeile I = 7 der F–Spalte. Der Inhalt ist „M”.
• Man sucht das entsprechende „M” in der L–Spalte und findet es in der Zeilennummer „1”.
• Von Zeile 1 der L–Spalte geht man horizontal zur F–Spalte und findet das Symbol „E”.
• In gleicher Weise findet man das dritte Ausgabesymbol „I” in der Zeile 4 der F–Spalte.
• Der Decodieralgorithmus endet mit dem Ausgabesymbol „N” in der drittletzten Zeile.

(3)  Richtig ist der Lösungsvorschlag 2: DEINSEINMEIN, wie aus der rechten Grafik hervorgeht.

(4)  Richtig ist der Lösungsvorschlag 3:

• Bei der BWT sind hier vier Zeichen gleich ihren Vorgängern, im Original kein einziges.
• In der F–Spalte wären zwar aufgrund der lexikografischen Sortierung noch mehr Zeichen gleich wie die jeweiligen Vorgänger (insgesamt 6), aber diese Sortierung lässt sich nicht verlustlos rückgängig machen.
• Auch der Lösungsvorschlag 1 ist falsch: Original und BWT beinhalten genau die gleichen Zeichen (dreimal E,dreimal I, dreimal N sowie je einmal D, M und S).