Aufgaben:Exercise 2.3: About the LZ78 Compression - Revision history

Guenter at 12:10, 10 August 2021

2021-08-10T12:10:22Z

Noah at 20:27, 6 August 2021

2021-08-06T20:27:22Z

Guenter at 11:59, 13 July 2021

2021-07-13T11:59:24Z

Guenter at 11:54, 13 July 2021

2021-07-13T11:54:53Z

Guenter at 13:47, 12 July 2021

2021-07-12T13:47:35Z

Guenter at 13:39, 12 July 2021

2021-07-12T13:39:59Z

Noah at 13:04, 9 July 2021

2021-07-09T13:04:03Z

Noah at 13:02, 9 July 2021

2021-07-09T13:02:18Z

Guenter at 13:38, 8 July 2021

2021-07-08T13:38:49Z

Noah at 21:04, 7 July 2021

2021-07-07T21:04:25Z

← Older revision		Revision as of 12:10, 10 August 2021
Line 1:		Line 1:

−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Komprimierung nach Lempel~~, ~~Ziv und Welch~~	+	{{quiz-Header\|Buchseite=Information_Theory/Compression_According_to_Lempel,_Ziv_and_Welch
	}}		}}

@@ Line 32: / Line 32: @@
-''Hints:''
+Hints:
 *The exercise belongs to the chapter&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch|Compression According to Lempel, Ziv and Welch]].
 *In particular, reference is made to the page&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#The_Lempel-Ziv_variant_LZ78|The Lempel-Ziv Variant LZ78]].

← Older revision		Revision as of 11:59, 13 July 2021
Line 132:		Line 132:


−	[[Category:Information Theory: Exercises\|^2.2 ~~Compression According to~~ Lempel, Ziv, Welch^]]	+	[[Category:Information Theory: Exercises\|^2.2 Lempel-Ziv-Welch Compression^]]

← Older revision		Revision as of 11:54, 13 July 2021
Line 132:		Line 132:


−	[[Category:Information Theory: Exercises\|^2.2 ~~Verfahren von~~ Lempel, Ziv, Welch^]]	+	[[Category:Information Theory: Exercises\|^2.2 Compression According to Lempel, Ziv, Welch^]]

@@ Line 93: / Line 93: @@
 '''(2)'''&nbsp; $\rm &epsilon;$&nbsp; denotes the empty character.&nbsp;
-*Since&nbsp; $\rm &epsilon;$ + <b>B</b> = <b>B</b>&nbsp;,<u>statements 1 and 2</u> are correct.
+*Since&nbsp; $\rm &epsilon;$ + <b>B</b> = <b>B</b> &nbsp; &rArr; &nbsp; <u>statements 1 and 2</u> are correct.
 *Statement 3 is again only true for LZW compression.
@@ Line 102: / Line 102: @@
-'''(4)'''&nbsp <u>Statements 2 and 4</u> are correct:
+'''(4)'''&nbsp; <u>Statements 2 and 4</u> are correct:
-*In the dictionary, character&nbsp; <b>B</b>&nbsp; is found under index &nbsp; $I = 1$&nbsp;.
+*In the dictionary, character&nbsp; <b>B</b>&nbsp; is found under index &nbsp; $I = 1$.
 *The next character&nbsp; <b>A</b>&nbsp; of the input sequence is appended: &nbsp; <b>(1, A)</b>.
 *Statement 3 cannot be correct because&nbsp; $Z$&nbsp; can only be a character and not a character sequence.
@@ Line 109: / Line 109: @@
-[[File:EN_Inf_A_2_3f.png|right|frame|LZ78 coding of&nbsp; <b>BARBARA–BAR</b>]]
+[[File:EN_Inf_A_2_3f.png|right|frame|LZ78 coding of&nbsp; "<b>BARBARA–BAR</b>"]]
-'''(5)'''&nbsp; The entire coding process is summarised in a table. One can see:
+'''(5)'''&nbsp; The entire coding process is summarised in the table on the right.&nbsp; One can see:
-* At each time&nbsp; $i$&nbsp;, the edited string is entered into the dictionary.
+* At each time&nbsp; $i$,&nbsp; the edited string is entered into the dictionary.
 * At time&nbsp; $\underline{i=7}$&nbsp; the coding process is completed.
