Aufgabe 2.13Z: Kombination BWT und MTF - Versionsgeschichte

Guenter am 13. August 2021 um 10:20 Uhr

2021-08-13T10:20:48Z

Guenter am 13. August 2021 um 10:05 Uhr

2021-08-13T10:05:25Z

Guenter: Guenter verschob die Seite Aufgabe 2.13Z: Kombination BWT und ''Move-to-Front'' nach Aufgabe 2.13Z: Kombination BWT und MTF

2021-07-05T12:35:23Z

Guenter verschob die Seite Aufgabe 2.13Z: Kombination BWT und ''Move-to-Front'' nach Aufgabe 2.13Z: Kombination BWT und MTF

Guenter am 28. Januar 2020 um 16:15 Uhr

2020-01-28T16:15:26Z

Guenter am 28. Januar 2020 um 15:55 Uhr

2020-01-28T15:55:23Z

Guenter am 5. Oktober 2018 um 07:04 Uhr

2018-10-05T07:04:41Z

Guenter am 5. Oktober 2018 um 06:50 Uhr

2018-10-05T06:50:26Z

Guenter am 2. Oktober 2018 um 15:02 Uhr

2018-10-02T15:02:48Z

Guenter: Guenter verschob die Seite Aufgabe 2.13Z: Kombination BWT & ''Move-to-Front'' nach Aufgabe 2.13Z: Kombination BWT und ''Move-to-Front''

2018-10-02T14:40:40Z

Guenter verschob die Seite Aufgabe 2.13Z: Kombination BWT & ''Move-to-Front'' nach Aufgabe 2.13Z: Kombination BWT und ''Move-to-Front''

Guenter: Die Seite wurde neu angelegt: „{{quiz-Header|Buchseite=Informationstheorie/Weitere Quellencodierverfahren }} Datei:P_ID2480__Inf_Z_2_14.png|right|Schema für die Burrows–Wheeler–Daten…“

2018-10-02T14:40:04Z

Die Seite wurde neu angelegt: „{{quiz-Header|Buchseite=Informationstheorie/Weitere Quellencodierverfahren }} Datei:P_ID2480__Inf_Z_2_14.png|right|Schema für die Burrows–Wheeler–Daten…“

Neue Seite

{{quiz-Header|Buchseite=Informationstheorie/Weitere Quellencodierverfahren
}}

[[Datei:P_ID2480__Inf_Z_2_14.png|right|Schema für die Burrows–Wheeler–Datenkomprimierung]]
Wir beziehen uns auf die Theorieseite [[Informationstheorie/Weitere_Quellencodierverfahren#Anwendungsszenario_f.C3.BCr_die_Burrows.E2.80.93Wheeler.E2.80.93Transformation|Anwendungsszenario für_die_Burrows-Wheeler-Transformation]] und betrachten das rechts skizzierte Codiersystem, bestehend aus den Blöcken.
* Burrows–Wheeler–Transformation (BWT) gemäß der Beschreibung in [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Aufgabe 2.13]]; die beiden Zeichenmengen am Ein– und Ausgang des BWT sind gleich: $\{$D, E, I, M, N, S$\}$;
* Move–to–Front (MTF), ein Sortieralgorithmus, der eine gleich lange Zeichenfolge (im Beispiel $N = 12$), aber mit anderem Alphabet $\{$0, 1, 2, 3, 4, 5$\}$ ausgibt;
* RLC0 – eine Lauflängencodierung speziell für die nach BWT und MTF (möglichst) häufige Null; alle anderen Indizes werden durch &bdquo;RLC0” nicht verändert;
* Huffman gemäß der Beschreibung im Kapitel [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]]; häufige Zeichen werden durch kurze Binärfolgen dargestellt, seltene durch lange.

Der MTF–Algorithmus lässt sich wie folgt beschreiben:

* Bei $M = 6$ Eingangssymbolen ist die Ausgangsfolge des MTF eine Aneinanderreihung von Indizes aus der Menge I$ = \{$0, 1, 2, 3, 4, 5$\}$.
* Vor Beginn des eigentlichen MTF–Algorithmus werden die möglichen Eingangssymbole lexikografisch sortiert und den folgenden Indizes zugeordnet:
:         D → 0, E → 1, I → 2, M → 3, N → 4, S → 5.
* Der MTF–Eingabestring sei hier N M S D E E E N I I I N. Dies war das BWT–Ergebnis in der [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Aufgabe 2.13]]. Das erste N wird gemäß Voreinstellung mit I = 4 dargestellt.
* Anschließend wird das N in der Sortierung an den Anfang gestellt, so dass nach dem Codierschritt $i = 1$ folgende Zuordnung gilt:
:         N → 0, D → 1, E → 2, I → 3, M → 4, S → 5.
* In gleicher Weise fährt man fort, bis der gesamte Eingangstext abgearbeitet ist. Steht ein Zeichen bereits an Position 0, so ist keine Neusortierung erforderlich.

