Exercise 2.13Z: Combination of BWT and MTF - Revision history

Hwang at 23:05, 12 November 2022

2022-11-12T23:05:25Z

Hwang at 15:09, 1 November 2022

2022-11-01T15:09:39Z

Guenter at 10:56, 13 August 2021

2021-08-13T10:56:51Z

Guenter at 10:42, 13 August 2021

2021-08-13T10:42:01Z

Guenter at 10:39, 13 August 2021

2021-08-13T10:39:43Z

Guenter at 12:35, 12 August 2021

2021-08-12T12:35:43Z

Noah at 20:09, 10 August 2021

2021-08-10T20:09:52Z

Noah at 20:25, 9 August 2021

2021-08-09T20:25:10Z

Noah at 20:17, 9 August 2021

2021-08-09T20:17:06Z

Noah at 12:48, 9 August 2021

2021-08-09T12:48:43Z

@@ Line 3: / Line 3: @@
 [[File:EN_Inf_Z_2_14b.png|right|frame|Scheme for Burrows-Wheeler data compression]]
-We refer to the theory page&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Application_scenario_for_the_Burrows-Wheeler_transformation|Application Scenario for the Burrows-Wheeler Transform]]&nbsp; and consider the coding system sketched on the right, consisting of the blocks
+We refer to the theory section&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Application_scenario_for_the_Burrows-Wheeler_transformation|Application Scenario for the Burrows-Wheeler Transform]]&nbsp; and consider the coding system sketched on the right, consisting of the blocks
 * "Burrows&ndash;Wheeler Transform"</i>&nbsp; $\rm (BWT)$&nbsp; as described in&nbsp; [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Exercise 2.13]];&nbsp; the character sets at the input and the output of the BWT are the same: &nbsp; $\{$ $\rm D$,&nbsp; $\rm E$,&nbsp; $\rm I$,&nbsp; $\rm M$,&nbsp; $\rm N$,&nbsp; $\rm S$ $\}$;
 * "Move&ndash;to&ndash;Front"&nbsp; $\rm (MTF)$, a sorting algorithm that outputs a string of the same length&nbsp; $($&nbsp; $N = 12$&nbsp; in the example$)$,&nbsp; but with a different 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>$\}$;
@@ Line 26: / Line 26: @@
 <u>Hints:</u>
 *The exercise belongs to the chapter&nbsp; [[Information_Theory/Further_Source_Coding_Methods|Further Source Coding Methods]].
-*In particular, reference is made to the page&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation|Burrows&ndash;Wheeler Transformation]].
+*In particular, reference is made to the section&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation|Burrows&ndash;Wheeler Transformation]].
 *Information on the Huffman code can be found in the chapter&nbsp;  [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy Coding according to Huffman]].&nbsp;  This information is not necessary for the solution of the task.
@@ Line 73: / Line 73: @@
 {{ML-Kopf}}
 [[File:EN_Inf_Z_2_14.png|right|frame|Example of the MTF algorithm]]
-'''(1)'''&nbsp; The graph on the information page shows that <u>solution suggestions 1 and 2</u> are correct and suggestion 3 is incorrect:
+'''(1)'''&nbsp; The graph on the information section shows that <u>solution suggestions 1 and 2</u> are correct and suggestion 3 is incorrect:
 *$\rm E$&nbsp; and&nbsp; $\rm I$&nbsp; occur grouped together,
 *but not the&nbsp; $\rm N$&nbsp; characters.

@@ Line 63: / Line 63: @@
 |type="[]"}
 + The initial sequence is binary.
-+ It causes the smallest possible average codeword length.
++ It causes the smallest possible average code word length.
 + The dimensioning depends on the other blocks.

@@ Line 72: / Line 72: @@
 ===Solution===
 {{ML-Kopf}}
 '''(1)'''&nbsp; The graph on the information page shows that <u>solution suggestions 1 and 2</u> are correct and suggestion 3 is incorrect:
-*$\rm E$&nbsp; und&nbsp; $\rm I$&nbsp; treten zwar gruppiert auf,
+*$\rm E$&nbsp; and&nbsp; $\rm I$&nbsp; occur grouped together,
-*aber nicht die&nbsp; $\rm N$&ndash;Zeichen.
+*but not the&nbsp; $\rm N$&nbsp; characters.
 '''(2)'''&nbsp;<u>Proposed solutions 2 and 3</u> are correct:
-*The input sequence is processed character by character.&nbsp; Thus, the output sequence also has the length&nbsp; $N = 12$.
+*The input sequence is processed&nbsp; "character by character".&nbsp; <br>Thus, the output sequence also has the length&nbsp; $N = 12$.
-*In fact, the input set&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; is converted into the output set.
+*In fact, the input set&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; is converted into the output set&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 \}$.
-*However, not by simple&nbsp; <i>mapping</i>, but by an algorithm which is outlined below.
+*However, not by simple&nbsp; "mapping",&nbsp; but by an algorithm which is outlined below.
+<br clear=all>
 '''(3)'''&nbsp; Correct is <u>solution suggestion 2</u>:
-*The table shows the MTF algorithm.&nbsp; The step&nbsp; $i=0$&nbsp; (red background) indicates the preassignment.&nbsp; The input of the MTF is highlighted in yellow, the output in green.
+*The table shows the MTF algorithm.&nbsp; The step&nbsp; $i=0$&nbsp; (red background) indicates the preassignment.&nbsp; The MTF input is highlighted in yellow, the output in green.
-* In step&nbsp; $i=1$&nbsp;, the input character&nbsp; $\rm N$&nbsp; corresponding to column&nbsp; $i=0$&nbsp; is represented by index&nbsp; $I = 4$&nbsp;.&nbsp; Subsequently,&nbsp; $\rm N$&nbsp; is sorted to the front, while the order of the other characters remains the same.
+* In step&nbsp; $i=1$,&nbsp; the input character&nbsp; $\rm N$&nbsp; corresponding to column&nbsp; $i=0$&nbsp; is represented by index&nbsp; $I = 4$&nbsp;.&nbsp; Subsequently,&nbsp; $\rm N$&nbsp; is sorted to the front, while the order of the other characters remains the same.
-*The input character&nbsp; $\rm M$&nbsp; in the second step is also given the index&nbsp; $I = 4$ according to column&nbsp; $i=2$&nbsp;.&nbsp; One continues in the same way until the twelfth character&nbsp; $\rm N$, to which the index&nbsp; $I = 1$&nbsp; is assigned.
+*The input character&nbsp; $\rm M$&nbsp; in the second step is also given the index&nbsp; $I = 4$&nbsp; according to column&nbsp; $i=2$&nbsp;.&nbsp; One continues in the same way until the twelfth character&nbsp; $\rm N$, to which the index&nbsp; $I = 1$&nbsp; is assigned.
 *You can see from the above table that at the times&nbsp; $i=6$,&nbsp; $i=7$,&nbsp; $i=10$&nbsp; and&nbsp; $i=11$&nbsp; the output index is&nbsp; $I = 0$&nbsp;.
-'''(4)'''&nbsp; <u>Statements 1 and 2</u> are correct:
+'''(4)'''&nbsp; <u>Statements 1 and 2</u>&nbsp; are correct:
-*The preprocessings "BWT" and "MTF" only have the task to generate as many zeros as possible.
+*The preprocessings&nbsp; "BWT"&nbsp; and&nbsp; "MTF"&nbsp; only have the task to generate as many zeros as possible.
-'''(5)'''&nbsp; <u>All statements</u> are correct.
+'''(5)'''&nbsp; <u>All statements</u>&nbsp; are correct.
-*You can find more information on the Huffman algorithm in the chapter "Entropy coding according to Huffman".
+*You can find more information on the Huffman algorithm in the chapter&nbsp; "Entropy coding according to Huffman".
 {{ML-Fuß}}
 [[Category:Information Theory: Exercises|^2.4 Further Source Coding Methods^]]