@@ Line 117: / Line 117: @@
 '''(6)'''&nbsp; If we represent all indices with three bits and the four characters with two bits each, we get the following results:
-* without coding: &nbsp; $N = 11 \cdot 2 \hspace{0.15cm}\underline {= 22 \, \rm Bit}$,
+* Without coding: &nbsp; $N = 11 \cdot 2 \hspace{0.15cm}\underline {= 22 \, \rm bits}$,
-* with LZ78 coding: &nbsp; $N = 7 \cdot (3+2) \hspace{0.15cm}\underline {= 35 \, \rm Bit}$.
+* with LZ78 coding: &nbsp; $N = 7 \cdot (3+2) \hspace{0.15cm}\underline {= 35 \, \rm bits}$.
 You can see from this:
-* Any LZ compression only makes sense with a larger file, even if one believes that a text like&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; accommodates the LZ78 algorithm.
+* Any LZ compression only makes sense with a larger file, even if one believes that a text like&nbsp; "<b>BARBARA&ndash;BAR</b>"&nbsp; accommodates the LZ78 algorithm.
-* With variable number of bits for the index according to task 2.4, the result for this LZ78 example would be:
+* With variable number of bits for the index according to Exercise 2.4, the result for this LZ78 example would be:
-:$$N = 1 \cdot 3 + 2 \cdot 4 + 4 \cdot 5 = 31 \,{\rm Bit}\hspace{0.05cm}.$$
+:$$N = 1 \cdot 3 + 2 \cdot 4 + 4 \cdot 5 = 31 \,{\rm bits}\hspace{0.05cm}.$$
 {{ML-Fuß}}

@@ Line 4: / Line 4: @@
 [[File:P_ID2434__Inf_A_2_3.png|right|frame|The LZ78&ndash;inventors]]
