Aufgaben:Aufgabe 2.3: Zur LZ78-Komprimierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(12 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2434__Inf_A_2_3.png|right|Abraham Lempel und Jacob Ziv ]]
+
[[Datei:P_ID2434__Inf_A_2_3.png|right|frame|Die LZ78–Erfinder]]
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 [https://de.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel] und [https://de.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv] entwickelten Komprimierungsverfahren nicht gegeben. Man spricht von ''universeller Quellencodierung''.
+
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  [https://de.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]  und  [https://de.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]  entwickelten Komprimierungsverfahren nicht gegeben.  Man spricht von  '''universeller Quellencodierung'''.
  
Wir betrachten in dieser Aufgabe die 1978 erstmals veröffentlichte Variante [LZ78].  Codiert werden soll der String &nbsp;<b>BARBARA&ndash;BAR</b>.
+
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>.
*LZ78 arbeitet mit einem globalen Wörterbuch, das zu Beginn nur mit einem leeren Zeichen (<b>&epsilon;</b>) unter dem Index <i>I</i> = 0 gefüllt ist. Dadurch unterscheidet sich &bdquo;LZ78&rdquo; von seinem Vorgänger &bdquo;LZ77&rdquo; (mit lokalem Wörterbuch) und auch von seinem Nachfolger &bdquo;LZW&rdquo; (Wörterbuch ist mit den möglichen Zeichen vorbelegt).
+
*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 &bdquo;LZ78&rdquo; von seinem Vorgänger &bdquo;LZ77&rdquo; (mit lokalem Wörterbuch) und auch von seinem Nachfolger &bdquo;LZW&rdquo; (Wörterbuch ist mit den möglichen Zeichen vorbelegt).
*Wird ein Zeichen oder ein Wortfragment (mehrere Zeichen) des Eingabestrings im Wörterbuch gefunden, so wird der Index <i>I</i><sub>0</sub> dieses Eintrags zusammen mit dem nächsten Eingangszeichen ''Z'' ausgegeben. In jedem Schritt '''' lautet also die Ausgabe: &nbsp;  (<i>I</i><sub>0</sub>, ''Z'').
+
*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)$.
*Anschließend wird der neue String unter dem nächsten freien Index <i>I</i><sub>neu</sub> ins Wörterbuch eingetragen. Betrachtet man das Wörterbuch als ein Feld ''W''[''I''] mit ''I'' &ge; 0, bei dem ein jedes Element eine Zeichenkette beliebiger Länge enthält, so gilt mit der Character&ndash;Variablen ''Z'':
+
*Anschließend wird der neue String unter dem nächsten freien Index&nbsp; $I_{\rm neu}$&nbsp; ins Wörterbuch eingetragen.  
:$$W (I_{\rm neu}) = W(I_0) + Z \hspace{0.05cm}. $$
+
*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$:
 +
:$$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:
 
Zur Verdeutlichung ein einfaches Beispiel:
*Zu einem gegebenen Zeitpunkt ist das Wörterbuch bis zum Index <i>I</i><sub>akt</sub>= 20 gefüllt.
+
*Zu einem gegebenen Zeitpunkt ist das Wörterbuch bis zum Index&nbsp; $I_{\rm akt }= 20$&nbsp; gefüllt.
*Zur Codierung steht '''Handy''' an. Im Wörterbuch findet man unter dem Index ''I'' = 11 den Eintrag <b>Ha</b> und unter dem Index ''I'' = 16 den Eintrag <b>Han</b>.
+
*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>".
*Somit lautet die aktuelle Coderausgabe &nbsp;  (<i>I</i><sub>0</sub>''Z'') = (16, <b>d</b>) und ins Wörterbuch wird als neue Phrase eingetragen: ''W''(21) = <b>Hand</b>.
+
*Somit lautet die aktuelle Coderausgabe &nbsp;  $(I_0,  Z) = (16,$ <b>d</b>$)$&nbsp; und ins Wörterbuch wird als neue Phrase eingetragen:  
*Nun liegt der String <b>y</b> zur Codierung an. Findet man hierfür keinen passenden Eintrag, so wird (0, <b>y</b>) ausgegeben und ''W''(22) = <b>&epsilon;</b> <b>y</b> = <b>y</b> neu ins Wörterbuch eingetragen.
+
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  $W(21) =$ <b>Hand</b>.
 +
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; $W(22) =  \rm &epsilon;$&nbsp; +  <b>y</b> $=$ <b>y</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; &nbsp; &nbsp; &nbsp; &nbsp; &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:
 +
* Die Dezimalzahl&nbsp; $I$&nbsp; (Index) wird durch drei Bit binär dargestellt.
 +
* 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.
 +
 
 +
 
 +
 
 +
 
  
Für die Teilaufgabe (6) können Sie von folgenden Voraussetzungen ausgehen:
 
* Die Dezimalzahl ''I'' (Index) wird durch drei Bit binär dargestellt.
 
* Das Zeichen ''Z'' &#8712; {<b>A</b>, <b>B</b>, <b>R</b>, <b>&ndash;</b>} wird mit jeweils zwei Bit binär codiert.
 
  
  
 
''Hinweise:''  
 
''Hinweise:''  
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch|Komprimierung nach Lempel, Ziv und Welch]].
+
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch|Komprimierung nach Lempel, Ziv und Welch]].
*Insbesondere wird auf die Seite [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|Die Lempel-Ziv-Variante LZ78]] Bezug genommen.
+
*Insbesondere wird auf die Seite&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|Die Lempel-Ziv-Variante LZ78]]&nbsp; Bezug genommen.
*Die Originalliteratur [LZ78] zu diesem Verfahren lautet: 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.
+
*Die Originalliteratur&nbsp; [LZ78]&nbsp; zu diesem Verfahren lautet: &nbsp; <br>&nbsp; &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.
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
+
*Die [[Aufgaben:2.3Z_Zur_LZ77-Codierung|Zusatzaufgabe 2.3Z]] sowie die [[Aufgaben:2.4_LZW-Algorithmus|Aufgabe 2.4]] behandeln andere LZ-Verfahren in ähnlicher Weise.
+
*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.
  
  
Zeile 35: Zeile 45:
 
<quiz display=simple>
 
<quiz display=simple>
 
{Welche Aussagen gelten für die Vorbelegung des LZ78&ndash;Wörterbuches?
 
{Welche Aussagen gelten für die Vorbelegung des LZ78&ndash;Wörterbuches?
|type="[]"}
+
|type="()"}
+ Vorbelegt ist nur der Index <i>I</i> = 0 mit dem Leerzeichen (<i>&epsilon;</i>).
+
+ Vorbelegt ist nur der Index&nbsp; $I = 0$&nbsp; mit dem Leerzeichen&nbsp; $(\varepsilon)$.
- Vorbelegt sind die Indizes <i>I</i> = 0 bis <i>I</i> = 3 mit den vier Zeichen.
+
- 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;''' .
  
  
{Was geschieht im Codierschritt <i>i</i> = 1?
+
{Was geschieht im Codierschritt&nbsp; $i = 1$?
 
|type="[]"}
 
|type="[]"}
+ Die Coderausgabe lautet (0, <b>B</b>).
+
+ Die Coderausgabe lautet: &nbsp; $(0,$ <b>B</b>$)$.
+ Der Wörterbucheintrag lautet: <i>W</i>(<i>I</i> = 1) = <b>B</b>.
+
+ Der Wörterbucheintrag lautet: &nbsp; $W(I = 1) =$ <b>B</b>.
- Der Wörterbucheintrag lautet: <i>W</i>(<i>I</i> = 1) = <b>BA</b>.
+
- Der Wörterbucheintrag lautet: &nbsp; $W(I = 1) =$ <b>BA</b>.
  
  
{Welche Aussagen gelten für die Codierschritte <i>i</i> = 2 und <i>i</i> = 3?
+
{Welche Aussagen gelten für die Codierschritte&nbsp; $i = 2$&nbsp; und&nbsp; $i = 3$?
 
|type="[]"}
 
|type="[]"}
+ Für <i>i</i> = 2 gilt: Ausgabe (0, <b>A</b>), Eintrag <i>W</i>(<i>I</i> = 2) = <b>A</b>.
+
+ Für&nbsp; $i = 2$&nbsp; gilt: &nbsp; Ausgabe&nbsp; $(0,$ <b>A</b>$)$, &nbsp; Eintrag&nbsp; $W(I = 2) =<b>A</b>.
+ Für <i>i</i> = 3 gilt: Ausgabe (0, <b>R</b>), Eintrag <i>W</i>(<i>I</i> = 3) = <b>R</b>.
+
+ Für&nbsp; $i = 3$&nbsp; gilt: &nbsp; Ausgabe&nbsp; $(0,$ <b>R</b>$)$, &nbsp; Eintrag&nbsp; $W(I = 3) =$ <b>R</b>.
  
  
{Welche Aussagen gelten für den Codierschritt <i>i</i> = 4?
+
{Welche Aussagen gelten für den Codierschritt&nbsp; $i = 4$?
 
|type="[]"}
 
|type="[]"}
- Bei Schritt <i>i</i> = 4 wird <b>BAR</b> gemeinsam codiert.
+
- Bei Schritt&nbsp; $i = 4$&nbsp; wird&nbsp; <b>BAR</b>&nbsp; gemeinsam codiert.
+ Bei Schritt <i>i</i> = 4 wird <b>BA</b> gemeinsam codiert.
+
+ Bei Schritt&nbsp; $i = 4$&nbsp; wird&nbsp; <b>BA</b>&nbsp; gemeinsam codiert.
- Die Coderausgabe lautet (2, <b>AR</b>).
+
- Die Coderausgabe lautet: &nbsp; $(2,$ <b>AR</b>$)$.
+ Die Coderausgabe lautet (1, <b>A</b>).
+
+ Die Coderausgabe lautet: &nbsp; $(1,$ <b>A</b>$)$.
  
  
{Vervollständigen Sie die LZ78&ndash;Codierung. Nach welchem Codierschritt <i>i</i> ist <b>BARBARA&ndash;BAR</b> vollständig codiert?
+
{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?
 
|type="{}"}
 
|type="{}"}
$i$ = { 7 3% }
+
$i_{\rm Ende} \ = \ $ { 7 3% }
  
  
{Wieviele Binärzeichen benötigt man, um <b>BARBARA&ndash;BAR</b> zu codieren? Beachten Sie die Hinweise auf der Angabenseite.
+
{Wieviele Binärzeichen benötigt man, um&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; zu codieren?&nbsp; Beachten Sie die Hinweise auf der Angabenseite.
 
|type="{}"}
 
|type="{}"}
$ohne\ Codierung:\ N$ = { 22 3% } $bit$
+
$\text{ohne Codierung: }\ N \ = \ $ { 22 3% } $\ \rm Bit$
$mit\ LZ78-Codierung:\ N$ = { 35 3% } $bit$
+
$\text{mit LZ78-Codierung: }\ N \ = \ $ { 35 3% } $\ \rm Bit$
  
  
Zeile 77: Zeile 87:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>1.</b>&nbsp;&nbsp;Zutreffend für den LZ78&ndash;Algorithmus ist <u>Aussage 1</u>. Die Vorbelegung gemäß Aussage 2 gilt dagegen für den LZW&ndash;Algorithmus, der 1983 gemeinsam mit Terry Welch veröffentlicht wurde.
+
'''(1)'''&nbsp; Zutreffend für den LZ78&ndash;Algorithmus ist <u>Aussage 1</u>:
 +
*Die Vorbelegung gemäß Aussage 2 gilt dagegen für den LZW&ndash;Algorithmus, der 1983 gemeinsam mit Terry Welch veröffentlicht wurde.
  
:<b>2.</b>&nbsp;&nbsp;<b>&epsilon;</b> bezeichnet das leere Zeichen. Da <b>&epsilon;</b> + <b>B</b> = <b>B</b> ergibt, sind die <u>Aussagen 1 und 2</u> richtig. Dagegen würde die Aussage 3 wieder für die LZW&ndash;Komprimierung zutreffen.
 
  
:<b>3.</b>&nbsp;&nbsp;<u>Beide Aussagen</u> treffen zu.
 
  
:<b>4.</b>&nbsp;&nbsp;Im Wörterbuch wird unter dem Index <i>I</i> = 1 das Zeichen <b>B</b> gefunden und das nächste Zeichen <b>A</b> der Eingangsfolge wird angehängt: (1, <b>A</b>). Richtig sind somit die <u>Aussagen 2 und 4</u>. Die Aussage 3 kann schon deshalb nicht stimmen, da <i>Z</i> nur ein Zeichen sein kann und keine Zeichenfolge.
+
'''(2)'''&nbsp; $\rm &epsilon;$&nbsp; bezeichnet das leere Zeichen.&nbsp;
 +
*Da&nbsp; $\rm &epsilon;$ + <b>B</b> = <b>B</b>&nbsp; ergibt, sind die <u>Aussagen 1 und 2</u> richtig.  
 +
*Aussage 3 trifft wieder nur für die LZW&ndash;Komprimierung zu.
  
:<b>5.</b>&nbsp;&nbsp;Der gesamte Codiervorgang ist in einer Tabelle zusammengefasst:
 
[[Datei:P_ID2435__Inf_A_2_3f.png|center|]]
 
:Man erkennt:
 
  
:* Zu jedem Zeitpunkt <i>i</i> wird die bearbeitete Zeichenfolge in das Wörterbuch eingetragen.
 
  
:* Zum Zeitpunkt <u><i>i</i> = 7</u> ist der Codiervorgang abgeschlossen.
+
'''(3)'''&nbsp; Hier treffen <u>beide Aussagen</u> zu.
  
:<b>6.</b>&nbsp;&nbsp; Stellt man alle Indizes mit 3 Bit dar und die vier Zeichen (Character) mit je 2 Bit, so kommt man zu folgenden Ergebnissen:
 
  
:* ohne Codierung: <i>N</i> = 11 &middot; 2 = <u>22 Bit</u>,
 
  
:* mit LZ78&ndash;Codierung: <i>N</i> = 7 &middot; (3 + 2) = <u>35 Bit</u>.
+
'''(4)'''&nbsp; Richtig sind die <u>Aussagen 2 und 4</u>:
 +
*Im Wörterbuch wird unter dem Index&nbsp; $I = 1$&nbsp; das Zeichen&nbsp; <b>B</b>&nbsp; gefunden.
 +
*Das nächste Zeichen&nbsp; <b>A</b>&nbsp; der Eingangsfolge wird angehängt: &nbsp; <b>(1, A)</b>.
 +
*Die Aussage 3 kann schon deshalb nicht stimmen, da&nbsp; $Z$&nbsp; nur ein Zeichen sein kann und keine Zeichenfolge.
  
: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 <b>BARBARA&ndash;BAR</b> dem LZ78&ndash;Algorithmus entgegenkommt.
 
  
:* Mit variabler Bitanzahl für den Index entsprechend der Theorieseite 5 und Aufgabe A2.4 ergibt sich für dieses LZ78-Beispiel
+
[[Datei:Inf_A_2_3f_version2.png|right|frame|LZ78–Codierung des Strings&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.
 +
* Zum Zeitpunkt&nbsp; $\underline{i=7}$&nbsp; ist der Codiervorgang abgeschlossen.
 +
 
 +
 
 +
 
 +
'''(6)'''&nbsp; Stellt man alle Indizes mit drei Bit dar und die vier Zeichen (Character) mit je zwei Bit, so kommt man zu folgenden Ergebnissen:
 +
* ohne Codierung: &nbsp; $N = 11 \cdot 2 \hspace{0.15cm}\underline {= 22 \, \rm Bit}$,
 +
* mit LZ78&ndash;Codierung: &nbsp; $N = 7 \cdot (3+2) \hspace{0.15cm}\underline {= 35 \, \rm Bit}$.
 +
 
 +
 
 +
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.
 +
* Mit variabler Bitanzahl für den Index entsprechend der Aufgabe 2.4 würde sich für dieses LZ78-Beispiel ergeben:
 
:$$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 Bit}\hspace{0.05cm}.$$
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
==Quellenverzeichnis==
+
 
<references/>
 
  
  

Aktuelle Version vom 12. Juli 2021, 14:28 Uhr

Die LZ78–Erfinder

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  Abraham Lempel  und  Jacob Ziv  entwickelten Komprimierungsverfahren nicht gegeben.  Man spricht von  universeller Quellencodierung.

Wir betrachten in dieser Aufgabe die 1978 erstmals veröffentlichte Variante  [LZ78].  Codiert werden soll der String  BARBARA–BAR.

  • Das Verfahren LZ78 arbeitet mit einem globalen Wörterbuch, das zu Beginn nur mit einem leeren Zeichen  $(\varepsilon)$  unter dem Index  $I = 0$  gefüllt ist.  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).
  • Wird ein Zeichen oder ein Wortfragment (mehrere Zeichen) des Eingabestrings im Wörterbuch gefunden, so wird der Index  $I_0$  dieses Eintrags zusammen mit dem nächsten Eingangszeichen  $Z$  ausgegeben.  In jedem Schritt  $i$  lautet also die Ausgabe:   $(I_0, \ Z)$.
  • Anschließend wird der neue String unter dem nächsten freien Index  $I_{\rm neu}$  ins Wörterbuch eingetragen.
  • Betrachtet man das Wörterbuch als ein Feld  $W\big[\hspace{0.05cm}I\hspace{0.05cm}\big]$  mit  $I ≥ 0$, bei dem ein jedes Element eine Zeichenkette beliebiger Länge enthält, so gilt mit der Character–Variablen  $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:

  • Zu einem gegebenen Zeitpunkt ist das Wörterbuch bis zum Index  $I_{\rm akt }= 20$  gefüllt.
  • Zur Codierung steht  Handy  an.  Im Wörterbuch findet man unter dem Index  $I = 11$  den Eintrag  "Ha"  und unter dem Index  $I = 16$  den Eintrag "Han".
  • Somit lautet die aktuelle Coderausgabe   $(I_0, Z) = (16,$ d$)$  und ins Wörterbuch wird als neue Phrase eingetragen:

            $W(21) =$ Hand.             $W(22) = \rm ε$  + y $=$ y .

  • Nun liegt der String  y  zur Codierung an.  Findet man hierfür keinen passenden Eintrag, so wird  $(0,$ y$)$  ausgegeben und ins Wörterbuch wird neu eingetragen:

            $W(22) = \rm ε$  + y $=$ y .


Für die Teilaufgabe  (6)  können Sie von folgenden Voraussetzungen ausgehen:

  • Die Dezimalzahl  $I$  (Index) wird durch drei Bit binär dargestellt.
  • Das Zeichen  $Z ∈ \{$ABR$ \}$  wird mit jeweils zwei Bit binär codiert.




Hinweise:

  • Die Aufgabe gehört zum Kapitel  Komprimierung nach Lempel, Ziv und Welch.
  • Insbesondere wird auf die Seite  Die Lempel-Ziv-Variante LZ78  Bezug genommen.
  • Die Originalliteratur  [LZ78]  zu diesem Verfahren lautet:  
          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.


Fragebogen

1

Welche Aussagen gelten für die Vorbelegung des LZ78–Wörterbuches?

Vorbelegt ist nur der Index  $I = 0$  mit dem Leerzeichen  $(\varepsilon)$.
Vorbelegt sind die Indizes  $I = 0$  bis  $I = 3$  mit den vier Zeichen  ABR  und  .

2

Was geschieht im Codierschritt  $i = 1$?

Die Coderausgabe lautet:   $(0,$ B$)$.
Der Wörterbucheintrag lautet:   $W(I = 1) =$ B.
Der Wörterbucheintrag lautet:   $W(I = 1) =$ BA.

3

Welche Aussagen gelten für die Codierschritte  $i = 2$  und  $i = 3$?

Für  $i = 2$  gilt:   Ausgabe  $(0,$ A$)$,   Eintrag  $W(I = 2) =$ A.
Für  $i = 3$  gilt:   Ausgabe  $(0,$ R$)$,   Eintrag  $W(I = 3) =$ R.

4

Welche Aussagen gelten für den Codierschritt  $i = 4$?

Bei Schritt  $i = 4$  wird  BAR  gemeinsam codiert.
Bei Schritt  $i = 4$  wird  BA  gemeinsam codiert.
Die Coderausgabe lautet:   $(2,$ AR$)$.
Die Coderausgabe lautet:   $(1,$ A$)$.

5

Vervollständigen Sie die LZ78–Codierung.  Nach welchem Codierschritt  $i_{\rm Ende}$  ist  BARBARA–BAR  vollständig codiert?

$i_{\rm Ende} \ = \ $

6

Wieviele Binärzeichen benötigt man, um  BARBARA–BAR  zu codieren?  Beachten Sie die Hinweise auf der Angabenseite.

$\text{ohne Codierung: }\ N \ = \ $

$\ \rm Bit$
$\text{mit LZ78-Codierung: }\ N \ = \ $

$\ \rm Bit$


Musterlösung

(1)  Zutreffend für den LZ78–Algorithmus ist Aussage 1:

  • Die Vorbelegung gemäß Aussage 2 gilt dagegen für den LZW–Algorithmus, der 1983 gemeinsam mit Terry Welch veröffentlicht wurde.


(2)  $\rm ε$  bezeichnet das leere Zeichen. 

  • Da  $\rm ε$ + B = B  ergibt, sind die Aussagen 1 und 2 richtig.
  • Aussage 3 trifft wieder nur für die LZW–Komprimierung zu.


(3)  Hier treffen beide Aussagen zu.


(4)  Richtig sind die Aussagen 2 und 4:

  • Im Wörterbuch wird unter dem Index  $I = 1$  das Zeichen  B  gefunden.
  • Das nächste Zeichen  A  der Eingangsfolge wird angehängt:   (1, A).
  • Die Aussage 3 kann schon deshalb nicht stimmen, da  $Z$  nur ein Zeichen sein kann und keine Zeichenfolge.


LZ78–Codierung des Strings  BARBARA–BAR

(5)  Der gesamte Codiervorgang ist in einer Tabelle zusammengefasst. Man erkennt:

  • Zu jedem Zeitpunkt  $i$  wird die bearbeitete Zeichenfolge in das Wörterbuch eingetragen.
  • Zum Zeitpunkt  $\underline{i=7}$  ist der Codiervorgang abgeschlossen.


(6)  Stellt man alle Indizes mit drei Bit dar und die vier Zeichen (Character) mit je zwei Bit, so kommt man zu folgenden Ergebnissen:

  • ohne Codierung:   $N = 11 \cdot 2 \hspace{0.15cm}\underline {= 22 \, \rm Bit}$,
  • mit LZ78–Codierung:   $N = 7 \cdot (3+2) \hspace{0.15cm}\underline {= 35 \, \rm Bit}$.


Daran erkennt man:

  • Eine jede LZ–Komprimierung macht erst bei einer größeren Datei Sinn, auch dann, wenn man glaubt, dass ein Text wie  BARBARA–BAR  dem LZ78–Algorithmus entgegenkommt.
  • Mit variabler Bitanzahl für den Index entsprechend der Aufgabe 2.4 würde sich für dieses LZ78-Beispiel ergeben:
$$N = 1 \cdot 3 + 2 \cdot 4 + 4 \cdot 5 = 31 \,{\rm Bit}\hspace{0.05cm}.$$