''Hinweise:''
*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Weitere_Quellencodierverfahren|Weitere Quellencodierverfahren]].
*Insbesondere wird Bezug genommen auf die Seite [[Informationstheorie/Weitere_Quellencodierverfahren#Burrows.E2.80.93Wheeler.E2.80.93Transformation|Burrows–Wheeler–Transformation]].
*Informationen zum Huffman–Code finden Sie im Kapitel [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]]. Für die Lösung dieser Aufgabe sind diese Informationen aber nicht erforderlich.

===Fragebogen===

<quiz display=simple>
{Welche Aussagen gelten für den Block &bdquo;BWT” des Codiersystems?
|type="[]"}
+ Die Eingangszeichenmenge ist $\{$D, E, I, M, N, S$\}$.
+ Die Ausgangszeichenmenge ist $\{$D, E, I, M, N, S$\}$.
- In der Ausgangsfolge treten alle $M = 6$ Zeichen gruppiert auf.

{Welche Aussagen gelten für den Block &bdquo;MTF” des Codiersystems?
|type="[]"}
- Die Ausgangszeichenmenge ist $\{$D, E, I, M, N, S$\}$.
+ Die Ausgangszeichenmenge ist $\{$0, 1, 2, 3, 4, 5$\}$.
+ Die MTF–Ausgangsfolge hat die Länge $N = 12$.

{Wie lautet die MTF–Ausgangsfolge?
|type="[]"}
- 230000100405,
+ 445340045001,
- 543120345123.

{Welche Aussagen gelten für den Block &bdquo;RLC0” des Codiersystems?
|type="[]"}
+ Der Eingangswert 0 erfährt eine Sonderbehandlung.
+ Je häufiger eine 0 auftritt, um so effektiver ist dieser Block.
- Am besten wäre Pr(0) ≈ Pr(1) ≈ ... ≈ Pr(5).

{Welche Aussagen gelten für den abschließenden Block &bdquo;Huffman”?
|type="[]"}
+ Die Ausgangsfolge ist binär.
+ Er bewirkt eine möglichst kleine mittlere Codewortlänge.
+ Die Dimensionierung richtet sich nach den anderen Blöcken.

</quiz>

===Musterlösung===
{{ML-Kopf}}
'''(1)'''  Die Grafik auf der Angabenseite zeigt, dass die Lösungsvorschläge 1 und 2 richtig sind und der Vorschlag 3 falsch ist. E und I treten zwar gruppiert auf, aber nicht die N–Zeichen.

'''(2)'''  Richtig sind die Lösungsvorschläge 2 und 3:
*Die Eingangsfolge wird Zeichen für Zeichen abgearbeitet. Auch die Ausgangsfolge hat somit die Länge N = 12.
*Tatsächlich wird die Eingangsmenge {D, E, I, N, M, S} in die Ausgangsmenge {0, 1, 2, 3, 4, 5} gewandelt.
*Allerdings nicht durch einfaches Mapping, sondern durch einen Algorithmus, der nachfolgend skizziert wird.

'''(3)'''  Die folgende Tabelle zeigt den MTF–Algorithmus. Der Schritt i = 0 (rote Hinterlegung) gibt die Vorbelegung an. Die Eingabe der MTF ist gelb hinterlegt, die Ausgabe grün. Richtig ist der Lösungsvorschlag 2:
* Im Schritt i = 1 wird das Eingangszeichen N entsprechend der Spalte i = 0 durch den Index I = 4 dargestellt. Anschließend wird N nach vorne sortiert, während die Reihenfolge der anderen Zeichen gleich bleibt.
* Das Eingangszeichen M im zweiten Schritt erhält entsprechend der Spalte i = 1 ebenfalls den Index I = 4. In gleicher Weise macht man weiter bis zum 12. Zeichen N, dem der Index I = 1 zugeordnet wird.
*Man erkennt aus obiger Tabelle weiter, dass zu den Zeitpunkten i = 6, i = 7, i = 10 und i = 11 der Ausgabeindex jeweils I = 0 ist.

:[[Datei:P_ID2481__Inf_Z_2_14b.png|Beispiel für den MTF–Algorithmus]]

'''(4)'''  Richtig sind die Aussagen 1 und 2. Die Vorverarbeitungen &bdquo;BWT” und &bdquo;MTF” haben nur die Aufgabe, möglichst viele Nullen zu generieren.

'''(5)'''  Alle Aussagen sind richtig. Nähere Angaben zum Huffman–Algorithmus finden Sie im Kapitel &bdquo;Entropiecodierung nach Huffman”.
{{ML-Fuß}}

[[Category:Aufgaben zu Informationstheorie|^2.4 Weitere Quellencodierverfahren^]]

@@ Zeile 74: / Zeile 74: @@
 ===Musterlösung===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Die Grafik auf der Angabenseite zeigt, dass die <u>Lösungsvorschläge 1 und 2</u> richtig sind und der Vorschlag 3 falsch ist:
+[[Datei:P_ID2481__Inf_Z_2_14b.png|right|frame|Beispiel für den MTF–Algorithmus]]
 *$\rm E$&nbsp; und&nbsp; $\rm I$&nbsp; treten zwar gruppiert auf,
 *aber nicht die&nbsp; $\rm N$&ndash;Zeichen.
@@ Zeile 82: / Zeile 84: @@
 *Die Eingangsfolge wird Zeichen für Zeichen abgearbeitet.&nbsp; Auch die Ausgangsfolge hat somit die Länge&nbsp; $N = 12$.
 *Tatsächlich wird die Eingangsmenge&nbsp; $\{ \hspace{0.05cm}\rm D,\hspace{0.05cm}  E,\hspace{0.05cm}  I,\hspace{0.05cm}  M,\hspace{0.05cm}  N , \hspace{0.05cm} S \}$&nbsp; in die Ausgangsmenge&nbsp;  $\{ \hspace{0.05cm}\rm 0,\hspace{0.05cm}  1,\hspace{0.05cm}  2,\hspace{0.05cm}  3,\hspace{0.05cm}  4 , \hspace{0.05cm} 5 \}$&nbsp; gewandelt.
-*Allerdings nicht durch einfaches&nbsp; <i>Mapping</i>, sondern durch einen Algorithmus, der nachfolgend skizziert wird.
+*Allerdings nicht durch einfaches&nbsp; "Mapping", sondern durch einen Algorithmus, der nachfolgend skizziert wird.
+<br clear=all>
 '''(3)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
 *Die  Tabelle zeigt den MTF&ndash;Algorithmus.&nbsp; Der Schritt&nbsp; $i=0$&nbsp; (rote Hinterlegung) gibt die Vorbelegung an.&nbsp; Die Eingabe der MTF ist gelb hinterlegt, die Ausgabe grün.

@@ Zeile 4: / Zeile 4: @@
 [[Datei:P_ID2480__Inf_Z_2_14.png|right|frame|Schema für die Burrows–Wheeler–Datenkomprimierung]]
 Wir beziehen uns auf die Theorieseite&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren#Anwendungsszenario_f.C3.BCr_die_Burrows.E2.80.93Wheeler.E2.80.93Transformation|Anwendungsszenario für die Burrows-Wheeler-Transformation]]&nbsp; und betrachten das rechts skizzierte Codiersystem, bestehend aus den Blöcken.
-* <i>Burrows&ndash;Wheeler&ndash;Transformation</i>&nbsp; $\rm (BWT)$&nbsp; gemäß der Beschreibung in&nbsp; [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Aufgabe 2.13]]; die beiden Zeichenmengen am Eingang und Ausgang des BWT sind gleich: &nbsp; $\{$ $\rm D$,&nbsp; $\rm E$,&nbsp; $\rm I$,&nbsp; $\rm M$,&nbsp; $\rm N$,&nbsp; $\rm S$ $\}$;
+* "Burrows&ndash;Wheeler&ndash;Transformation"&nbsp; $\rm (BWT)$&nbsp; gemäß der Beschreibung in&nbsp; [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Aufgabe 2.13]];&nbsp; die beiden Zeichenmengen am Eingang und Ausgang des BWT sind gleich: &nbsp; $\{$ $\rm D$,&nbsp; $\rm E$,&nbsp; $\rm I$,&nbsp; $\rm M$,&nbsp; $\rm N$,&nbsp; $\rm S$ $\}$;
-* <i>Move&ndash;to&ndash;Front</i>&nbsp; $\rm (MTF)$, ein Sortieralgorithmus, der eine gleich lange Zeichenfolge&nbsp; $($im Beispiel&nbsp; $N = 12)$, aber mit anderem Alphabet&nbsp; $\{$<b>0</b>,&nbsp; <b>1</b>,&nbsp; <b>2</b>,&nbsp; <b>3</b>,&nbsp; <b>4</b>,&nbsp; <b>5</b>$\}$&nbsp; ausgibt;
+* "Move&ndash;to&ndash;Front"&nbsp; $\rm (MTF)$, ein Sortieralgorithmus,&nbsp; der eine gleich lange Zeichenfolge&nbsp; $($im Beispiel&nbsp; $N = 12)$, aber mit anderem Alphabet&nbsp; $\{$<b>0</b>,&nbsp; <b>1</b>,&nbsp; <b>2</b>,&nbsp; <b>3</b>,&nbsp; <b>4</b>,&nbsp; <b>5</b>$\}$&nbsp; ausgibt;
 * $\rm RLC0$&nbsp; &ndash; eine Lauflängencodierung speziell für die nach&nbsp; $\rm BWT$&nbsp; und&nbsp; $\rm MTF$&nbsp; (möglichst) häufige Null;&nbsp; alle anderen Indizes werden durch&nbsp; $\rm RLC0$&nbsp; nicht verändert;
-* $\rm Huffman$&nbsp; gemäß der Beschreibung im Kapitel&nbsp; [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]]; häufige Zeichen werden durch kurze Binärfolgen dargestellt und seltene durch lange.
+* $\rm Huffman$&nbsp; gemäß der Beschreibung im Kapitel&nbsp; [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]];&nbsp; häufige Zeichen werden durch kurze Binärfolgen dargestellt und seltene durch lange.
@@ Zeile 65: / Zeile 65: @@
 |type="[]"}
 + Die Ausgangsfolge ist binär.
-+ Er bewirkt eine möglichst kleine mittlere Codewortlänge.
++ Dieser Block bewirkt eine möglichst kleine mittlere Codewortlänge.
 + Die Dimensionierung richtet sich nach den anderen Blöcken.

@@ Zeile 75: / Zeile 75: @@
 {{ML-Kopf}}
 '''(1)'''&nbsp; Die Grafik auf der Angabenseite zeigt, dass die <u>Lösungsvorschläge 1 und 2</u> richtig sind und der Vorschlag 3 falsch ist:
-*$\rm E$ und $\rm I$ treten zwar gruppiert auf,
+*$\rm E$&nbsp; und&nbsp; $\rm I$&nbsp; treten zwar gruppiert auf,
-*aber nicht die $\rm N$&ndash;Zeichen.
+*aber nicht die&nbsp; $\rm N$&ndash;Zeichen.
 '''(2)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 2 und 3</u>:
-*Die Eingangsfolge wird Zeichen für Zeichen abgearbeitet. Auch die Ausgangsfolge hat somit die Länge $N = 12$.
+*Die Eingangsfolge wird Zeichen für Zeichen abgearbeitet.&nbsp; Auch die Ausgangsfolge hat somit die Länge&nbsp; $N = 12$.
-*Tatsächlich wird die Eingangsmenge $\{ \hspace{0.05cm}\rm D,\hspace{0.05cm}  E,\hspace{0.05cm}  I,\hspace{0.05cm}  M,\hspace{0.05cm}  N , \hspace{0.05cm} S \}$ in die Ausgangsmenge  $\{ \hspace{0.05cm}\rm 0,\hspace{0.05cm}  1,\hspace{0.05cm}  2,\hspace{0.05cm}  3,\hspace{0.05cm}  4 , \hspace{0.05cm} 5 \}$ gewandelt.
+*Tatsächlich wird die Eingangsmenge&nbsp; $\{ \hspace{0.05cm}\rm D,\hspace{0.05cm}  E,\hspace{0.05cm}  I,\hspace{0.05cm}  M,\hspace{0.05cm}  N , \hspace{0.05cm} S \}$&nbsp; in die Ausgangsmenge&nbsp;  $\{ \hspace{0.05cm}\rm 0,\hspace{0.05cm}  1,\hspace{0.05cm}  2,\hspace{0.05cm}  3,\hspace{0.05cm}  4 , \hspace{0.05cm} 5 \}$&nbsp; gewandelt.
-*Allerdings nicht durch einfaches <i>Mapping</i>, sondern durch einen Algorithmus, der nachfolgend skizziert wird.
+*Allerdings nicht durch einfaches&nbsp; <i>Mapping</i>, sondern durch einen Algorithmus, der nachfolgend skizziert wird.
@@ Zeile 88: / Zeile 88: @@
 '''(3)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
-*Die  Tabelle zeigt den MTF&ndash;Algorithmus. Der Schritt $i=0$ (rote Hinterlegung) gibt die Vorbelegung an. Die Eingabe der MTF ist gelb hinterlegt, die Ausgabe grün.
+*Die  Tabelle zeigt den MTF&ndash;Algorithmus.&nbsp; Der Schritt&nbsp; $i=0$&nbsp; (rote Hinterlegung) gibt die Vorbelegung an.&nbsp; Die Eingabe der MTF ist gelb hinterlegt, die Ausgabe grün.
-* Im Schritt $i=1$ wird das Eingangszeichen $\rm N$  entsprechend der Spalte $i=0$ durch den Index $I = 4$ dargestellt. Anschließend wird $\rm N$ nach vorne sortiert, während die Reihenfolge der anderen Zeichen gleich bleibt.
+* Im Schritt&nbsp; $i=1$&nbsp; wird das Eingangszeichen&nbsp; $\rm N$&nbsp;  entsprechend der Spalte&nbsp; $i=0$&nbsp; durch den Index&nbsp; $I = 4$&nbsp; dargestellt.&nbsp; Anschließend wird&nbsp; $\rm N$&nbsp; nach vorne sortiert, während die Reihenfolge der anderen Zeichen gleich bleibt.
-* Das Eingangszeichen $\rm M$ im zweiten Schritt erhält entsprechend der Spalte $i=2$ ebenfalls den Index $I = 4$. In gleicher Weise macht man weiter bis zum zwölften Zeichen $\rm N$, dem der Index $I = 1$ zugeordnet wird.
+* Das Eingangszeichen&nbsp; $\rm M$&nbsp; im zweiten Schritt erhält entsprechend der Spalte&nbsp; $i=2$&nbsp; ebenfalls den Index&nbsp; $I = 4$.&nbsp; In gleicher Weise macht man weiter bis zum zwölften Zeichen&nbsp; $\rm N$, dem der Index&nbsp; $I = 1$&nbsp; zugeordnet wird.
-*Man erkennt aus obiger Tabelle weiter, dass zu den Zeitpunkten $i=6$, $i=7$, $i=10$ und $i=11$ der Ausgabeindex jeweils $I = 0$ ist.
+*Man erkennt aus obiger Tabelle weiter, dass zu den Zeitpunkten&nbsp; $i=6$,&nbsp; $i=7$,&nbsp; $i=10$&nbsp; und&nbsp; $i=11$&nbsp; der Ausgabeindex jeweils&nbsp; $I = 0$&nbsp; ist.
 '''(4)'''&nbsp; Richtig sind die <u>Aussagen 1 und 2</u>:
 *Die Vorverarbeitungen &bdquo;BWT&rdquo; und &bdquo;MTF&rdquo;  haben nur die Aufgabe, möglichst viele Nullen zu generieren.

@@ Zeile 3: / Zeile 3: @@
 [[Datei:P_ID2480__Inf_Z_2_14.png|right|frame|Schema für die Burrows–Wheeler–Datenkomprimierung]]
-Wir beziehen uns auf die Theorieseite [[Informationstheorie/Weitere_Quellencodierverfahren#Anwendungsszenario_f.C3.BCr_die_Burrows.E2.80.93Wheeler.E2.80.93Transformation|Anwendungsszenario für die Burrows-Wheeler-Transformation]] und betrachten das rechts skizzierte Codiersystem, bestehend aus den Blöcken.
+Wir beziehen uns auf die Theorieseite&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren#Anwendungsszenario_f.C3.BCr_die_Burrows.E2.80.93Wheeler.E2.80.93Transformation|Anwendungsszenario für die Burrows-Wheeler-Transformation]]&nbsp; und betrachten das rechts skizzierte Codiersystem, bestehend aus den Blöcken.
-* <i>Burrows&ndash;Wheeler&ndash;Transformation</i> $\rm (BWT)$ gemäß der Beschreibung in [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Aufgabe 2.13]]; die beiden Zeichenmengen am Ein&ndash; und Ausgang des BWT sind gleich: &nbsp; $\{$ $\rm D$, $\rm E$, $\rm I$, $\rm M$, $\rm N$, $\rm S$ $\}$;
+* <i>Burrows&ndash;Wheeler&ndash;Transformation</i>&nbsp; $\rm (BWT)$&nbsp; gemäß der Beschreibung in&nbsp; [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Aufgabe 2.13]]; die beiden Zeichenmengen am Eingang und Ausgang des BWT sind gleich: &nbsp; $\{$ $\rm D$,&nbsp; $\rm E$,&nbsp; $\rm I$,&nbsp; $\rm M$,&nbsp; $\rm N$,&nbsp; $\rm S$ $\}$;
-* <i>Move&ndash;to&ndash;Front</i> $\rm (MTF)$, ein Sortieralgorithmus, der eine gleich lange Zeichenfolge (im Beispiel $N = 12$), aber mit anderem Alphabet $\{$<b>0</b>, <b>1</b>, <b>2</b>, <b>3</b>, <b>4</b>, <b>5</b>$\}$ ausgibt;
+* <i>Move&ndash;to&ndash;Front</i>&nbsp; $\rm (MTF)$, ein Sortieralgorithmus, der eine gleich lange Zeichenfolge&nbsp; $($im Beispiel&nbsp; $N = 12)$, aber mit anderem Alphabet&nbsp; $\{$<b>0</b>,&nbsp; <b>1</b>,&nbsp; <b>2</b>,&nbsp; <b>3</b>,&nbsp; <b>4</b>,&nbsp; <b>5</b>$\}$&nbsp; ausgibt;
-* $\rm RLC0$ &ndash; eine Lauflängencodierung speziell für die nach BWT und MTF (möglichst) häufige Null; alle anderen Indizes werden durch &bdquo;RLC0&rdquo; nicht verändert;
+* $\rm RLC0$&nbsp; &ndash; eine Lauflängencodierung speziell für die nach&nbsp; $\rm BWT$&nbsp; und&nbsp; $\rm MTF$&nbsp; (möglichst) häufige Null;&nbsp; alle anderen Indizes werden durch&nbsp; $\rm RLC0$&nbsp; nicht verändert;
-* $\rm Huffman$ gemäß der Beschreibung im Kapitel [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]]; häufige Zeichen werden durch kurze Binärfolgen dargestellt und seltene durch lange.
+* $\rm Huffman$&nbsp; gemäß der Beschreibung im Kapitel&nbsp; [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]]; häufige Zeichen werden durch kurze Binärfolgen dargestellt und seltene durch lange.
-Der MTF&ndash;Algorithmus lässt sich bei $M = 6$ Eingangssymbolen  wie folgt beschreiben:
+Der&nbsp; $\rm MTF$&ndash;Algorithmus lässt sich bei&nbsp; $M = 6$&nbsp; Eingangssymbolen  wie folgt beschreiben:
-* Die Ausgangsfolge des MTF ist eine Aneinanderreihung von Indizes aus der Menge
+* Die Ausgangsfolge des&nbsp; $\rm MTF$&nbsp; ist eine Aneinanderreihung von Indizes aus der Menge
-:&nbsp; &nbsp;  &nbsp; &nbsp;$ I = \{$<b>0</b>, <b>1</b>, <b>2</b>, <b>3</b>, <b>4</b>, <b>5</b>$\}$.
+:&nbsp; &nbsp;  &nbsp; &nbsp;$ I = \{$<b>0</b>,&nbsp; <b>1</b>,&nbsp; <b>2</b>,&nbsp; <b>3</b>,&nbsp; <b>4</b>,&nbsp; <b>5</b>$\}$.
-* Vor Beginn des eigentlichen MTF&ndash;Algorithmus werden die möglichen Eingangssymbole lexikografisch sortiert und den folgenden Indizes zugeordnet:
+* Vor Beginn des eigentlichen&nbsp; $\rm MTF$&ndash;Algorithmus werden die möglichen Eingangssymbole lexikografisch sortiert und den folgenden Indizes zugeordnet:
-: &nbsp; &nbsp;  &nbsp; &nbsp;   $\rm D$ &#8594; <b>0</b>, &nbsp; &nbsp; $\rm E$ &#8594; <b>1</b>, &nbsp; &nbsp;  $\rm I$ &#8594; <b>2</b>, &nbsp; &nbsp; $\rm M$ &#8594; <b>3</b>, &nbsp; &nbsp;  $\rm N$ &#8594; <b>4</b>,&nbsp; &nbsp;  $\rm S$ &#8594; <b>5</b>.
+: &nbsp; &nbsp;  &nbsp; &nbsp;   $\rm D$ &nbsp; &#8594; &nbsp; <b>0</b>, &nbsp; &nbsp; $\rm E$ &nbsp; &#8594; &nbsp; <b>1</b>, &nbsp; &nbsp;  $\rm I$ &nbsp; &#8594; &nbsp; <b>2</b>, &nbsp; &nbsp; $\rm M$ &nbsp; &#8594; &nbsp; <b>3</b>, &nbsp; &nbsp;  $\rm N$ &nbsp; &#8594; &nbsp; <b>4</b>,&nbsp; &nbsp;  $\rm S$ &nbsp; &#8594; &nbsp; <b>5</b>.
-* Der MTF&ndash;Eingabestring sei hier $\rm N\hspace{0.05cm}M\hspace{0.05cm}S\hspace{0.05cm}D\hspace{0.05cm}E\hspace{0.05cm}E\hspace{0.05cm}E\hspace{0.05cm}N\hspace{0.05cm}I\hspace{0.05cm}I\hspace{0.05cm}I\hspace{0.05cm}N$ . Dies war das BWT&ndash;Ergebnis in der [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Aufgabe 2.13]]. Das erste $\rm N$ wird gemäß Voreinstellung mit $I = 4$ dargestellt.
+* Der&nbsp; $\rm MTF$&ndash;Eingabestring sei hier&nbsp; $\rm N\hspace{0.05cm}M\hspace{0.05cm}S\hspace{0.05cm}D\hspace{0.05cm}E\hspace{0.05cm}E\hspace{0.05cm}E\hspace{0.05cm}N\hspace{0.05cm}I\hspace{0.05cm}I\hspace{0.05cm}I\hspace{0.05cm}N$.&nbsp; Dies war das&nbsp; $\rm BWT$&ndash;Ergebnis in der&nbsp; [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Aufgabe 2.13]].&nbsp; Das erste&nbsp; $\rm N$&nbsp; wird gemäß Voreinstellung mit&nbsp; $I = 4$&nbsp; dargestellt.
-* Anschließend wird das $\rm N$ in der Sortierung an den Anfang gestellt, so dass nach dem Codierschritt $i = 1$ die Zuordnung gilt:
+* Anschließend wird das&nbsp; $\rm N$&nbsp; in der Sortierung an den Anfang gestellt, so dass nach dem Codierschritt&nbsp; $i = 1$&nbsp; die Zuordnung gilt:
-: &nbsp; &nbsp;  &nbsp; &nbsp;   $\rm N$ &#8594; <b>0</b>, &nbsp; &nbsp; $\rm D$ &#8594; <b>1</b>, &nbsp; &nbsp;  $\rm E$ &#8594; <b>2</b>, &nbsp; &nbsp; $\rm I$ &#8594; <b>3</b>, &nbsp; &nbsp;  $\rm M$ &#8594; <b>4</b>,&nbsp; &nbsp;  $\rm S$ &#8594; <b>5</b>.
+: &nbsp; &nbsp;  &nbsp; &nbsp;   $\rm N$ &nbsp; &#8594; &nbsp; <b>0</b>, &nbsp; &nbsp; $\rm D$ &nbsp; &#8594; &nbsp; <b>1</b>, &nbsp; &nbsp;  $\rm E$ &nbsp; &#8594; &nbsp;  <b>2</b>, &nbsp; &nbsp; $\rm I$ &nbsp; &#8594; &nbsp; <b>3</b>, &nbsp; &nbsp;  $\rm M$ &nbsp; &#8594; &nbsp; <b>4</b>,&nbsp; &nbsp;  $\rm S$ &nbsp; &#8594; &nbsp; <b>5</b>.
-* In gleicher Weise fährt man fort, bis der gesamte Eingangstext abgearbeitet ist. Steht ein Zeichen bereits an Position <b>0</b>, so ist keine Neusortierung erforderlich.
+* In gleicher Weise fährt man fort, bis der gesamte Eingangstext abgearbeitet ist.&nbsp; Steht ein Zeichen bereits an Position&nbsp; <b>0</b>, so ist keine Neusortierung erforderlich.
@@ 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]].
-*Informationen zum Huffman&ndash;Code finden Sie im Kapitel [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]]. Für die Lösung dieser Aufgabe sind diese Informationen aber nicht erforderlich.
+*Informationen zum Huffman&ndash;Code finden Sie im Kapitel&nbsp;  [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]].&nbsp;  Für die Lösung der Aufgabe sind diese Informationen nicht erforderlich.
@@ Zeile 34: / Zeile 34: @@
 <quiz display=simple>
-{Welche Aussagen gelten für den Block &bdquo;BWT&rdquo; des Codiersystems?
+{Welche Aussagen gelten für den Block&nbsp; $\rm BWT$&nbsp; des Codiersystems?
 |type="[]"}
-+ Die Eingangszeichenmenge ist $\{ \hspace{0.05cm}\rm D,\hspace{0.05cm}  E,\hspace{0.05cm}  I,\hspace{0.05cm}  M,\hspace{0.05cm}  N , \hspace{0.05cm} S \}$.
++ Die Eingangszeichenmenge ist&nbsp; $\{ \hspace{0.05cm}\rm D,\hspace{0.05cm}  E,\hspace{0.05cm}  I,\hspace{0.05cm}  M,\hspace{0.05cm}  N , \hspace{0.05cm} S \}$.
 + Die Ausgangszeichenmenge ist $\{ \hspace{0.05cm}\rm D,\hspace{0.05cm}  E,\hspace{0.05cm}  I,\hspace{0.05cm}  M,\hspace{0.05cm}  N , \hspace{0.05cm} S \}$.
-- In der Ausgangsfolge treten alle $M = 6$ Zeichen gruppiert auf.
+- In der Ausgangsfolge treten alle&nbsp; $M = 6$&nbsp; Zeichen gruppiert auf.
-{Welche Aussagen gelten für den Block &bdquo;MTF&rdquo;  des Codiersystems?
+{Welche Aussagen gelten für den Block&nbsp; $\rm MTF$&nbsp;  des Codiersystems?
 |type="[]"}
-- Die Ausgangszeichenmenge ist $\{ \hspace{0.05cm}\rm D,\hspace{0.05cm}  E,\hspace{0.05cm}  I,\hspace{0.05cm}  M,\hspace{0.05cm}  N , \hspace{0.05cm} S \}$.
+- Die Ausgangszeichenmenge ist&nbsp; $\{ \hspace{0.05cm}\rm D,\hspace{0.05cm}  E,\hspace{0.05cm}  I,\hspace{0.05cm}  M,\hspace{0.05cm}  N , \hspace{0.05cm} S \}$.
-+ Die Ausgangszeichenmenge ist $\{ \hspace{0.05cm}\rm 0,\hspace{0.05cm}  1,\hspace{0.05cm}  2,\hspace{0.05cm}  3,\hspace{0.05cm}  4 , \hspace{0.05cm} 5 \}$.
++ Die Ausgangszeichenmenge ist&nbsp; $\{ \hspace{0.05cm}\rm 0,\hspace{0.05cm}  1,\hspace{0.05cm}  2,\hspace{0.05cm}  3,\hspace{0.05cm}  4 , \hspace{0.05cm} 5 \}$.
-+ Die MTF&ndash;Ausgangsfolge hat die Länge $N = 12$.
++ Die MTF&ndash;Ausgangsfolge hat die Länge&nbsp; $N = 12$.
-{Wie lautet die MTF&ndash;Ausgangsfolge?
+{Wie lautet die&nbsp; $\rm MTF$&ndash;Ausgangsfolge?
 |type="()"}
 - $\rm 230000100405$,
@@ Zeile 55: / Zeile 55: @@
-{Welche Aussagen gelten für den Block &bdquo;RLC0&rdquo;  des Codiersystems?
+{Welche Aussagen gelten für den Block&nbsp; $\rm RLC0$&nbsp;  des Codiersystems?
 |type="[]"}
-+ Der Eingangswert  $0$ erfährt eine Sonderbehandlung.
++ Der Eingangswert&nbsp;  $0$&nbsp; erfährt eine Sonderbehandlung.
-+ Je häufiger eine $0$ auftritt, um so effektiver ist dieser Block.
++ Je häufiger eine&nbsp; $0$&nbsp; auftritt, um so effektiver ist dieser Block.
-- Am besten wäre $\rm Pr(0) &asymp; Pr(1) &asymp; \text{...} &asymp; Pr(5)$.
+- Am besten wäre&nbsp; $\rm Pr(0) &asymp; Pr(1) &asymp; \text{...} &asymp; Pr(5)$.

@@ Zeile 49: / Zeile 49: @@
 {Wie lautet die MTF&ndash;Ausgangsfolge?
-|type="[]"}
+|type="()"}
 - $\rm 230000100405$,
 + $\rm 445340045001$,
@@ Zeile 74: / Zeile 74: @@
 ===Musterlösung===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Die Grafik auf der Angabenseite zeigt, dass die <u>Lösungsvorschläge 1 und 2</u> richtig sind und der Vorschlag 3 falsch ist. <b>E</b> und <b>I</b> treten zwar gruppiert auf, aber nicht die <b>N</b>&ndash;Zeichen.
+'''(1)'''&nbsp; Die Grafik auf der Angabenseite zeigt, dass die <u>Lösungsvorschläge 1 und 2</u> richtig sind und der Vorschlag 3 falsch ist:
 '''(2)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 2 und 3</u>:
-*Die Eingangsfolge wird Zeichen für Zeichen abgearbeitet. Auch die Ausgangsfolge hat somit die Länge <i>N</i> = 12.
+*Die Eingangsfolge wird Zeichen für Zeichen abgearbeitet. Auch die Ausgangsfolge hat somit die Länge $N = 12$.
-*Tatsächlich wird die Eingangsmenge {<b>D</b>, <b>E</b>, <b>I</b>, <b>N</b>, <b>M</b>, <b>S</b>} in die Ausgangsmenge  {<b>0</b>, <b>1</b>, <b>2</b>, <b>3</b>, <b>4</b>, <b>5</b>} gewandelt.
+*Tatsächlich wird die Eingangsmenge $\{ \hspace{0.05cm}\rm D,\hspace{0.05cm}  E,\hspace{0.05cm}  I,\hspace{0.05cm}  M,\hspace{0.05cm}  N , \hspace{0.05cm} S \}$ in die Ausgangsmenge  $\{ \hspace{0.05cm}\rm 0,\hspace{0.05cm}  1,\hspace{0.05cm}  2,\hspace{0.05cm}  3,\hspace{0.05cm}  4 , \hspace{0.05cm} 5 \}$ gewandelt.
 *Allerdings nicht durch einfaches <i>Mapping</i>, sondern durch einen Algorithmus, der nachfolgend skizziert wird.
-:[[Datei:P_ID2481__Inf_Z_2_14b.png|Beispiel für den MTF–Algorithmus]]
+[[Datei:P_ID2481__Inf_Z_2_14b.png|center|frame|Beispiel für den MTF–Algorithmus]]
-'''(5)'''&nbsp; <u>Alle Aussagen</u> sind richtig. Nähere Angaben zum Huffman&ndash;Algorithmus finden Sie im Kapitel &bdquo;Entropiecodierung nach Huffman&rdquo;.
+'''(5)'''&nbsp; <u>Alle Aussagen</u> sind richtig.
 {{ML-Fuß}}
 [[Category:Aufgaben zu Informationstheorie|^2.4 Weitere Quellencodierverfahren^]]