-In contrast to entropy coding according to Huffman or Shannon, where one must know the source statistics (as precisely as possible), such restrictions do not apply to the compression methods developed by&nbsp; [https://en.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]&nbsp; and&nbsp; [https://en.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]&nbsp;.&nbsp; This is called ''universal source coding''.
+In contrast to&nbsp; "Entropy Coding"&nbsp; according to Huffman or Shannon, where one must know the source statistics&nbsp; (as precisely as possible),&nbsp; such restrictions do not apply to the compression methods developed by&nbsp; [https://en.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]&nbsp; and&nbsp; [https://en.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]&nbsp;.&nbsp; This is called&nbsp; "Universal Source Coding".
-In this task, we consider the variant first published in 1978&nbsp; [LZ78].&nbsp;  The string &nbsp;<b>BARBARA&ndash;BAR</b> is to be encoded.
+In this exercise, we consider the variant first published in 1978&nbsp; [LZ78].&nbsp;  The string &nbsp;<b>BARBARA&ndash;BAR</b> is to be encoded.
-*The procedure LZ78 works with a global dictionary, which is initially only filled with an empty character&nbsp; $(\varepsilon)$&nbsp; under the index&nbsp; $I = 0$&nbsp;.&nbsp; This distinguishes "LZ78" from its predecessor "LZ77" (with local dictionary) and also from its successor "LZW" (dictionary is prefilled with the possible characters).
+*The procedure&nbsp; "LZ78"&nbsp; works with a global dictionary, which is initially only filled with an empty character&nbsp; $(\varepsilon)$&nbsp; under the index&nbsp; $I = 0$.&nbsp; This distinguishes&nbsp; "LZ78"&nbsp; from its predecessor&nbsp; "LZ77"&nbsp; (with local dictionary)&nbsp; and also from its successor&nbsp; "LZW"&nbsp; (dictionary is prefilled with the possible characters).
-*f a character or a word fragment (several characters) of the input string is found in the dictionary, the index&nbsp; $I_0$&nbsp; of this entry is output together with the next input character&nbsp; $Z$&nbsp;.&nbsp; In each step&nbsp; $i$&nbsp; the output is therefore: &nbsp;  $(I_0, \ Z)$.
+*If a character or a word fragment&nbsp; (several characters)&nbsp; of the input string is found in the dictionary, the index&nbsp; $I_0$&nbsp; of this entry is output together with the next input character&nbsp; $Z$&nbsp;.&nbsp; In each step&nbsp; $i$&nbsp; the output is therefore: &nbsp;  $(I_0, \ Z)$.
-*Afterwards, the new string is entered into the dictionary under the next free index&nbsp; $I_{\rm neu}$&nbsp;.
+*Afterwards, the new string is entered into the dictionary under the next free index&nbsp; $I_{\rm new}$.
 *If one considers the dictionary as a field&nbsp; $W\big[\hspace{0.05cm}I\hspace{0.05cm}\big]$&nbsp; with&nbsp; $I &ge; 0$, where each element contains a string of arbitrary length, then with the character variable&nbsp; $Z$:
-:$$W \big[\hspace{0.05cm}I_{\rm neu}\hspace{0.05cm}\big]  = W\big[\hspace{0.05cm}I_0\hspace{0.05cm}\big] + Z \hspace{0.05cm}. $$
+:$$W \big[\hspace{0.05cm}I_{\rm new}\hspace{0.05cm}\big]  = W\big[\hspace{0.05cm}I_0\hspace{0.05cm}\big] + Z \hspace{0.05cm}. $$
 For clarification, a simple example:
-*At a given time, the dictionary is filled up to index&nbsp; $I_{\rm akt }= 20$&nbsp;.
+*At a given time, the dictionary is filled up to index&nbsp; $I_{\rm act }= 20$.
-*'''Handy'''&nbsp; is waiting to be encoded.&nbsp; In the dictionary, the &nbsp; <b>Ha</b>&nbsp; is found under index&nbsp; $I = 11$&nbsp; and the entry <b>Han</b> under index&nbsp; $I = 16$&nbsp;.
+*'''Handy'''&nbsp; is waiting to be encoded.&nbsp; In the dictionary, &nbsp; "<b>Ha</b>"&nbsp; is found under index&nbsp; $I = 11$&nbsp; and the entry&nbsp; "<b>Han</b>"&nbsp; under index&nbsp; $I = 16$.
-*Thus, the current code output is &nbsp;  $(I_0,  Z) = (16,$ <b>d</b>$)$&nbsp; and the following is entered into the dictionary as a new phrase: &nbsp; $W(21) =$ <b>Hand</b>.
+*Thus, the current code output is &nbsp;  $(I_0,  Z) = (16,$ <b>d</b>$)$&nbsp; and the following is entered into the dictionary as a new phrase:
-*Now the string&nbsp; <b>y</b>&nbsp; is available for coding.&nbsp; If no suitable entry is found, &nbsp; $(0,$ <b>y</b>$)$&nbsp; is output and a new entry is made in the dictionary: &nbsp; $W(22) = $ $\rm &epsilon;$&nbsp; +  <b>y</b> $=$ <b>y</b> .
+&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; $W(21) = $ <b>Hand</b>.
 For subtask&nbsp; '''(6)'''&nbsp; you can assume the following:
 * The decimal number&nbsp; $I$&nbsp; (index) is represented in binary by three bits.
 * The character&nbsp; $Z &#8712; \{$<b>A</b>,&nbsp; <b>B</b>,&nbsp; <b>R</b>,&nbsp; <b>&ndash;</b>$ \}$&nbsp; is binary coded by two bits each.
@@ Line 32: / Line 33: @@
 ''Hints:''
-*The task belongs to the chapter&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch|Compression According to Lempel, Ziv and Welch]].
+*The exercise belongs to the chapter&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch|Compression According to Lempel, Ziv and Welch]].
-*In particular, reference is made to the page&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#The_Lempel-Ziv_variant_LZ78|The Lempel-Ziv Variant LZ78]]&nbsp;.
+*In particular, reference is made to the page&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#The_Lempel-Ziv_variant_LZ78|The Lempel-Ziv Variant LZ78]].
-*The original literature&nbsp; [LZ78]&nbsp; on this method is: &nbsp; <br>Ziv, J.; Lempel, A.: ''Compression of Individual Sequences via Variable-Rate Coding.'' In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.
+*The original literature&nbsp; [LZ78]&nbsp; on this method is:  <br> &nbsp; &nbsp; Ziv, J.; Lempel, A.:&nbsp; Compression of Individual Sequences via Variable-Rate Coding.&nbsp; In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.
-*&nbsp; [[Aufgaben:2.3Z_Zur_LZ77-Codierung|Exercise 2.3Z]]&nbsp; and&nbsp; [[Aufgaben:Aufgabe_2.4:_Zum_LZW-Algorithmus|Exercise 2.4]]&nbsp; deal with other Lempel&ndash;Ziv methods in a similar way.
+*[[Aufgaben:2.3Z_Zur_LZ77-Codierung|Exercise 2.3Z]]&nbsp; and&nbsp; [[Aufgaben:Aufgabe_2.4:_Zum_LZW-Algorithmus|Exercise 2.4]]&nbsp; deal with other Lempel&ndash;Ziv methods in a similar way.
@@ Line 45: / Line 46: @@
 |type="()"}
 + Only the index&nbsp; $I = 0$&nbsp; with the space&nbsp; $(\varepsilon)$ is preassigned.
