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

Guenter am 13. August 2021 um 08:10 Uhr

2021-08-13T08:10:56Z

Guenter am 13. August 2021 um 08:06 Uhr

2021-08-13T08:06:29Z

Guenter am 13. August 2021 um 08:01 Uhr

2021-08-13T08:01:56Z

Guenter am 28. Januar 2020 um 15:24 Uhr

2020-01-28T15:24:28Z

Guenter am 28. Januar 2020 um 15:13 Uhr

2020-01-28T15:13:01Z

Guenter am 2. Oktober 2018 um 14:38 Uhr

2018-10-02T14:38:26Z

Guenter am 2. Oktober 2018 um 14:23 Uhr

2018-10-02T14:23:52Z

Guenter am 2. Oktober 2018 um 14:18 Uhr

2018-10-02T14:18:09Z

Guenter: Guenter verschob die Seite Aufgaben:2.13 Burrows-Wheeler-Rücktransformation nach Aufgaben:Aufgabe 2.13: Burrows-Wheeler-Rücktransformation

2018-01-03T14:01:59Z

Guenter verschob die Seite 2.13 Burrows-Wheeler-Rücktransformation nach Aufgabe 2.13: Burrows-Wheeler-Rücktransformation

Guenter am 28. Mai 2017 um 12:08 Uhr

2017-05-28T12:08:55Z

@@ Zeile 70: / Zeile 70: @@
 {{ML-Kopf}}
 '''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>:
-*Man bezeichnet die erste Spalte der BWT&ndash;Matrix auch als&nbsp; F&ndash;Spalte&nbsp; und die letzte Spalte als&nbsp; L&ndash;Spalte&nbsp; (von &bdquo;<i>First</i>&rdquo; bzw. &bdquo;<i>Last</i>&rdquo;).
+*Man bezeichnet die erste Spalte der BWT&ndash;Matrix auch als&nbsp; F&ndash;Spalte&nbsp; und die letzte Spalte als&nbsp; L&ndash;Spalte&nbsp; (von &bdquo;First&rdquo; bzw. &bdquo;Last&rdquo;).
 *Weitergegeben zur nächsten Codierstufe wird nur die&nbsp; L&ndash;Spalte.
 *Die&nbsp; F&ndash;Spalte, die zur Rücktransformation ebenfalls benötigt wird, ergibt sich aus der&nbsp; L&ndash;Spalte&nbsp; durch lexikografisches Sortieren.

@@ Zeile 52: / Zeile 52: @@
 {Was passiert, wenn bei der Rekonstruktion&nbsp; $\text{(BWT&ndash;Rücktransformation})$&nbsp; vom falschen Primärindex&nbsp; $I = 0$&nbsp; ausgegangen wird?
 |type="[]"}
-- Es ergibt sich der Originaltext, von hinten nach vorne gelesen.
+- $\rm MEINDEINSEIN$,
-+ Das Ergebnis ist eine zyklische Vertauschung des Originals.
++ $\rm DEINSEINMEIN$,

@@ Zeile 4: / Zeile 4: @@
 [[Datei:P_ID2478__Inf_A_2_14.png|right|frame|Zu analysierendes <br>BWT-Ergebnis]]
-Die&nbsp;  ''Burrows&ndash;Wheeler&ndash;Transformation'' &ndash; abgekürzt&nbsp; $\rm BWT$&nbsp; &ndash; 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.
+Die&nbsp;  "Burrows&ndash;Wheeler&ndash;Transformation" &ndash; abgekürzt&nbsp; $\rm BWT$&nbsp; &ndash; 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&nbsp; $N$&nbsp; eine&nbsp; $N&times;N$&ndash;Matrix erzeugt, wobei sich jede Zeile dieser ersten BWT&ndash;Matrix aus der Vorgängerzeile durch zyklische Linksverschiebung ergibt.
@@ Zeile 12: / Zeile 12: @@
 * Weiter wird in dieser Aufgabe auf die&nbsp; $\text{F&ndash;Spalte}$&nbsp; (von &bdquo;First&rdquo;, erste Zeile der BWT&ndash;Matrix) Bezug genommen, die man für die inverse Burrows&ndash;Wheeler&ndash;Transformation benötigt &nbsp; &#8658; &nbsp; Rekonstruktion des Originaltextes aus der L&ndash;Spalte.
-* Für die inverse BWT benötigt man ferner den so genannten <i>Primärindex</i>&nbsp; $I$.&nbsp; Dieser gibt diejenige Zeile der BWT&ndash;Matrix an, in welcher der Algorithmus gestartet werden muss.
+* Für die inverse BWT benötigt man ferner den so genannten Primärindex&nbsp; $I$.&nbsp; Dieser gibt diejenige Zeile der BWT&ndash;Matrix an, in welcher der Algorithmus gestartet werden muss.

@@ Zeile 69: / Zeile 69: @@
 {{ML-Kopf}}
 '''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>:
-*Man bezeichnet die erste Spalte der BWT&ndash;Matrix auch als F&ndash;Spalte und die letzte Spalte als L&ndash;Spalte (von &bdquo;<i>First</i>&rdquo; bzw. &bdquo;<i>Last</i>&rdquo;).
+*Man bezeichnet die erste Spalte der BWT&ndash;Matrix auch als&nbsp; F&ndash;Spalte&nbsp; und die letzte Spalte als&nbsp; L&ndash;Spalte&nbsp; (von &bdquo;<i>First</i>&rdquo; bzw. &bdquo;<i>Last</i>&rdquo;).
-*Weitergegeben zur nächsten Codierstufe wird nur die L&ndash;Spalte.
+*Weitergegeben zur nächsten Codierstufe wird nur die&nbsp; L&ndash;Spalte.
-*Die F&ndash;Spalte, die zur Rücktransformation ebenfalls benötigt wird, ergibt sich aus der L&ndash;Spalte durch lexikografisches Sortieren.
+*Die&nbsp; F&ndash;Spalte, die zur Rücktransformation ebenfalls benötigt wird, ergibt sich aus der&nbsp; L&ndash;Spalte&nbsp; durch lexikografisches Sortieren.
 '''(2)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>: <b>MEINDEINSEIN</b>, 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:
-:[[Datei:P_ID2479__Inf_A_2_14b.png|right|frame|BW–Rücktransformation mit $I = 7$ (links) bzw. $I = 0$ (rechts)]]
+'''(2)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>: &nbsp; <b>MEINDEINSEIN</b>, wie aus der linken Darstellung der folgenden Grafik hervorgeht. <br>Beachten Sie, dass die obersten Zeile jeweils für die Zeilennummer&nbsp; $I = 0$&nbsp; steht. Zur Erklärung:
-* Man beginnt die Decodierung mit der Zeile  $I = 7$ der F&ndash;Spalte. Der Inhalt ist  &bdquo;M&rdquo;.
+:[[Datei:P_ID2479__Inf_A_2_14b.png|right|frame|BW–Rücktransformation mit&nbsp; $I = 7$&nbsp; (links) bzw.&nbsp; $I = 0$&nbsp; (rechts)]]
 * Man sucht das entsprechende &bdquo;M&rdquo; in der L&ndash;Spalte und findet es in der Zeilennummer &bdquo;1&rdquo;.
