Aufgaben:Exercise 2.3Z: About the LZ77 Coding - Revision history

Guenter at 12:10, 10 August 2021

2021-08-10T12:10:52Z

Noah at 20:26, 6 August 2021

2021-08-06T20:26:55Z

Guenter at 11:58, 13 July 2021

2021-07-13T11:58:12Z

Guenter at 09:34, 13 July 2021

2021-07-13T09:34:54Z

Guenter at 09:23, 13 July 2021

2021-07-13T09:23:02Z

Noah at 15:58, 12 July 2021

2021-07-12T15:58:40Z

Guenter at 15:03, 12 July 2021

2021-07-12T15:03:13Z

Guenter at 15:01, 12 July 2021

2021-07-12T15:01:16Z

Guenter at 15:00, 12 July 2021

2021-07-12T15:00:04Z

Guenter at 14:57, 12 July 2021

2021-07-12T14:57:44Z

← 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 33: / Line 33: @@
-''Hints:''
+Hints:
 *The task 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#LZ77_-_the_basic_form_of_the_Lempel-Ziv_algorithms|LZ77 &ndash; the basic form of the Lempel-Ziv algorithms]]&nbsp;.

← Older revision		Revision as of 11:58, 13 July 2021
Line 116:		Line 116:


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

@@ Line 82: / Line 82: @@
 [[File:P_ID2438__Inf_Z_2_3c.png|right|frame|Example of the LZ77 algorithm with&nbsp; $G = 4$]]
 '''(1)'''&nbsp;<u>Solution suggestion 3</u> is correct.
-*The preview buffer contains the character string&nbsp; <b>BARA</b> at the time&nbsp; $i = 4$&nbsp;.
+*The preview buffer contains the character string&nbsp; "<b>BARA</b>" at the time&nbsp; $i = 4$&nbsp;.
-*The search buffer contains&nbsp; <b>BAR</b> in the last three digits:
+*The search buffer contains&nbsp; "<b>BAR</b>" in the last three digits:
 :$$P = 2\hspace{0.05cm},\hspace{0.2cm}L = 3\hspace{0.05cm},\hspace{0.2cm}Z = \boldsymbol{\rm A}\hspace{0.05cm}.$$
@@ Line 89: / Line 89: @@
 '''(2)'''&nbsp;<u>The first two solutions</u> are correct:
-*The hyphen is not found in the search buffer at time&nbsp; $i = 5$&nbsp;.
+*The hyphen is not found in the search buffer at time&nbsp; $i = 5$.
 *The output is&nbsp; $(0, 0,$ <b>&ndash;</b>$)$.
-'''(3)'''&nbsp; The upper graphic shows the&nbsp; <i>Sliding&ndash;Window</i>&nbsp; and the coder output at times&nbsp; $i>5$.
+'''(3)'''&nbsp; The upper graphic shows the&nbsp; "Sliding Window"&nbsp; and the coder output at times&nbsp; $i>5$.
-*After&nbsp; $i = 9$&nbsp; coding steps the coding process is finished considering&nbsp; <b>eof</b>&nbsp; &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 9}$.
+*After&nbsp; $i = 9$&nbsp; coding steps the coding process is finished considering&nbsp; <b>eof</b>&nbsp; &nbsp; &rArr; &nbsp; $\underline{i_{\rm end} = 9}$.
 [[File:P_ID2439__Inf_Z_2_3d.png|right|frame|Example of the LZ77 algorithm with&nbsp; $G = 5$]]
-'''(4)'''&nbsp; With a larger buffer size&nbsp; $(G = 5$&nbsp; instead of&nbsp; $G = 4)$&nbsp; the coding is already completed after the 6th coding step &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 6}$.
+'''(4)'''&nbsp; With a larger buffer size&nbsp; $(G = 5$&nbsp; instead of&nbsp; $G = 4)$&nbsp; the coding is already completed after the 6th coding step &nbsp; &rArr; &nbsp; $\underline{i_{\rm end} = 6}$.
 *A comparison of the two graphs shows that nothing changes for&nbsp; $G = 5$&nbsp; compared to&nbsp; $G = 4$&nbsp; up to and including&nbsp; $i = 5$&nbsp;.