-- The indices&nbsp; $I = 0$&nbsp; to&nbsp; $I = 3$&nbsp; with the four characters&nbsp; '''A''',&nbsp; '''B''',&nbsp; '''R'''&nbsp; and&nbsp; '''&ndash;''' are preallocated.
+- The indices&nbsp; $I = 0$&nbsp; to&nbsp; $I = 3$&nbsp; with the four characters&nbsp; "'''A'''",&nbsp; "'''B'''",&nbsp; '''R'''&nbsp; and&nbsp; "'''&ndash;'''" are preallocated.
@@ Line 69: / Line 70: @@
-{Complete the LZ78 coding.&nbsp; After which coding step&nbsp; $i_{\rm Ende}$&nbsp; is&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; completely coded?
+{Complete the LZ78 coding.&nbsp; After which coding step&nbsp; $i_{\rm end}$&nbsp; is&nbsp; "<b>BARBARA&ndash;BAR</b>"&nbsp; completely coded?
 |type="{}"}
-$i_{\rm Ende} \ = \ $ { 7 3% }
+$i_{\rm end} \ = \ $ { 7 3% }
-{How many binary characters are needed to code&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp;?&nbsp; Follow the instructions on the information page.
+{How many binary characters are needed to code&nbsp; "<b>BARBARA&ndash;BAR"</b>&nbsp;?&nbsp; Follow the instructions on the information page.
 |type="{}"}
-$\text{without coding:  }\ N \ = \ $ { 22 3% } $\ \rm Bit$
+$\text{without coding:  }\ N \ = \ $ { 22 3% } $\ \rm bits$
-$\text{with LZ78 coding:  }\ N \ = \ $ { 35 3% } $\ \rm Bit$
+$\text{with LZ78 coding:  }\ N \ = \ $ { 35 3% } $\ \rm bits$

← Older revision		Revision as of 13:04, 9 July 2021
Line 36:		Line 36:
	*The original literature  [LZ78]  on this method is:   <br>Ziv, J.; Lempel, A.: ''Compression of Individual Sequences via Variable-Rate Coding.'' In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.		*The original literature  [LZ78]  on this method is:   <br>Ziv, J.; Lempel, A.: ''Compression of Individual Sequences via Variable-Rate Coding.'' In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.

−	*  [[Aufgaben:2.3Z_Zur_LZ77-Codierung\|Exercise 2.3Z]]  and  [[Aufgaben:Aufgabe_2.4:_Zum_LZW-Algorithmus\|Exercise 2.4]]  deal with other–Ziv methods in a similar way.	+	*  [[Aufgaben:2.3Z_Zur_LZ77-Codierung\|Exercise 2.3Z]]  and  [[Aufgaben:Aufgabe_2.4:_Zum_LZW-Algorithmus\|Exercise 2.4]]  deal with other Lempel–Ziv methods in a similar way.

@@ Line 42: / Line 42: @@
 <quiz display=simple>
-{Welche Aussagen gelten für die Vorbelegung des LZ78&ndash;Wörterbuches?
+{Which statements apply to the preassignment of the LZ78 dictionary?
 |type="()"}
-+ Vorbelegt ist nur der Index&nbsp; $I = 0$&nbsp; mit dem Leerzeichen&nbsp; $(\varepsilon)$.
++ Only the index&nbsp; $I = 0$&nbsp; with the space&nbsp; $(\varepsilon)$ is preassigned.
-- Vorbelegt sind die Indizes&nbsp; $I = 0$&nbsp; bis&nbsp; $I = 3$&nbsp; mit den vier Zeichen&nbsp; '''A''',&nbsp; '''B''',&nbsp; '''R'''&nbsp; und&nbsp; '''&ndash;''' .
+- The indices&nbsp; $I = 0$&nbsp; to&nbsp; $I = 3$&nbsp; with the four characters&nbsp; '''A''',&nbsp; '''B''',&nbsp; '''R'''&nbsp; and&nbsp; '''&ndash;''' are preallocated.
-{Was geschieht im Codierschritt&nbsp; $i = 1$?
+{What happens in the coding step&nbsp; $i = 1$?
 |type="[]"}
-+ Die Coderausgabe lautet: &nbsp; $(0,$ <b>B</b>$)$.
++ The coder output is: &nbsp; $(0,$ <b>B</b>$)$.
-+ Der Wörterbucheintrag lautet: &nbsp; $W(I = 1) =$ <b>B</b>.
++ The dictionary entry is: &nbsp; $W(I = 1) =$ <b>B</b>.
-- Der Wörterbucheintrag lautet: &nbsp; $W(I = 1) =$ <b>BA</b>.
+- The dictionary entry is: &nbsp; $W(I = 1) =$ <b>BA</b>.
-{Welche Aussagen gelten für die Codierschritte&nbsp; $i = 2$&nbsp; und&nbsp; $i = 3$?
+{Which statements are true for the coding steps&nbsp; $i = 2$&nbsp; and&nbsp; $i = 3$?
 |type="[]"}
-+ Für&nbsp; $i = 2$&nbsp; gilt: &nbsp; Ausgabe&nbsp; $(0,$ <b>A</b>$)$, &nbsp; Eintrag&nbsp; $W(I = 2) =$  <b>A</b>.
++ For&nbsp; $i = 2$&nbsp;, the following is true: &nbsp; Output&nbsp; $(0,$ <b>A</b>$)$, &nbsp; entry&nbsp; $W(I = 2) =$  <b>A</b>.
-+ Für&nbsp; $i = 3$&nbsp; gilt: &nbsp; Ausgabe&nbsp; $(0,$ <b>R</b>$)$, &nbsp; Eintrag&nbsp; $W(I = 3) =$ <b>R</b>.
++ For&nbsp; $i = 3$&nbsp;, the following is true: &nbsp; Output&nbsp; $(0,$ <b>R</b>$)$, &nbsp; entry&nbsp; $W(I = 3) =$ <b>R</b>.
-{Welche Aussagen gelten für den Codierschritt&nbsp; $i = 4$?
+{Which statements are true for the coding step&nbsp; $i = 4$?
 |type="[]"}
-- Bei Schritt&nbsp; $i = 4$&nbsp; wird&nbsp; <b>BAR</b>&nbsp; gemeinsam codiert.
+- At step&nbsp; $i = 4$&nbsp; &nbsp; <b>BAR</b>&nbsp; is coded together.
-+ Bei Schritt&nbsp; $i = 4$&nbsp; wird&nbsp; <b>BA</b>&nbsp; gemeinsam codiert.
++ At step&nbsp; $i = 4$&nbsp; &nbsp; <b>BA</b>&nbsp; is coded together.
-- Die Coderausgabe lautet: &nbsp; $(2,$ <b>AR</b>$)$.
+- The coder output is: &nbsp; $(2,$ <b>AR</b>$)$.
-+ Die Coderausgabe lautet: &nbsp; $(1,$ <b>A</b>$)$.
++ The coder output is: &nbsp; $(1,$ <b>A</b>$)$.
-{Vervollständigen Sie die LZ78&ndash;Codierung.&nbsp; Nach welchem Codierschritt&nbsp; $i_{\rm Ende}$&nbsp; ist&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; vollständig codiert?
+{Complete the LZ78 coding.&nbsp; After which coding step&nbsp; $i_{\rm Ende}$&nbsp; is&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; completely coded?
 |type="{}"}
 $i_{\rm Ende} \ = \ $ { 7 3% }
-{Wieviele Binärzeichen benötigt man, um&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; zu codieren?&nbsp; Beachten Sie die Hinweise auf der Angabenseite.
+{How many binary characters are needed to code&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp;?&nbsp; Follow the instructions on the information page.
 |type="{}"}
-$\text{ohne Codierung:  }\ N \ = \ $ { 22 3% } $\ \rm Bit$
+$\text{without coding:  }\ N \ = \ $ { 22 3% } $\ \rm Bit$
-$\text{mit LZ78-Codierung:  }\ N \ = \ $ { 35 3% } $\ \rm Bit$
+$\text{with LZ78 coding:  }\ N \ = \ $ { 35 3% } $\ \rm Bit$
@@ Line 83: / Line 83: @@
 </quiz>
-===Musterlösung===
+===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Zutreffend für den LZ78&ndash;Algorithmus ist <u>Aussage 1</u>:
+'''(1)'''&nbsp; <u>Statement 1</u> applies to the LZ78 algorithm:
-*Die Vorbelegung gemäß Aussage 2 gilt dagegen für den LZW&ndash;Algorithmus, der 1983 gemeinsam mit Terry Welch veröffentlicht wurde.
+*In contrast, the preassignment according to statement 2 is true for the LZW algorithm, which was published in 1983 together with Terry Welch.
-Daran erkennt man:
-* Eine jede LZ&ndash;Komprimierung macht erst bei einer größeren Datei Sinn, auch dann, wenn man glaubt, dass ein Text wie&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; dem LZ78&ndash;Algorithmus entgegenkommt.
+You can see from this:
-* Mit variabler Bitanzahl für den Index entsprechend der Aufgabe 2.4 würde sich für dieses LZ78-Beispiel ergeben:
+* Any LZ compression only makes sense with a larger file, even if one believes that a text like&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; accommodates the LZ78 algorithm.
 :$$N = 1 \cdot 3 + 2 \cdot 4 + 4 \cdot 5 = 31 \,{\rm Bit}\hspace{0.05cm}.$$
 {{ML-Fuß}}

@@ Line 107: / Line 107: @@
-[[File:Inf_A_2_3f_version2.png|right|frame|LZ78–Codierung von&nbsp; <b>BARBARA–BAR</b>]]
+[[File:EN_Inf_A_2_3f.png|right|frame|LZ78–Codierung von&nbsp; <b>BARBARA–BAR</b>]]
 '''(5)'''&nbsp; Der gesamte Codiervorgang ist in einer Tabelle zusammengefasst. Man erkennt:
 * Zu jedem Zeitpunkt&nbsp; $i$&nbsp; wird die bearbeitete Zeichenfolge in das Wörterbuch eingetragen.

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2434__Inf_A_2_3.png|right|frame|Die LZ78&ndash;Erfinder]]
+[[File:P_ID2434__Inf_A_2_3.png|right|frame|The LZ78&ndash;inventors]]
-Im Gegensatz zur Entropiecodierung nach Huffman oder nach Shannon, bei der man die Quellenstatistik (möglichst genau) kennen muss, sind solche Einschränkungen bei den von&nbsp; [https://de.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]&nbsp; und&nbsp; [https://de.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]&nbsp; entwickelten Komprimierungsverfahren nicht gegeben.&nbsp; Man spricht von ''universeller Quellencodierung''.
+In contrast to entropy coding according to Huffman or Shannon, where one must know the source statistics (as precisely as possible), such restrictions do not apply to the compression methods developed by&nbsp; [https://en.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]&nbsp; and&nbsp; [https://en.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]&nbsp;.&nbsp; This is called ''universal source coding''.
-Wir betrachten in dieser Aufgabe die 1978 erstmals veröffentlichte Variante&nbsp; [LZ78].&nbsp;  Codiert werden soll der String &nbsp;<b>BARBARA&ndash;BAR</b>.
+In this task, we consider the variant first published in 1978&nbsp; [LZ78].&nbsp;  The string &nbsp;<b>BARBARA&ndash;BAR</b> is to be encoded.
-*Das Verfahren LZ78 arbeitet mit einem globalen Wörterbuch, das zu Beginn nur mit einem leeren Zeichen&nbsp; $(\varepsilon)$&nbsp; unter dem Index&nbsp; $I = 0$&nbsp; gefüllt ist.&nbsp; Dadurch unterscheidet sich "LZ78" von seinem Vorgänger "LZ77" (mit lokalem Wörterbuch) und auch von seinem Nachfolger "LZW" (Wörterbuch ist mit den möglichen Zeichen vorbelegt).
+*The procedure LZ78 works with a global dictionary, which is initially only filled with an empty character&nbsp; $(\varepsilon)$&nbsp; under the index&nbsp; $I = 0$&nbsp;.&nbsp; This distinguishes "LZ78" from its predecessor "LZ77" (with local dictionary) and also from its successor "LZW" (dictionary is prefilled with the possible characters).
-*Wird ein Zeichen oder ein Wortfragment (mehrere Zeichen) des Eingabestrings im Wörterbuch gefunden, so wird der Index&nbsp; $I_0$&nbsp; dieses Eintrags zusammen mit dem nächsten Eingangszeichen&nbsp; $Z$&nbsp; ausgegeben.&nbsp; In jedem Schritt&nbsp; $i$&nbsp; lautet also die Ausgabe: &nbsp;  $(I_0, \ Z)$.
+*f a character or a word fragment (several characters) of the input string is found in the dictionary, the index&nbsp; $I_0$&nbsp; of this entry is output together with the next input character&nbsp; $Z$&nbsp;.&nbsp; In each step&nbsp; $i$&nbsp; the output is therefore: &nbsp;  $(I_0, \ Z)$.
-*Anschließend wird der neue String unter dem nächsten freien Index&nbsp; $I_{\rm neu}$&nbsp; ins Wörterbuch eingetragen.
+*Afterwards, the new string is entered into the dictionary under the next free index&nbsp; $I_{\rm neu}$&nbsp;.
-*Betrachtet man das Wörterbuch als ein Feld&nbsp; $W\big[\hspace{0.05cm}I\hspace{0.05cm}\big]$&nbsp; mit&nbsp; $I &ge; 0$, bei dem ein jedes Element eine Zeichenkette beliebiger Länge enthält, so gilt mit der Character&ndash;Variablen&nbsp; $Z$:
+*If one considers the dictionary as a field&nbsp; $W\big[\hspace{0.05cm}I\hspace{0.05cm}\big]$&nbsp; with&nbsp; $I &ge; 0$, where each element contains a string of arbitrary length, then with the character variable&nbsp; $Z$:
 :$$W \big[\hspace{0.05cm}I_{\rm neu}\hspace{0.05cm}\big]  = W\big[\hspace{0.05cm}I_0\hspace{0.05cm}\big] + Z \hspace{0.05cm}. $$
-Zur Verdeutlichung ein einfaches Beispiel:
+For clarification, a simple example:
-*Zu einem gegebenen Zeitpunkt ist das Wörterbuch bis zum Index&nbsp; $I_{\rm akt }= 20$&nbsp; gefüllt.
+*At a given time, the dictionary is filled up to index&nbsp; $I_{\rm akt }= 20$&nbsp;.
-*Zur Codierung steht&nbsp; '''Handy'''&nbsp; an.&nbsp; Im Wörterbuch findet man unter dem Index&nbsp; $I = 11$&nbsp; den Eintrag&nbsp; <b>Ha</b>&nbsp; und unter dem Index&nbsp; $I = 16$&nbsp; den Eintrag <b>Han</b>.
+*'''Handy'''&nbsp; is waiting to be encoded.&nbsp; In the dictionary, the &nbsp; <b>Ha</b>&nbsp; is found under index&nbsp; $I = 11$&nbsp; and the entry <b>Han</b> under index&nbsp; $I = 16$&nbsp;.
-*Somit lautet die aktuelle Coderausgabe &nbsp;  $(I_0,  Z) = (16,$ <b>d</b>$)$&nbsp; und ins Wörterbuch wird als neue Phrase eingetragen: &nbsp; $W(21) =$ <b>Hand</b>.
+*Thus, the current code output is &nbsp;  $(I_0,  Z) = (16,$ <b>d</b>$)$&nbsp; and the following is entered into the dictionary as a new phrase: &nbsp; $W(21) =$ <b>Hand</b>.
-*Nun liegt der String&nbsp; <b>y</b>&nbsp; zur Codierung an.&nbsp; Findet man hierfür keinen passenden Eintrag, so wird&nbsp; $(0,$ <b>y</b>$)$&nbsp; ausgegeben und ins Wörterbuch wird neu eingetragen: &nbsp; $W(22) = $ $\rm &epsilon;$&nbsp; +  <b>y</b> $=$ <b>y</b> .
+*Now the string&nbsp; <b>y</b>&nbsp; is available for coding.&nbsp; If no suitable entry is found, &nbsp; $(0,$ <b>y</b>$)$&nbsp; is output and a new entry is made in the dictionary: &nbsp; $W(22) = $ $\rm &epsilon;$&nbsp; +  <b>y</b> $=$ <b>y</b> .
-Für die Teilaufgabe&nbsp; '''(6)'''&nbsp; können Sie von folgenden Voraussetzungen ausgehen:
+For subtask&nbsp; '''(6)'''&nbsp; you can assume the following:
-* Die Dezimalzahl&nbsp; $I$&nbsp; (Index) wird durch drei Bit binär dargestellt.
+* The decimal number&nbsp; $I$&nbsp; (index) is represented in binary by three bits.
-* Das Zeichen&nbsp; $Z &#8712; \{$<b>A</b>,&nbsp; <b>B</b>,&nbsp; <b>R</b>,&nbsp; <b>&ndash;</b>$ \}$&nbsp; wird mit jeweils zwei Bit binär codiert.
+* The character&nbsp; $Z &#8712; \{$<b>A</b>,&nbsp; <b>B</b>,&nbsp; <b>R</b>,&nbsp; <b>&ndash;</b>$ \}$&nbsp; is binary coded by two bits each.
@@ Line 30: / Line 30: @@
-''Hinweise:''
-*Die Aufgabe gehört zum  Kapitel&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch|Komprimierung nach Lempel, Ziv und Welch]].
+''Hints:''
-*Insbesondere wird auf die Seite&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|Die Lempel-Ziv-Variante LZ78]]&nbsp; Bezug genommen.
+*The task belongs to the chapter&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch|Compression According to Lempel, Ziv and Welch]].
-*Die Originalliteratur&nbsp; [LZ78]&nbsp; zu diesem Verfahren lautet: &nbsp; <br>Ziv, J.; Lempel, A.: ''Compression of Individual Sequences via Variable-Rate Coding.'' In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.
+*In particular, reference is made to the page&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#The_Lempel-Ziv_variant_LZ78|The Lempel-Ziv Variant LZ78]]&nbsp;.
-*Die&nbsp; [[Aufgaben:2.3Z_Zur_LZ77-Codierung|Aufgabe 2.3Z]]&nbsp; sowie die&nbsp; [[Aufgaben:Aufgabe_2.4:_Zum_LZW-Algorithmus|Aufgabe 2.4]]&nbsp; behandeln andere Lempel&ndash;Ziv-Verfahren in ähnlicher Weise.
+*&nbsp; [[Aufgaben:2.3Z_Zur_LZ77-Codierung|Exercise 2.3Z]]&nbsp; and&nbsp; [[Aufgaben:Aufgabe_2.4:_Zum_LZW-Algorithmus|Exercise 2.4]]&nbsp; deal with other&ndash;Ziv methods in a similar way.
-===Fragebogen===
+===Questions===
 <quiz display=simple>