Aufgaben:Aufgabe 2.13Z: Kombination BWT & ''Move-to-Front'': Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(7 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2480__Inf_Z_2_14.png|right|]]
+
[[Datei:P_ID2480__Inf_Z_2_14.png|right|Schema für die Burrows–Wheeler–Datenkomprimierung]]
Wir beziehen und auf die letzte Theorieseite von Kapitel 2.4 und betrachten das rachts skizzierte Codiersystem, bestehend aus den Blöcken.
+
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.
 +
* <i>Burrows&ndash;Wheeler&ndash;Transformation</i> (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:  $\{$<b>D</b>, <b>E</b>, <b>I</b>, <b>M</b>, <b>N</b>, <b>S</b>$\}$;
 +
* <i>Move&ndash;to&ndash;Front</i> (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>RLC0</i> &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;
 +
* <i>Huffman</i> gemäß der Beschreibung im Kapitel [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]]; häufige Zeichen werden durch kurze Binärfolgen dargestellt, seltene durch lange.
  
:* <i>Burrows&ndash;Wheeler&ndash;Transformation</i> (BWT) gemäß der Beschreibung in Aufgabe A2.14; Zeichenmengen am Ein&ndash; und Ausgang sind gleich:  {<b>D</b>, <b>E</b>, <b>I</b>, <b>M</b>, <b>N</b>, <b>S</b>};
 
 
:* <i>Move&ndash;to&ndash;Front</i> (MTF), ein Sortieralgorithmus, der eine gleich lange Zeichenfolge (im Beispiel <i>N</i> = 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>RLC0</i> &ndash; eine Lauflängencodierung speziell für die nach BWT und MTF (möglichst) häufige Null; alle anderen Indizes werden durch RLC0 nicht verändert;
 
 
:* <i>Huffman</i> als Beispiel eines Entropiecodierers gemäß der Beschreibung in Kapitel 2.3; häufige Zeichen werden durch kurze Binärfolgen dargestellt, seltene durch lange.
 
  
 
Der MTF&ndash;Algorithmus lässt sich wie folgt beschreiben:
 
Der MTF&ndash;Algorithmus lässt sich wie folgt beschreiben:
  
:* Bei <i>M</i> = 6 Eingangssymbolen ist die Ausgangsfolge des MTF eine Aneinanderreihung von Indizes <i>I</i> aus der Menge <i>I</i>&nbsp;=&nbsp;{<b>0</b>, <b>1</b>, <b>2</b>, <b>3</b>, <b>4</b>, <b>5</b>}.
+
* Bei $M = 6$ Eingangssymbolen ist die Ausgangsfolge des MTF eine Aneinanderreihung von Indizes aus der Menge <i>I</i>$ = \{$<b>0</b>, <b>1</b>, <b>2</b>, <b>3</b>, <b>4</b>, <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 MTF&ndash;Algorithmus werden die möglichen Eingangssymbole lexikografisch sortiert und den folgenden Indizes zugeordnet:
+
: &nbsp; &nbsp;  &nbsp; &nbsp;  <b>D</b> &#8594; <b>0</b>, <b>E</b> &#8594; <b>1</b>, <b>I</b> &#8594; <b>2</b>, <b>M</b> &#8594; <b>3</b>, <b>N</b> &#8594; <b>4</b>, <b>S</b> &#8594; <b>5</b>.
:     <b>D</b> &#8594; <b>0</b>, <b>E</b> &#8594; <b>1</b>, <b>I</b> &#8594; <b>2</b>, <b>M</b> &#8594; <b>3</b>, <b>N</b> &#8594; <b>4</b>, <b>S</b> &#8594; <b>5</b>.
+
* Der MTF&ndash;Eingabestring sei hier <b>N<sub>&nbsp;</sub>M<sub>&nbsp;</sub>S<sub>&nbsp;</sub>D<sub>&nbsp;</sub>E<sub>&nbsp;</sub>E<sub>&nbsp;</sub>E<sub>&nbsp;</sub>N<sub>&nbsp;</sub>I<sub>&nbsp;</sub>I<sub>&nbsp;</sub>I<sub>&nbsp;</sub>N</b>. Dies war das BWT&ndash;Ergebnis in der [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Aufgabe 2.13]]. Das erste <b>N</b> wird gemäß Voreinstellung mit <i>I</i> = <b>4</b> dargestellt.
 +
* Anschließend wird das <b>N</b> in der Sortierung an den Anfang gestellt, so dass nach dem Codierschritt $i = 1$ folgende Zuordnung gilt:
 +
:  &nbsp; &nbsp;  &nbsp; &nbsp;      <b>N</b> &#8594; <b>0</b>, <b>D</b> &#8594; <b>1</b>, <b>E</b> &#8594; <b>2</b>, <b>I</b> &#8594; <b>3</b>, <b>M</b> &#8594; <b>4</b>, <b>S</b> &#8594; <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.
  
:* Der MTF&ndash;Eingabestring sei hier <b>N<sub>&nbsp;</sub>M<sub>&nbsp;</sub>S<sub>&nbsp;</sub>D<sub>&nbsp;</sub>E<sub>&nbsp;</sub>E<sub>&nbsp;</sub>E<sub>&nbsp;</sub>N<sub>&nbsp;</sub>I<sub>&nbsp;</sub>I<sub>&nbsp;</sub>I<sub>&nbsp;</sub>N</b>. Dies war das BWT&ndash;Ergebnis in der Aufgabe A2.14. Das erste <b>N</b> wird gemäß Voreinstellung mit <i>I</i> = <b>4</b> dargestellt.
 
  
:* Anschließend wird das <b>N</b> in der Sortierung an den Anfang gestellt, so dass nach dem Codierschritt <i>i</i> = 1 folgende Zuordnung gilt:
+
''Hinweise:''
:    <b>N</b> &#8594; <b>0</b>, <b>D</b> &#8594; <b>1</b>, <b>E</b> &#8594; <b>2</b>, <b>I</b> &#8594; <b>3</b>, <b>M</b> &#8594; <b>4</b>, <b>S</b> &#8594; <b>5</b>.
+
*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&ndash;Wheeler&ndash;Transformation]].
:* 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.
+
*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.
 
 
<b>Hinweis:</b> Die Aufgabe gehört zu Kapitel 2.4. Informationen zum Huffman&ndash;Code finden Sie in Kapitel 2.3. Für die Lösung dieser Aufgabe sind diese Informationen aber nicht erforderlich.
 
  
  