@@ Line 36: / Line 36: @@
 + The input character set is&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 \}$.
 + The output character set is $\{ \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 the output sequence, allnbsp; $M = 6$&nbsp; characters occur grouped together.
+- In the output sequence, all&nbsp; $M = 6$&nbsp; characters occur grouped together.

@@ Line 3: / Line 3: @@
 [[File:EN_Inf_Z_2_14b.png|right|frame|Scheme for Burrows-Wheeler data compression]]
-We refer to the theory page&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Application_scenario_for_the_Burrows-Wheeler_transformation|Application Scenario for the Burrows-Wheeler Transform]]&nbsp; and consider the coding system sketched on the right, consisting of the blocks.
+We refer to the theory page&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Application_scenario_for_the_Burrows-Wheeler_transformation|Application Scenario for the Burrows-Wheeler Transform]]&nbsp; and consider the coding system sketched on the right, consisting of the blocks
-* <i>Burrows&ndash;Wheeler&ndash;Transformation</i>&nbsp; $\rm (BWT)$&nbsp; as described in&nbsp; [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Exercise 2.13]]; the two character sets at the input and output of the BWT are the same: &nbsp; $\{$ $\rm D$,&nbsp; $\rm E$,&nbsp; $\rm I$,&nbsp; $\rm M$,&nbsp; $\rm N$,&nbsp; $\rm S$ $\}$;
+* "Burrows&ndash;Wheeler Transform"</i>&nbsp; $\rm (BWT)$&nbsp; as described in&nbsp; [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Exercise 2.13]];&nbsp; the character sets at the input and the output of the BWT are the same: &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)$, a sorting algorithm that outputs a string of the same length&nbsp; $($&nbsp; $N = 12 in the example)$, but with a different 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;;
+* "Move&ndash;to&ndash;Front"&nbsp; $\rm (MTF)$, a sorting algorithm that outputs a string of the same length&nbsp; $($&nbsp; $N = 12$&nbsp; in the example$)$,&nbsp; but with a different 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>$\}$;
-* $\rm RLC0$&nbsp; &ndash; a run-length encoding specifically for zero, which is (as) frequent according to&nbsp; $\rm BWT$&nbsp; and&nbsp; $\rm MTF$&nbsp; ;&nbsp; all other indices are not changed by&nbsp; $\rm RLC0$&nbsp;;
+* $\rm RLC0$&nbsp; &ndash; a run-length encoding specifically for&nbsp; <b>0</b>, which is (as) frequent according to&nbsp; $\rm BWT$&nbsp; and&nbsp; $\rm MTF$;&nbsp;  all other indices are not changed by&nbsp; $\rm RLC0$&nbsp;;
 * $\rm Huffman$&nbsp; as described in the chapter&nbsp; [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy coding according to Huffman]]; frequent characters are represented by short binary sequences and rare ones by long ones.
-The&nbsp; $\rm MTF$&ndash;algorithm can be described as follows for&nbsp; $M = 6$&nbsp; input symbols:
+The&nbsp; $\rm MTF$&nbsp; algorithm can be described as follows for&nbsp; $M = 6$&nbsp; input symbols:
 * The output sequence of the&nbsp; $\rm MTF$&nbsp; is a string of indices from the set
@@ Line 24: / Line 24: @@
-Hints:
+<u>Hints:</u>
-*The exercise belongs to the chapter&nbsp;  [[Information_Theory/Weitere_Quellencodierverfahren|Other source coding methods]].
+*The exercise belongs to the chapter&nbsp; [[Information_Theory/Further_Source_Coding_Methods|Further Source Coding Methods]].
-*In particular, reference is made to the page&nbsp;  [[Information_Theory/Weitere_Quellencodierverfahren#Burrows.E2.80.93Wheeler_transformation|Burrows&ndash;Wheeler Transformation]].
+*In particular, reference is made to the page&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation|Burrows&ndash;Wheeler Transformation]].
 *Information on the Huffman code can be found in the chapter&nbsp;  [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy Coding according to Huffman]].&nbsp;  This information is not necessary for the solution of the task.

← Older revision		Revision as of 12:35, 12 August 2021
Line 1:		Line 1:
−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Weitere Quellencodierverfahren~~	+	{{quiz-Header\|Buchseite=Information_Theory/Further_Source_Coding_Methods
	}}		}}

@@ Line 32: / Line 32: @@
 <quiz display=simple>