-*Due to the larger buffer, however,&nbsp; <b>BAR</b>&nbsp; can now be coded together with&nbsp; <b>eof</b>&nbsp; (end-of-file) in a single step, whereas with&nbsp; $G = 4$&nbsp; four steps were necessary for this.
+*Due to the larger buffer, however,&nbsp; "<b>BAR</b>"&nbsp; can now be coded together with&nbsp; "<b>eof</b>"&nbsp; (end-of-file) in a single step, whereas with&nbsp; $G = 4$&nbsp; four steps were necessary for this.
 <br clear=all>
 '''(5)'''&nbsp;Only <u>statement 1</u> is correct.
@@ Line 108: / Line 108: @@
 *It is true that with LZ78 only pairs&nbsp; $(I, \ Z)$&nbsp; have to be transmitted, whereas with LZ77 each coding step is identified by a triple&nbsp; $(P, \ L, \ Z)$&nbsp;.&nbsp; However, this does not mean that fewer bits have to be transmitted per coding step.
 *Consider, for example, the buffer size&nbsp; $G = 8$.&nbsp; With LZ77, one must then represent&nbsp; $P$&nbsp; with three bits and&nbsp; $L$&nbsp; with four bits.&nbsp; Please note that the match found between the preview buffer and the search buffer may also end in the preview buffer.
-*The new character&nbsp; $Z$&nbsp; requires exactly the same number of bits in LZ78 as in LZ77 (namely two bits), if one assumes the symbol range&nbsp; $M = 4$&nbsp; as here.
+*The new character&nbsp; $Z$&nbsp; requires exactly the same number of bits in LZ78 as in LZ77 (namely two bits), if one assumes the symbol set size&nbsp; $M = 4$&nbsp; as here.
-*Statement 2 would only be correct if&nbsp; $N_{\rm I}$&nbsp; were smaller than&nbsp; $N_{\rm P}+ N_{\rm L}$, for example&nbsp; $N_{\rm I} = 6$. But this would mean that one would have to limit the dictionary size to&nbsp; $I = 2^6 = 64$&nbsp;.&nbsp; This is not sufficient for large files.
+*Statement 2 would only be correct if&nbsp; $N_{\rm I}$&nbsp; were smaller than&nbsp; $N_{\rm P}+ N_{\rm L}$, for example&nbsp; $N_{\rm I} = 6$.&nbsp; But this would mean that one would have to limit the dictionary size to&nbsp; $I = 2^6 = 64$&nbsp;.&nbsp; This is not sufficient for large files.
 *Our rough calculation, however, is based on a uniform number of bits for the index&nbsp; $I$.&nbsp; With a variable number of bits for the index, you can save quite a few bits by transmitting&nbsp; $I$&nbsp; only with as many bits as are necessary for the coding step&nbsp; $i$&nbsp;.
 *In principle, however, this does not change the limitation of the dictionary size, which will always lead to problems with large files.

@@ Line 54: / Line 54: @@
 {Which statement is true for the same buffer size&nbsp; $G = 4$&nbsp; at step&nbsp; $i = 5$?
 |type="[]"}
-+ The search buffer contains&nbsp; <b>BARA</b>.
++ The search buffer contains&nbsp; "<b>BARA</b>".
-+ The preview buffer says&nbsp; <b>&ndash;BAR</b>.
++ The preview buffer says&nbsp; "<b>&ndash;BAR</b>".
 - The output is&nbsp; $(0, 0,$ <b>A</b>$)$.
