Aufgaben:Aufgabe 2.13Z: Kombination BWT & ''Move-to-Front'': Unterschied zwischen den Versionen
Zeile 16: | Zeile 16: | ||
* 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 Aufgabe | + | * 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 <i>i</i> = 1 folgende Zuordnung gilt: | * 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: | ||
: <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. | ||
Zeile 26: | Zeile 25: | ||
*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Weitere_Quellencodierverfahren|Weitere Quellencodierverfahren]]. | *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]]. | *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. |
− | |||
− | |||
Version vom 28. Mai 2017, 15:00 Uhr
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.