Zeile 36: Zeile 33:
 
{Welche Aussagen gelten für den Block &bdquo;BWT&rdquo; des Codiersystems?
 
{Welche Aussagen gelten für den Block &bdquo;BWT&rdquo; des Codiersystems?
 
|type="[]"}
 
|type="[]"}
+ Die Eingangszeichenmenge ist {<b>D</b>, <b>E</b>, <b>I</b>, <b>M</b>, <b>N</b>, <b>S</b>}.
+
+ Die Eingangszeichenmenge ist $\{$<b>D</b>, <b>E</b>, <b>I</b>, <b>M</b>, <b>N</b>, <b>S</b>$\}$.
+ Die Ausgangszeichenmenge ist {<b>D</b>, <b>E</b>, <b>I</b>, <b>M</b>, <b>N</b>, <b>S</b>}.
+
+ Die Ausgangszeichenmenge ist $\{$<b>D</b>, <b>E</b>, <b>I</b>, <b>M</b>, <b>N</b>, <b>S</b>$\}$.
- In der Ausgangsfolge treten alle <i>M</i> = 6 Zeichen gruppiert auf.
+
- In der Ausgangsfolge treten alle $M = 6$ Zeichen gruppiert auf.
  
  
 
{Welche Aussagen gelten für den Block &bdquo;MTF&rdquo;  des Codiersystems?
 
{Welche Aussagen gelten für den Block &bdquo;MTF&rdquo;  des Codiersystems?
 
|type="[]"}
 
|type="[]"}
- Die Ausgangszeichenmenge ist {<b>D</b>, <b>E</b>, <b>I</b>, <b>M</b>, <b>N</b>, <b>S</b>}.
+
- Die Ausgangszeichenmenge ist $\{$<b>D</b>, <b>E</b>, <b>I</b>, <b>M</b>, <b>N</b>, <b>S</b>$\}$.
+ Die Ausgangszeichenmenge ist {<b>0</b>, <b>1</b>, <b>2</b>, <b>3</b>, <b>4</b>, <b>5</b>}.
+
+ Die Ausgangszeichenmenge ist $\{$<b>0</b>, <b>1</b>, <b>2</b>, <b>3</b>, <b>4</b>, <b>5</b>$\}$.
+ Die MTF&ndash;Ausgangsfolge hat die Länge <i>N</i> = 12.
+
+ Die MTF&ndash;Ausgangsfolge hat die Länge $N = 12$.
  
  
Zeile 74: Zeile 71:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
<b>1.</b>&nbsp;&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. <b>E</b> und <b>I</b> treten zwar gruppiert auf, aber nicht die <b>N</b>&ndash;Zeichen.
  