-{After which step&nbsp; $i_{\rm Ende}$&nbsp; is the coding with&nbsp; $G = 4$&nbsp; finished?
+{After which step&nbsp; $i_{\rm end}$&nbsp; is the coding with&nbsp; $G = 4$&nbsp; finished?
 |type="{}"}
-$i_{\rm Ende} \ = \ $ { 9 }
+$i_{\rm end} \ = \ $ { 9 }
-{Now let&nbsp; $G = 5$.&nbsp; After which step&nbsp; $i_{\rm Ende}$&nbsp; is the coding finished?
+{Now let&nbsp; $G = 5$.&nbsp; After which step&nbsp; $i_{\rm end}$&nbsp; is the coding finished?
 |type="{}"}
-$i_{\rm Ende} \ = \ $ { 6 }
+$i_{\rm end} \ = \ $ { 6 }

@@ Line 80: / Line 80: @@
 ===Solution===
 {{ML-Kopf}}
-[[File:P_ID2438__Inf_Z_2_3c.png|right|frame|Beispiel zum LZ77–Algorithmus mit&nbsp; $G = 4$]]
+[[File:P_ID2438__Inf_Z_2_3c.png|right|frame|Example of the LZ77 algorithm with&nbsp; $G = 4$]]
-'''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>.
+'''(1)'''&nbsp;<u>Solution suggestion 3</u> is correct.
-*Im Vorschaupuffer steht zum betrachteten Zeitpunkt&nbsp; $i = 4$&nbsp; die Zeichenfolge&nbsp; <b>BARA</b>.
+*The preview buffer contains the character string&nbsp; <b>BARA</b> at the time&nbsp; $i = 4$&nbsp;.
-*Im Suchpuffer steht in den letzten drei Stellen&nbsp; <b>BAR</b>:
+*The search buffer contains&nbsp; <b>BAR</b> in the last three digits:
 :$$P = 2\hspace{0.05cm},\hspace{0.2cm}L = 3\hspace{0.05cm},\hspace{0.2cm}Z = \boldsymbol{\rm A}\hspace{0.05cm}.$$
-'''(2)'''&nbsp; Richtig sind die <u>beiden ersten Lösungsvorschläge</u>:
+'''(2)'''&nbsp;<u>The first two solutions</u> are correct:
-*Der Bindestrich findet sich zum Zeitpunkt&nbsp; $i = 5$&nbsp; nicht im Suchpuffer.
+*The hyphen is not found in the search buffer at time&nbsp; $i = 5$&nbsp;.
-*Ausgegeben wird&nbsp; $(0, 0,$ <b>&ndash;</b>$)$.
+*The output is&nbsp; $(0, 0,$ <b>&ndash;</b>$)$.
-'''(3)'''&nbsp; Die obere Grafik zeigt das&nbsp; <i>Sliding&ndash;Window</i>&nbsp; und die Coderausgabe zu den Zeiten&nbsp; $i>5$.
+'''(3)'''&nbsp; The upper graphic shows the&nbsp; <i>Sliding&ndash;Window</i>&nbsp; and the coder output at times&nbsp; $i>5$.
-*Nach&nbsp; $i = 9$&nbsp; Codierschritten ist der Codiervorgang unter Berücksichtigung von&nbsp; <b>eof</b>&nbsp; beendet &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 9}$.
+*After&nbsp; $i = 9$&nbsp; coding steps the coding process is finished considering&nbsp; <b>eof</b>&nbsp; &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 9}$.
-[[File:P_ID2439__Inf_Z_2_3d.png|right|frame|Beispiel zum LZ77–Algorithmus mit&nbsp; $G = 5$]]
+[[File:P_ID2439__Inf_Z_2_3d.png|right|frame|Example of the LZ77 algorithm with&nbsp; $G = 5$]]
-'''(4)'''&nbsp; Bei größerer Puffergröße&nbsp; $(G = 5$&nbsp; anstelle von&nbsp; $G = 4)$&nbsp; ist die Codierung schon nach dem 6. Codierschritt  abgeschlossen &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 6}$.
+'''(4)'''&nbsp; With a larger buffer size&nbsp; $(G = 5$&nbsp; instead of&nbsp; $G = 4)$&nbsp; the coding is already completed after the 6th coding step &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 6}$.
-*Ein Vergleich der beiden Grafiken zeigt, dass sich für&nbsp; $G = 5$&nbsp; gegenüber&nbsp; $G = 4$&nbsp; bis einschließlich&nbsp; $i = 5$&nbsp;  nichts ändert.
+*A comparison of the two graphs shows that nothing changes for&nbsp; $G = 5$&nbsp; compared to&nbsp; $G = 4$&nbsp; up to and including&nbsp; $i = 5$&nbsp;.
-*Aufgrund des größeren Puffers lässt sich aber nun&nbsp; <b>BAR</b>&nbsp; gemeinsam mit&nbsp; <b>eof</b>&nbsp; (end-of-file) in einem einzigen Schritt codieren, während mit&nbsp; $G = 4$&nbsp; hierfür vier Schritte notwendig waren.
+*Due to the larger buffer, however,&nbsp; <b>BAR</b>&nbsp; can now be coded together with&nbsp; <b>eof</b>&nbsp; (end-of-file) in a single step, whereas with&nbsp; $G = 4$&nbsp; four steps were necessary for this.
 <br clear=all>
-'''(5)'''&nbsp; Richtig ist nur die  <u>Aussage 1</u>.
+'''(5)'''&nbsp;Only <u>statement 1</u> is correct.
-*Ein Nachteil von LZ77 ist das lokale Wörterbuch.&nbsp; Eigentlich schon bekannte Phrasen können nicht für die Datenkomprimierung verwendet werden, wenn sie mehr als&nbsp; $G$&nbsp; Zeichen vorher im Text aufgetreten sind.&nbsp; Dagegen sind bei LZ78 alle Phrasen im globalen Wörterbuch abgelegt.
+*A disadvantage of LZ77 is the local dictionary.&nbsp; Phrases that are actually already known cannot be used for data compression if they occurred more than&nbsp; $G$&nbsp; characters earlier in the text.&nbsp; In contrast, with LZ78 all phrases are stored in the global dictionary.
-*Richtig ist zwar, dass bei LZ78 nur Pärchen&nbsp; $(I, \ Z)$&nbsp; übertragen werden müssen, während bei LZ77 jeder Codierschritt durch ein Triple&nbsp; $(P, \ L, \ Z)$&nbsp; gekennzeichnet ist.&nbsp; Das bedeutet aber noch nicht, dass pro Codierschritt auch weniger Bit übertragen werden müssen.
+*It is true that with LZ78 only pairs&nbsp; $(I, \ Z)$&nbsp; have to be transmitted, whereas with LZ77 each coding step is identified by a triple&nbsp; $(P, \ L, \ Z)$&nbsp;.&nbsp; However, this does not mean that fewer bits have to be transmitted per coding step.
-*Betrachten wir beispielhaft die Puffergröße&nbsp; $G = 8$.&nbsp; Bei LZ77 muss man dann&nbsp; $P$&nbsp; mit drei Bit und&nbsp; $L$&nbsp; mit vier Bit dargestellen.&nbsp; Beachten Sie bitte, dass die gefundene Übereinstimmung zwischen Vorschaupuffer und Suchpuffer auch im Vorschaupuffer enden darf.
+*Consider, for example, the buffer size&nbsp; $G = 8$.&nbsp; With LZ77, one must then represent&nbsp; $P$&nbsp; with three bits and&nbsp; $L$&nbsp; with four bits.&nbsp; Please note that the match found between the preview buffer and the search buffer may also end in the preview buffer.
-*Das neue Zeichen&nbsp; $Z$&nbsp; benötigt bei LZ78 genau die gleiche Bitanzahl wie bei LZ77 (nämlich zwei Bit), wenn man wie hier vom Symbolumfang&nbsp; $M = 4$&nbsp; ausgeht.
+*The new character&nbsp; $Z$&nbsp; requires exactly the same number of bits in LZ78 as in LZ77 (namely two bits), if one assumes the symbol range&nbsp; $M = 4$&nbsp; as here.
-*Die Aussage 2 wäre nur dann richtig, wenn&nbsp; $N_{\rm I}$&nbsp; kleiner wäre als&nbsp; $N_{\rm P}+ N_{\rm L}$, beispielsweise&nbsp; $N_{\rm I} = 6$. Das würde aber bedeuten, dass man die Wörterbuchgröße auf&nbsp; $I = 2^6 = 64$&nbsp; begrenzen müsste.&nbsp; Dies reicht für große Dateien nicht aus.
+*Statement 2 would only be correct if&nbsp; $N_{\rm I}$&nbsp; were smaller than&nbsp; $N_{\rm P}+ N_{\rm L}$, for example&nbsp; $N_{\rm I} = 6$. But this would mean that one would have to limit the dictionary size to&nbsp; $I = 2^6 = 64$&nbsp;.&nbsp; This is not sufficient for large files.
-*Unsere Überschlagsrechnung basiert allerdings auf einer einheitlichen Bitanzahl für den Index&nbsp; $I$.&nbsp; Mit variabler Bitanzahl für den Index kann man etliche Bit einsparen, indem man&nbsp; $I$&nbsp; nur mit so vielen Bit überträgt, wie es für den Codierschritt&nbsp; $i$&nbsp; erforderlich ist.
+*Our rough calculation, however, is based on a uniform number of bits for the index&nbsp; $I$.&nbsp; With a variable number of bits for the index, you can save quite a few bits by transmitting&nbsp; $I$&nbsp; only with as many bits as are necessary for the coding step&nbsp; $i$&nbsp;.
-*Prinzipiell ändert das aber nichts an der Beschränkung der Wörterbuchgröße, was bei großen Dateien stets zu Problemen führen wird.
+*In principle, however, this does not change the limitation of the dictionary size, which will always lead to problems with large files.
 {{ML-Fuß}}

← Older revision		Revision as of 15:03, 12 July 2021
Line 38:		Line 38:
	*The original literature  [LZ77]  on this method is: <br>       Ziv, J.; Lempel, A.:  A Universal Algorithm for Sequential Data Compression.  In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.		*The original literature  [LZ77]  on this method is: <br>       Ziv, J.; Lempel, A.:  A Universal Algorithm for Sequential Data Compression.  In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.

−	*  [[Aufgaben:Exercise_2.4:~~_About_the_LZW_algorithm~~\|Exercise 2.3]]  and  [[Aufgaben:Exercise_2.4:_About_the_LZW_algorithm\|Exercise 2.4]]  deal with other Lempel–Ziv methods in a similar way.	+	*  [[Aufgaben:Exercise_2.3:_About_the_LZ78_Compression\|Exercise 2.3]]  and  [[Aufgaben:Exercise_2.4:_About_the_LZW_algorithm\|Exercise 2.4]]  deal with other Lempel–Ziv methods in a similar way.

← Older revision		Revision as of 15:01, 12 July 2021
Line 38:		Line 38:
	*The original literature  [LZ77]  on this method is: <br>       Ziv, J.; Lempel, A.:  A Universal Algorithm for Sequential Data Compression.  In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.		*The original literature  [LZ77]  on this method is: <br>       Ziv, J.; Lempel, A.:  A Universal Algorithm for Sequential Data Compression.  In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.

−	*  [[Aufgaben:2.~~3_Zur_LZ78-Komprimierung~~\|Exercise 2.3]]  and  [[Aufgaben:~~Aufgabe_2~~.4:~~_Zum_LZW-Algorithmus~~\|Exercise 2.4]]  deal with other Lempel–Ziv methods in a similar way.	+	*  [[Aufgaben:Exercise_2.4:_About_the_LZW_algorithm\|Exercise 2.3]]  and  [[Aufgaben:Exercise_2.4:_About_the_LZW_algorithm\|Exercise 2.4]]  deal with other Lempel–Ziv methods in a similar way.

@@ Line 4: / Line 4: @@
 [[File:P_ID2436__Inf_Z_2_3.png|right|frame|Sliding–Window with&nbsp; $G = 4$&nbsp; and&nbsp; $G = 5$<br>(valid for "LZ77")]]
-In&nbsp; [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Exercise 2.3]],&nbsp; you were supposed to compress&nbsp; "<b>BARBARA&ndash;BAR</b>"&nbsp; (string of length&nbsp; $11$, four different characters)&nbsp; using the LZ78 algorithm.&nbsp;
+In&nbsp; [[Aufgaben:Exercise_2.3:_About_the_LZ78_Compression|Exercise 2.3]],&nbsp; you were supposed to compress&nbsp; "<b>BARBARA&ndash;BAR</b>"&nbsp; (string of length&nbsp; $11$, four different characters)&nbsp; using the LZ78 algorithm.&nbsp;
 In this exercise we use the same text to demonstrate LZ77 compression.&nbsp; To note:

@@ Line 4: / Line 4: @@
 [[File:P_ID2436__Inf_Z_2_3.png|right|frame|Sliding–Window with&nbsp; $G = 4$&nbsp; and&nbsp; $G = 5$<br>(valid for "LZ77")]]
-In &nbsp; [[Aufgaben:2.3_Zur_LZ78-Komprimierung|task 2.3]]&nbsp;, you were supposed to compress&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; (string of length&nbsp; $11$, four different characters)&nbsp; using the LZ78 algorithm.&nbsp;
+In&nbsp; [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Exercise 2.3]],&nbsp; you were supposed to compress&nbsp; "<b>BARBARA&ndash;BAR</b>"&nbsp; (string of length&nbsp; $11$, four different characters)&nbsp; using the LZ78 algorithm.&nbsp;
-In this task we use the same text to demonstrate LZ77 compression.&nbsp; To note:
+In this exercise we use the same text to demonstrate LZ77 compression.&nbsp; To note:
-* While the successor "LZ78" successively builds a global dictionary, "LZ77" uses a local dictionary.
+* While the successor&nbsp; "LZ78"&nbsp; successively builds a global dictionary,&nbsp; "LZ77"&nbsp; uses a local dictionary.
-* The LZ77 method works with a&nbsp; <i>Sliding Window</i> that is gradually shifted over the input text.
+* The LZ77 method works with a&nbsp; "Sliding Window"&nbsp; that is gradually shifted over the input text.
-* This "sliding window" is divided into the&nbsp; ''preview buffer''&nbsp; (highlighted in blue in the graphic) and the&nbsp; ''search buffer''&nbsp; (highlighted in red).&nbsp; Both buffers have a size of&nbsp; $G$&nbsp; memory locations each.
+* This&nbsp; "sliding window"&nbsp; is divided into the&nbsp; "preview buffer"&nbsp; (highlighted in blue in the graphic)&nbsp; and the&nbsp; "search buffer"&nbsp; (highlighted in red).&nbsp; Both buffers have a size of&nbsp; $G$&nbsp; memory locations each.
-* Each coding step&nbsp; $i$&nbsp; is characterised by a number triple&nbsp; $(P,\ L,\ Z)$&nbsp;.&nbsp; Here,&nbsp; $P$&nbsp; and&nbsp; $L$&nbsp; are integers and&nbsp; $Z$&nbsp; is a character.&nbsp; The binary representations of&nbsp; $P$,&nbsp; $L$&nbsp; and&nbsp; $Z$.
+* Each coding step&nbsp; $i$&nbsp; is characterised by a triple&nbsp; $(P,\ L,\ Z)$.&nbsp; Here,&nbsp; $P$&nbsp; and&nbsp; $L$&nbsp; are integers and&nbsp; $Z$&nbsp; is a character.&nbsp; Transmitted are the binary representations of&nbsp; $P$,&nbsp; $L$&nbsp; and&nbsp; $Z$.
-* After transmission, the&nbsp; <i>Sliding Window</i>&nbsp; is shifted one or more positions to the right and the next coding step&nbsp; $i + 1$ begins.
+* After transmission, the&nbsp; sliding window&nbsp; is shifted one or more positions to the right and the next coding step&nbsp; $i + 1$ begins.
 The upper diagram shows the initial allocation with the buffer size&nbsp; $G = 4$&nbsp; at the times&nbsp; $i = 1$&nbsp; as well as&nbsp; $i = 4$.
 *At time&nbsp; $i = 1$&nbsp;, the search buffer is empty, so the coder output is&nbsp; $(0, 0,$ <b>B</b>$)$&nbsp;.
-*After the shift by one position, the search buffer contains a&nbsp; <b>B</b>, but no string that begins with&nbsp; <b>A</b>&nbsp;.&nbsp; The second number triple is therefore&nbsp; $(0, 0,$ <b>A</b>$)$.
+*After the shift by one position, the search buffer contains a&nbsp; <b>B</b>, but no string that begins with&nbsp; <b>A</b>.&nbsp; The second number triple is therefore&nbsp; $(0, 0,$ <b>A</b>$)$.
 *The output for&nbsp; $i = 3$&nbsp; is&nbsp; $(0, 0,$ <b>R</b>$)$, since there is no string beginning with&nbsp; <b>R</b>&nbsp; in the search buffer even now.
 The snapshot at time&nbsp; $i = 4$&nbsp; is also shown in the graphic.&nbsp; The search is now for the character string in the search buffer that best matches the preview text&nbsp; <b>BARA</b>&nbsp;.&nbsp; A number triple&nbsp; $(P,\ L,\ Z)$, is transmitted again, but now with the following meaning:
-* $P$&nbsp; indicates the position in the (red) search buffer where the match starts.&nbsp; The&nbsp; $P$& values of the individual memory locations can be seen in the graphic.
+* $P$&nbsp; indicates the position in the (red) search buffer where the match starts.&nbsp; The&nbsp; $P$&nbsp; values of the individual memory locations can be seen in the graphic.
-* $L$&nbsp; denotes the number of characters in the search buffer that, starting at&nbsp; $P$&nbsp; , match the current string in the preview buffer.
+* $L$&nbsp; denotes the number of characters in the search buffer that, starting at&nbsp; $P$,&nbsp; match the current string in the preview buffer.
 * Finally $Z$&nbsp; denotes the first character in the preview buffer that differs from the matching string found in the search buffer.
 The larger the LZ77 parameter&nbsp; $G$&nbsp;, the easier it is to find the longest possible match.&nbsp; In subtask&nbsp; '''(4)'''&nbsp;  you will notice that the LZ77 encoding with&nbsp; $G = 5$&nbsp; gives a better result than the one with&nbsp; $G = 4$.
-* However, because of the later binary representation of&nbsp; $P$,&nbsp; , one will always choose&nbsp; $G$&nbsp; as a power of two, so that&nbsp; $G$&nbsp; can be represented with&nbsp; $\log_2 \ P$&nbsp; bits&nbsp; $(G = 8$ &nbsp; &#8658; &nbsp; three-digit binary number&nbsp; $P)$.
+* However, because of the later binary representation of&nbsp; $P$,&nbsp; one will always choose&nbsp; $G$&nbsp; as a power of two, so that&nbsp; $G$&nbsp; can be represented with&nbsp; $\log_2 \ P$&nbsp; bits&nbsp; $(G = 8$ &nbsp; &#8658; &nbsp; three-digit binary number&nbsp; $P)$.
-*This means that a&nbsp; <i>Sliding Window</i>&nbsp; with&nbsp; $G = 5$&nbsp; has rather little practical relevance.
+*This means that a&nbsp; "Sliding Window"&nbsp; with&nbsp; $G = 5$&nbsp; has rather little practical relevance.
@@ Line 36: / Line 36: @@
 *The task 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#LZ77_-_the_basic_form_of_the_Lempel-Ziv_algorithms|LZ77 &ndash; the basic form of the Lempel-Ziv algorithms]]&nbsp;.
-*The original literature&nbsp; [LZ77]&nbsp; on this method is: <br>Ziv, J.; Lempel, A.: ''A Universal Algorithm for Sequential Data Compression.'' In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.
+*The original literature&nbsp; [LZ77]&nbsp; on this method is: <br> &nbsp; &nbsp; &nbsp; Ziv, J.; Lempel, A.:&nbsp; A Universal Algorithm for Sequential Data Compression.&nbsp; In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.
-*&nbsp; [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Task 2.3]]&nbsp; and&nbsp; [[Aufgaben:Aufgabe_2.4:_Zum_LZW-Algorithmus|task 2.4]]&nbsp; deal with other Lempel&ndash;Ziv methods in a similar way.
+*&nbsp; [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Exercise 2.3]]&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.