-* Von Zeile 1  der L&ndash;Spalte geht man horizontal zur F&ndash;Spalte  und findet das Symbol &bdquo;E&rdquo;.
+* Von Zeile 1  der L&ndash;Spalte geht man horizontal zur&nbsp; F&ndash;Spalte&nbsp;  und findet das Symbol&nbsp; &bdquo;E&rdquo;.
-* In gleicher Weise findet man das dritte Ausgabesymbol &bdquo;I&rdquo; in der Zeile 4  der F&ndash;Spalte.
+* In gleicher Weise findet man das dritte Ausgabesymbol&nbsp; &bdquo;I&rdquo;&nbsp; in der Zeile 4  der F&ndash;Spalte.
-* Der Decodieralgorithmus endet mit dem Ausgabesymbol &bdquo;N&rdquo; in der drittletzten Zeile.
+* Der Decodieralgorithmus endet mit dem Ausgabesymbol&nbsp; &bdquo;N&rdquo;&nbsp; in der drittletzten Zeile.
-'''(3)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>: &nbsp; $\rm DEINSEINMEIN$, wie aus der rechten Grafik hervorgeht.
+'''(3)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>: &nbsp; <br><br>$\rm DEINSEINMEIN$, wie aus der rechten Grafik hervorgeht.
 <br clear=all>
 '''(4)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>:
 *Bei der BWT sind hier vier Zeichen gleich ihren Vorgängern, im Original kein einziges.
 *In der F&ndash;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: &nbsp; Original und BWT beinhalten genau die gleichen Zeichen (dreimal $\rm E$, dreimal $\rm I$, dreimal $\rm N$ sowie je einmal $\rm D$, $\rm M$ und $\rm S$).
+*Auch der Lösungsvorschlag 1 ist falsch: &nbsp; Original und BWT beinhalten genau gleiche Zeichen&nbsp; $($dreimal&nbsp; $\rm E$,&nbsp; dreimal&nbsp; $\rm I$,&nbsp; dreimal&nbsp; $\rm N$ sowie je einmal&nbsp; $\rm D$,&nbsp; $\rm M$&nbsp; und&nbsp; $\rm S)$.
 {{ML-Fuß}}

@@ Zeile 4: / Zeile 4: @@
 [[Datei:P_ID2478__Inf_A_2_14.png|right|frame|Zu analysierendes <br>BWT-Ergebnis]]
-Die ''Burrows&ndash;Wheeler&ndash;Transformation'' &ndash; abgekürzt '''BWT''' &ndash; 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.
+Die&nbsp;  ''Burrows&ndash;Wheeler&ndash;Transformation'' &ndash; abgekürzt&nbsp; $\rm BWT$&nbsp; &ndash; 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&times;N$&ndash;Matrix erzeugt, wobei sich jede Zeile dieser ersten BWT&ndash;Matrix aus der Vorgängerzeile durch zyklische Linksverschiebung ergibt.
+* Zunächst wird aus einem Block der Länge&nbsp; $N$&nbsp; eine&nbsp; $N&times;N$&ndash;Matrix erzeugt, wobei sich jede Zeile dieser ersten BWT&ndash;Matrix aus der Vorgängerzeile durch zyklische Linksverschiebung ergibt.
-* Danach wird die Matrix lexikografisch (ohne Sonderzeichen: &nbsp; alphabetisch) sortiert. Das Ergebnis der BWT ist die letzte Zeile der neuen BWT&ndash;Matrix, die so genannte <i>L&ndash;Spalte</i>   (von &bdquo;Last&rdquo;, &nbsp; letzte Zeile der BWT&ndash;Matrix).
+* Danach wird die Matrix lexikografisch&nbsp; (ohne Sonderzeichen: &nbsp; alphabetisch)&nbsp; sortiert.&nbsp; Das Ergebnis der BWT ist die letzte Zeile der neuen&nbsp; BWT&ndash;Matrix, die so genannte&nbsp; $\text{L&ndash;Spalte}$&nbsp;  (von &bdquo;Last&rdquo;, &nbsp; letzte Zeile der BWT&ndash;Matrix).
-* Weiter wird in dieser Aufgabe auf die <i>F&ndash;Spalte</i> (von &bdquo;First&rdquo;, erste Zeile der BWT&ndash;Matrix) Bezug genommen, die man für die inverse Burrows&ndash;Wheeler&ndash;Transformation benötigt &nbsp; &#8658; &nbsp; Rekonstruktion des Originaltextes aus der L&ndash;Spalte.
+* Weiter wird in dieser Aufgabe auf die&nbsp; $\text{F&ndash;Spalte}$&nbsp; (von &bdquo;First&rdquo;, erste Zeile der BWT&ndash;Matrix) Bezug genommen, die man für die inverse Burrows&ndash;Wheeler&ndash;Transformation benötigt &nbsp; &#8658; &nbsp; Rekonstruktion des Originaltextes aus der L&ndash;Spalte.
-* Für die inverse BWT benötigt man ferner den so genannten <i>Primärindex</i> $I$. Dieser gibt diejenige Zeile der BWT&ndash;Matrix an, in welcher der Algorithmus gestartet werden muss.
+* Für die inverse BWT benötigt man ferner den so genannten <i>Primärindex</i>&nbsp; $I$.&nbsp; Dieser gibt diejenige Zeile der BWT&ndash;Matrix an, in welcher der Algorithmus gestartet werden muss.
-Die Grafik zeigt das Ergebnis einer BWT, genauer gesagt deren L&ndash;Spalte.
+Die Grafik zeigt das Ergebnis einer BWT, genauer gesagt deren L&ndash;Spalte.&nbsp; Aus dieser soll der Originaltext entsprechend der Beschreibung auf der Theorieseite&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren#Burrows.E2.80.93Wheeler.E2.80.93Transformation|Burrows&ndash;Wheeler&ndash;Transformation]]&nbsp; rekonstruiert werden,
@@ Zeile 26: / Zeile 26: @@
 ''Hinweise:''
-*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Weitere_Quellencodierverfahren|Weitere Quellencodierverfahren]].
+*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren|Weitere Quellencodierverfahren]].
-*Insbesondere wird  Bezug genommen auf die Seite [[Informationstheorie/Weitere_Quellencodierverfahren#Burrows.E2.80.93Wheeler.E2.80.93Transformation|Burrows&ndash;Wheeler&ndash;Transformation]].
+*Insbesondere wird  Bezug genommen auf die Seite&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren#Burrows.E2.80.93Wheeler.E2.80.93Transformation|Burrows&ndash;Wheeler&ndash;Transformation]].
 *Weitere Informationen finden Sie in den beiden nachfolgend genannten Veröffentlichungen:
-: '''(1)''' &nbsp; Abel, J.: ''Verlustlose Datenkompression auf Grundlage der Burrows-Wheeler-Transformation''. <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; In: PIK - Praxis der Informationsverarbeitung und Kommunikation, no. 3, vol. 26, S. 140-144, Sept.  2003.
+: '''(1)''' &nbsp; Abel, J.: ''Verlustlose Datenkompression auf Grundlage der Burrows-Wheeler-Transformation''. <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; In: PIK - Praxis der Informationsverarbeitung und Kommunikation, no. 3, vol. 26, S. 140&ndash;144, Sept.  2003.
-: '''(2)''' &nbsp; Abel, J.: ''Grundlagen des Burrows-Wheeler-Kompressionsalgorithmus''. <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; In: Informatik Forschung & Entwicklung, no. 2, vol. 18, S. 80-87, Jan.  2004.
+: '''(2)''' &nbsp; Abel, J.: ''Grundlagen des Burrows-Wheeler-Kompressionsalgorithmus''. <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; In: Informatik Forschung & Entwicklung, no. 2, vol. 18, S. 80&ndash;87, Jan.  2004.
@@ Zeile 36: / Zeile 36: @@
 <quiz display=simple>
-{Wie lautet die zur vorgegebenen L&ndash;Spalte zugehörige '''F&ndash;Spalte'''?
+{Wie lautet die zur vorgegebenen&nbsp; $\text{L&ndash;Spalte}$&nbsp; zugehörige&nbsp; $\text{F&ndash;Spalte}$?
-|type="[]"}
+|type="()"}
 - $\rm SEINMEINDEIN$,
 - $\rm NIIINEEEDSMN$,
@@ Zeile 43: / Zeile 43: @@
-{Wie lautet das Ergebnis der Rekonstruktion mit dem Primärindex $\underline{I = 7}$?
+{Wie lautet das Ergebnis der Rekonstruktion mit dem Primärindex&nbsp; $\underline{I = 7}$?
-|type="[]"}
+|type="()"}
 + $\rm MEINDEINSEIN$,
 - $\rm DEINSEINMEIN$,
@@ Zeile 50: / Zeile 50: @@
-{Was passiert, wenn bei der Rekonstruktion ('''BWT&ndash;Rücktransformation''') vom falschen Primärindex $\underline{I = 0}$ ausgegangen wird?
+{Was passiert, wenn bei der Rekonstruktion&nbsp; $\text{(BWT&ndash;Rücktransformation})$&nbsp; vom falschen Primärindex&nbsp; $I = 0$&nbsp; ausgegangen wird?
 |type="[]"}
 - Es ergibt sich der Originaltext, von hinten nach vorne gelesen.

@@ Zeile 3: / Zeile 3: @@
 }}
-[[Datei:P_ID2478__Inf_A_2_14.png|right|Zu analysierendes BWT-Ergebnis]]
+[[Datei:P_ID2478__Inf_A_2_14.png|right|frame|Zu analysierendes BWT-Ergebnis]]
-Die ''Burrows&ndash;Wheeler&ndash;Transformation'' &ndash; abgekürzt BWT &ndash; 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.
+Die ''Burrows&ndash;Wheeler&ndash;Transformation'' &ndash; abgekürzt '''BWT''' &ndash; 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&times;N$&ndash;Matrix erzeugt, wobei sich jede Zeile dieser ersten BWT&ndash;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&ndash;Matrix, die so genannte <i>L&ndash;Spalte</i>.
+* Danach wird die Matrix lexikografisch (ohne Sonderzeichen: &nbsp; alphabetisch) sortiert. Das Ergebnis der BWT ist die letzte Zeile der neuen BWT&ndash;Matrix, die so genannte <i>L&ndash;Spalte</i>   (von &bdquo;Last&rdquo;, &nbsp; letzte Zeile der BWT&ndash;Matrix).
-* Weiter wird in dieser Aufgabe auf die <i>F&ndash;Spalte</i> (von &bdquo;First&rdquo;, erste Zeile der BWT&ndash;Matrix) Bezug genommen, die man für die inverse Burrows&ndash;Wheeler&ndash;Transformation benötigt&nbsp;&#8658;&nbsp;Rekonstruktion des Originaltextes aus der L&ndash;Spalte  (von &bdquo;Last&rdquo;, Letzte Zeile der BWT&ndash;Matrix) .
+* Weiter wird in dieser Aufgabe auf die <i>F&ndash;Spalte</i> (von &bdquo;First&rdquo;, erste Zeile der BWT&ndash;Matrix) Bezug genommen, die man für die inverse Burrows&ndash;Wheeler&ndash;Transformation benötigt &nbsp; &#8658; &nbsp; Rekonstruktion des Originaltextes aus der L&ndash;Spalte.
 * Für die inverse BWT benötigt man ferner den so genannten <i>Primärindex</i> $I$. Dieser gibt diejenige Zeile der BWT&ndash;Matrix an, in welcher der Algorithmus gestartet werden muss.
-Die Grafik zeigt das Ergebnis einer BWT, genauer gesagt deren L&ndash;Spalte. Aus dieser soll der Originaltext entsprechend der Beschreibung auf der Theorieseite [[Informationstheorie/Weitere_Quellencodierverfahren#Burrows.E2.80.93Wheeler.E2.80.93Transformation|Burrows&ndash;Wheeler&ndash;Transformation]] rekonstruiert werden, wobei in Teilaufgabe (2) von Primärindex $I = 7$ und in Teilaufgabe (3) von $I = 0$ auszugehen ist.
+Die Grafik zeigt das Ergebnis einer BWT, genauer gesagt deren L&ndash;Spalte.

@@ Zeile 61: / Zeile 61: @@
 ===Musterlösung===
 {{ML-Kopf}}
-<b>1.</b>&nbsp;&nbsp;Man bezeichnet die erste Spalte der BWT&ndash;Matrix auch als F&ndash;Spalte und die letzte Spalte als L&ndash;Spalte (von &bdquo;<i>First</i>&rdquo; bzw. &bdquo;<i>Last</i>&rdquo;). Weitergegeben zur nächsten Codierstufe wird nur die L&ndash;Spalte. Die F&ndash;Spalte, die zur Rücktransformation ebenfalls benötigt wird, ergibt sich aus der L&ndash;Spalte durch lexikografisches Sortieren &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>.
+'''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>:
-:* Man beginnt die Decodierung mit der Zeile  <i>I</i> = 7 der F&ndash;Spalte. Der Inhalt ist  &bdquo;M&rdquo;.
+'''(2)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>: <b>MEINDEINSEIN</b>, wie aus der linken Darstellung der folgenden Grafik hervorgeht. Beachten Sie, dass die obersten Zeile jeweils für die Zeilennummer <i>I</i> = 0 steht. Zur Erklärung:
-:* Man sucht das entsprechende &bdquo;M&rdquo; in der L&ndash;Spalte und findet es in der Zeilennummer &bdquo;1&rdquo;.
+:[[Datei:P_ID2479__Inf_A_2_14b.png|BW–Rücktransformation mit <i>I</i> = 7 bzw. <i>I</i> = 0]]
-:* Von Zeile 1  der L&ndash;Spalte geht man horizontal zur F&ndash;Spalte  und findet das Symbol &bdquo;E&rdquo;.
+'''(3)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>: <b>DEINSEINMEIN</b>, wie aus der rechten Grafik hervorgeht.
-:* In gleicher Weise findet man das dritte Ausgabesymbol &bdquo;I&rdquo; in der Zeile 4  der F&ndash;Spalte.
+'''(4)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>:
+*Bei der BWT sind hier vier Zeichen gleich ihren Vorgängern, im Original kein einziges.
-:* Der Decodieralgorithmus endet mit dem Ausgabesymbol &bdquo;N&rdquo; in der drittletzten Zeile.
+*In der F&ndash;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 <b>E</b>,dreimal <b>I</b>, dreimal <b>N</b> sowie je einmal <b>D</b>, <b>M</b> und <b>S</b>).
 {{ML-Fuß}}