<b>2.</b>&nbsp;&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.
+
'''(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.
 +
*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.
 +
*Allerdings nicht durch einfaches <i>Mapping</i>, sondern durch einen Algorithmus, der nachfolgend skizziert wird.
  
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. Allerdings nicht durch einfaches <i>Mapping</i>, sondern durch einen Algorithmus, der nachfolgend skizziert wird.
+
'''(3)'''&nbsp; Die folgende Tabelle zeigt den MTF&ndash;Algorithmus. Der Schritt <i>i</i>&nbsp;=&nbsp;0 (rote Hinterlegung) gibt die Vorbelegung an. Die Eingabe der MTF ist gelb hinterlegt, die Ausgabe grün. Richtig ist der <u>Lösungsvorschlag 2</u>:
 +
* Im Schritt <i>i</i> = 1 wird das Eingangszeichen <b>N</b> entsprechend der Spalte <i>i</i> = 0 durch den Index <i>I</i> = <b>4</b> dargestellt. Anschließend wird <b>N</b> nach vorne sortiert, während die Reihenfolge der anderen Zeichen gleich bleibt.
 +
* Das Eingangszeichen <b>M</b> im zweiten Schritt erhält entsprechend der Spalte <i>i</i> = 1 ebenfalls den Index <i>I</i> = <b>4</b>. In gleicher Weise macht man weiter bis zum 12. Zeichen <b>N</b>, dem der Index <i>I</i> = <b>1</b> zugeordnet wird.
 +
*Man erkennt aus obiger Tabelle weiter, dass zu den Zeitpunkten <i>i</i> = 6, <i>i</i>&nbsp;=&nbsp;7, <i>i</i> = 10 und <i>i</i> = 11 der Ausgabeindex jeweils <i>I</i> = <b>0</b> ist.
  
<b>3.</b>&nbsp;&nbsp;Die folgende Tabelle zeigt den MTF&ndash;Algorithmus. Der Schritt <i>i</i>&nbsp;=&nbsp;0 (rote Hinterlegung) gibt die Vorbelegung an. Die Eingabe der MTF ist gelb hinterlegt, die Ausgabe grün.
+
:[[Datei:P_ID2481__Inf_Z_2_14b.png|Beispiel für den MTF–Algorithmus]]
[[Datei:P_ID2481__Inf_Z_2_14b.png|center|]]
 
:* Im Schritt <i>i</i> = 1 wird das Eingangszeichen <b>N</b> entsprechend der Spalte <i>i</i> = 0 durch den Index <i>I</i> = <b>4</b> dargestellt. Anschließend wird <b>N</b> nach vorne sortiert, während die Reihenfolge der anderen Zeichen gleich bleibt.
 
  
:* Das Eingangszeichen <b>M</b> im zweiten Schritt erhält entsprechend der Spalte <i>i</i> = 1 ebenfalls den Index <i>I</i> = <b>4</b>. In gleicher Weise macht man weiter bis zum 12. Zeichen <b>N</b>, dem der Index <i>I</i> = <b>1</b> zugeordnet wird.
+
'''(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.
  
Richtig ist <u>Lösungsvorschlag 2</u>. Man erkennt aus obiger Tabelle weiter, dass zu den Zeitpunkten <i>i</i> = 6, <i>i</i>&nbsp;=&nbsp;7, <i>i</i> = 10 und <i>i</i> = 11 der Ausgabeindex jeweils <i>I</i> = <b>0</b> ist.
+
'''(5)'''&nbsp; <u>Alle Aussagen</u> sind richtig. Nähere Angaben zum Huffman&ndash;Algorithmus finden Sie im Kapitel &bdquo;Entropiecodierung nach Huffman&rdquo;.
 
 
<b>4.</b>&nbsp;&nbsp;Richtig sind die <u>Aussagen 1 und 2</u>. Die Vorverarbeitungsschritte BWT und MTF haben lediglich die Aufgabe, möglichst viele Nullen zu generieren.
 
 
 
<b>5.</b>&nbsp;&nbsp;<u>Alle Aussagen</u> sind richtig. Nähere Angaben zum Huffman&ndash;Algorithmus finden Sie im Kapitel 2.3.
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
 
 
 
[[Category:Aufgaben zu Informationstheorie|^2.4 Weitere Quellencodierverfahren^]]
 

Aktuelle Version vom 8. Oktober 2018, 11:06 Uhr

Schema für die Burrows–Wheeler–Datenkomprimierung

Wir beziehen uns auf die Theorieseite 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 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 „RLC0” nicht verändert;
  • Huffman gemäß der Beschreibung im Kapitel 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:
        D0, E1, I2, M3, N4, S5.
  • Der MTF–Eingabestring sei hier N M S D E E E N I I I N. Dies war das BWT–Ergebnis in der 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:
        N0, D1, E2, I3, M4, S5.
  • 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:


Fragebogen

1

Welche Aussagen gelten für den Block „BWT” des Codiersystems?

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.

2

Welche Aussagen gelten für den Block „MTF” des Codiersystems?

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$.

3

Wie lautet die MTF–Ausgangsfolge?

230000100405,
445340045001,
543120345123.

4

Welche Aussagen gelten für den Block „RLC0” des Codiersystems?

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

5

Welche Aussagen gelten für den abschließenden Block „Huffman”?

Die Ausgangsfolge ist binär.
Er bewirkt eine möglichst kleine mittlere Codewortlänge.
Die Dimensionierung richtet sich nach den anderen Blöcken.


Musterlösung

(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.
Beispiel für den MTF–Algorithmus

(4)  Richtig sind die Aussagen 1 und 2. Die Vorverarbeitungen „BWT” und „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 „Entropiecodierung nach Huffman”.