Difference between revisions of "Aufgaben:Aufgabe 2.13Z: Kombination BWT & ''Move-to-Front''"
Line 13: | Line 13: | ||
Der MTF–Algorithmus lässt sich wie folgt beschreiben: | 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 $ | + | * 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–Algorithmus werden die möglichen Eingangssymbole lexikografisch sortiert und den folgenden Indizes zugeordnet: | * Vor Beginn des eigentlichen MTF–Algorithmus werden die möglichen Eingangssymbole lexikografisch sortiert und den folgenden Indizes zugeordnet: | ||
: <b>D</b> → <b>0</b>, <b>E</b> → <b>1</b>, <b>I</b> → <b>2</b>, <b>M</b> → <b>3</b>, <b>N</b> → <b>4</b>, <b>S</b> → <b>5</b>. | : <b>D</b> → <b>0</b>, <b>E</b> → <b>1</b>, <b>I</b> → <b>2</b>, <b>M</b> → <b>3</b>, <b>N</b> → <b>4</b>, <b>S</b> → <b>5</b>. | ||
* Der MTF–Eingabestring sei hier <b>N<sub> </sub>M<sub> </sub>S<sub> </sub>D<sub> </sub>E<sub> </sub>E<sub> </sub>E<sub> </sub>N<sub> </sub>I<sub> </sub>I<sub> </sub>I<sub> </sub>N</b>. Dies war das BWT–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. | * Der MTF–Eingabestring sei hier <b>N<sub> </sub>M<sub> </sub>S<sub> </sub>D<sub> </sub>E<sub> </sub>E<sub> </sub>E<sub> </sub>N<sub> </sub>I<sub> </sub>I<sub> </sub>I<sub> </sub>N</b>. Dies war das BWT–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 | + | * Anschließend wird das <b>N</b> in der Sortierung an den Anfang gestellt, so dass nach dem Codierschritt $i = 1$ folgende Zuordnung gilt: |
: <b>N</b> → <b>0</b>, <b>D</b> → <b>1</b>, <b>E</b> → <b>2</b>, <b>I</b> → <b>3</b>, <b>M</b> → <b>4</b>, <b>S</b> → <b>5</b>. | : <b>N</b> → <b>0</b>, <b>D</b> → <b>1</b>, <b>E</b> → <b>2</b>, <b>I</b> → <b>3</b>, <b>M</b> → <b>4</b>, <b>S</b> → <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. Steht ein Zeichen bereits an Position <b>0</b>, so ist keine Neusortierung erforderlich. | ||
Line 33: | Line 33: | ||
{Welche Aussagen gelten für den Block „BWT” des Codiersystems? | {Welche Aussagen gelten für den Block „BWT” 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 | + | - In der Ausgangsfolge treten alle $M = 6$ Zeichen gruppiert auf. |
{Welche Aussagen gelten für den Block „MTF” des Codiersystems? | {Welche Aussagen gelten für den Block „MTF” 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–Ausgangsfolge hat die Länge | + | + Die MTF–Ausgangsfolge hat die Länge $N = 12$. |
Revision as of 15:07, 28 May 2017
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:
- 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 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 Weitere Quellencodierverfahren.
- Insbesondere wird Bezug genommen auf die Seite Burrows–Wheeler–Transformation.
- Informationen zum Huffman–Code finden Sie im Kapitel Entropiecodierung nach Huffman. Für die Lösung dieser Aufgabe sind diese Informationen aber nicht erforderlich.
Fragebogen
Musterlösung
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.
- 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.
Richtig ist Lösungsvorschlag 2. 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.
4. Richtig sind die Aussagen 1 und 2. Die Vorverarbeitungsschritte BWT und MTF haben lediglich die Aufgabe, möglichst viele Nullen zu generieren.
5. Alle Aussagen sind richtig. Nähere Angaben zum Huffman–Algorithmus finden Sie im Kapitel 2.3.