Aufgaben:Aufgabe 2.13: Burrows-Wheeler-Rücktransformation

• Zurück zum Buch

Zu analysierendes
BWT-Ergebnis

Die  Burrows–Wheeler–Transformation – abgekürzt  $\rm 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  $\text{L–Spalte}$  (von „Last”,   letzte Zeile der BWT–Matrix).

• Weiter wird in dieser Aufgabe auf die  $\text{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.

• 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)  vom 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:

(1)   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.

(2)   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  $\text{L–Spalte}$  zugehörige  $\text{F–Spalte}$?

	$\rm SEINMEINDEIN$,
	$\rm NIIINEEEDSMN$,
	$\rm DEEEIIIMNNNS$.

2

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

	$\rm MEINDEINSEIN$,
	$\rm DEINSEINMEIN$,
	$\rm NIESNIEDNIEM$.

3

Was passiert, wenn bei der Rekonstruktion  $\text{(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

Musterlösung

(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:

BW–Rücktransformation mit  $I = 7$  (links) bzw.  $I = 0$  (rechts)

• 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:  

$\rm 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 gleiche Zeichen  $($dreimal  $\rm E$,  dreimal  $\rm I$,  dreimal  $\rm N$ sowie je einmal  $\rm D$,  $\rm M$  und  $\rm S)$.