-{Welche Aussagen gelten für den Block&nbsp; $\rm BWT$&nbsp; des Codiersystems?
+{Which statements are true for block&nbsp; $\rm BWT$&nbsp; of the coding system?
 |type="[]"}
-+ 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 \}$.
++ The input character set is&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 \}$.
++ The output character set is $\{ \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&nbsp; $M = 6$&nbsp; Zeichen gruppiert auf.
+- In the output sequence, allnbsp; $M = 6$&nbsp; characters occur grouped together.
-{Welche Aussagen gelten für den Block&nbsp; $\rm MTF$&nbsp;  des Codiersystems?
+{Which statements are true for the block&nbsp; $\rm MTF$&nbsp; of the coding system?
 |type="[]"}
-- 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 \}$.
+- The output character set is&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&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 \}$.
++ The output character set is&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&nbsp; $N = 12$.
++ The MTF output sequence has length&nbsp; $N = 12$.
-{Wie lautet die&nbsp; $\rm MTF$&ndash;Ausgangsfolge?
+{What is the&nbsp; $\rm MTF$ output sequence?
 |type="()"}
 - $\rm 230000100405$,
@@ Line 53: / Line 53: @@
-{Welche Aussagen gelten für den Block&nbsp; $\rm RLC0$&nbsp;  des Codiersystems?
+{Which statements apply to block&nbsp; $\rm RLC0$&nbsp; of the coding system?
 |type="[]"}
-+ Der Eingangswert&nbsp;  $0$&nbsp; erfährt eine Sonderbehandlung.
++ The input value&nbsp;  $0$&nbsp; receives special treatment
-+ Je häufiger eine&nbsp; $0$&nbsp; auftritt, um so effektiver ist dieser Block.
++ The more often a&nbsp; $0$&nbsp; occurs, the more effective this block is.
-- Am besten wäre&nbsp; $\rm Pr(0) &asymp; Pr(1) &asymp; \text{...} &asymp; Pr(5)$.
+- The best would be&nbsp; $\rm Pr(0) &asymp; Pr(1) &asymp; \text{...} &asymp; Pr(5)$.
-{Welche Aussagen gelten für den abschließenden Block "Huffman"?
+{Which statements are true for the final block "Huffman"?
 |type="[]"}
-+ Die Ausgangsfolge ist binär.
++ The initial sequence is binary.
-+ Er bewirkt eine möglichst kleine mittlere Codewortlänge.
++ It causes the smallest possible average codeword length.
-+ Die Dimensionierung richtet sich nach den anderen Blöcken.
++ The dimensioning depends on the other blocks.
@@ Line 70: / Line 70: @@
 </quiz>
-===Musterlösung===
+===Solutions===
 {{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:
+'''(1)'''&nbsp; The graph on the information page shows that <u>solution suggestions 1 and 2</u> are correct and suggestion 3 is incorrect:
 *$\rm E$&nbsp; und&nbsp; $\rm I$&nbsp; treten zwar gruppiert auf,
 *aber nicht die&nbsp; $\rm N$&ndash;Zeichen.
-'''(2)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 2 und 3</u>:
+'''(2)'''&nbsp;<u>Proposed solutions 2 and 3</u> are correct:
-*Die Eingangsfolge wird Zeichen für Zeichen abgearbeitet.&nbsp; Auch die Ausgangsfolge hat somit die Länge&nbsp; $N = 12$.
+*The input sequence is processed character by character.&nbsp; Thus, the output sequence also has the length&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.
+*In fact, the input set&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; is converted into the output set.
-*Allerdings nicht durch einfaches&nbsp; <i>Mapping</i>, sondern durch einen Algorithmus, der nachfolgend skizziert wird.
+*However, not by simple&nbsp; <i>mapping</i>, but by an algorithm which is outlined below.
-[[File:EN_Inf_Z_2_14.png|center|frame|Beispiel für den MTF–Algorithmus]]
+[[File:EN_Inf_Z_2_14.png|center|frame|Example of the MTF algorithm]]
-'''(3)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
+'''(3)'''&nbsp; Correct is <u>solution suggestion 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.
+*The table shows the MTF algorithm.&nbsp; The step&nbsp; $i=0$&nbsp; (red background) indicates the preassignment.&nbsp; The input of the MTF is highlighted in yellow, the output in green.
-* 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.
+* In step&nbsp; $i=1$&nbsp;, the input character&nbsp; $\rm N$&nbsp; corresponding to column&nbsp; $i=0$&nbsp; is represented by index&nbsp; $I = 4$&nbsp;.&nbsp; Subsequently,&nbsp; $\rm N$&nbsp; is sorted to the front, while the order of the other characters remains the same.
-* 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.
+*The input character&nbsp; $\rm M$&nbsp; in the second step is also given the index&nbsp; $I = 4$ according to column&nbsp; $i=2$&nbsp;.&nbsp; One continues in the same way until the twelfth character&nbsp; $\rm N$, to which the index&nbsp; $I = 1$&nbsp; is assigned.
-*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.
+*You can see from the above table that at the times&nbsp; $i=6$,&nbsp; $i=7$,&nbsp; $i=10$&nbsp; and&nbsp; $i=11$&nbsp; the output index is&nbsp; $I = 0$&nbsp;.
-'''(4)'''&nbsp; Richtig sind die <u>Aussagen 1 und 2</u>:
+'''(4)'''&nbsp; <u>Statements 1 and 2</u> are correct:
-*Die Vorverarbeitungen "BWT" und "MTF"  haben nur die Aufgabe, möglichst viele Nullen zu generieren.
+*The preprocessings "BWT" and "MTF" only have the task to generate as many zeros as possible.
-'''(5)'''&nbsp; <u>Alle Aussagen</u> sind richtig.
+'''(5)'''&nbsp; <u>All statements</u> are correct.
-*Nähere Angaben zum Huffman&ndash;Algorithmus finden Sie im Kapitel "Entropiecodierung nach Huffman".
+*You can find more information on the Huffman algorithm in the chapter "Entropy coding according to Huffman".
 {{ML-Fuß}}
 [[Category:Information Theory: Exercises|^2.4 Further Source Coding Methods^]]

@@ Line 2: / Line 2: @@
 }}
-[[File:EN_Inf_Z_2_14b.png|right|frame|Schema für die Burrows–Wheeler–Datenkomprimierung]]
+[[File:EN_Inf_Z_2_14b.png|right|frame|Scheme for Burrows-Wheeler data compression]]
-Wir beziehen uns auf die Theorieseite&nbsp; [[Information_Theory/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.
+We refer to the theory page&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Application_scenario_for_the_Burrows-Wheeler_transformation|Application Scenario for the Burrows-Wheeler Transform]]&nbsp; and consider the coding system sketched on the right, consisting of the blocks.
-* <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>Burrows&ndash;Wheeler&ndash;Transformation</i>&nbsp; $\rm (BWT)$&nbsp; as described in&nbsp; [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Exercise 2.13]]; the two character sets at the input and output of the BWT are the same: &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;
+* <i>Move&ndash;to&ndash;Front</i>&nbsp; $\rm (MTF)$, a sorting algorithm that outputs a string of the same length&nbsp; $($&nbsp; $N = 12 in the example)$, but with a different 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;;
-* $\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 RLC0$&nbsp; &ndash; a run-length encoding specifically for zero, which is (as) frequent according to&nbsp; $\rm BWT$&nbsp; and&nbsp; $\rm MTF$&nbsp; ;&nbsp; all other indices are not changed by&nbsp; $\rm RLC0$&nbsp;;
-* $\rm Huffman$&nbsp; gemäß der Beschreibung im Kapitel&nbsp; [[Information_Theory/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]]; häufige Zeichen werden durch kurze Binärfolgen dargestellt und seltene durch lange.
+* $\rm Huffman$&nbsp; as described in the chapter&nbsp; [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy coding according to Huffman]]; frequent characters are represented by short binary sequences and rare ones by long ones.
-Der&nbsp; $\rm MTF$&ndash;Algorithmus lässt sich bei&nbsp; $M = 6$&nbsp; Eingangssymbolen  wie folgt beschreiben:
+The&nbsp; $\rm MTF$&ndash;algorithm can be described as follows for&nbsp; $M = 6$&nbsp; input symbols:
-* Die Ausgangsfolge des&nbsp; $\rm MTF$&nbsp; ist eine Aneinanderreihung von Indizes aus der Menge
+* The output sequence of the&nbsp; $\rm MTF$&nbsp; is a string of indices from the set
 :&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&nbsp; $\rm MTF$&ndash;Algorithmus werden die möglichen Eingangssymbole lexikografisch sortiert und den folgenden Indizes zugeordnet:
+* Before starting the actual&nbsp; $\rm MTF$ algorithm, the possible input symbols are sorted lexicographically and assigned to the following indices:
 : &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&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.
+* Let the&nbsp; $\rm MTF$ input string here be&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; This was the&nbsp; $\rm BWT$ result in&nbsp; [[Aufgaben:2.13_Burrows-Wheeler-Rücktransformation|Exercise 2.13]].&nbsp; The first&nbsp; $\rm N$&nbsp; is represented as&nbsp; $I = 4$&nbsp; according to the default setting.
-* 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:
+* Then the&nbsp; $\rm N$&nbsp; is placed at the beginning in the sorting, so that after the coding step&nbsp; $i = 1$&nbsp; the assignment holds:
 : &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.&nbsp; Steht ein Zeichen bereits an Position&nbsp; <b>0</b>, so ist keine Neusortierung erforderlich.
+* Continue in the same way until the entire input text has been processed.&nbsp; If a character is already at position&nbsp; <b>0</b>, no reordering is necessary.
-''Hinweise:''
+===Questions===
 <quiz display=simple>