faecher:informatik:oberstufe:codierung:lzw:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:codierung:lzw:start [03.10.2022 18:13] – [Decodierung] Frank Schiebelfaecher:informatik:oberstufe:codierung:lzw:start [05.12.2023 14:52] (aktuell) – Frank Schiebel
Zeile 42: Zeile 42:
 | **BAA**                            | BAA ←102<sub>16</sub>  | 102<sub>16</sub>  |                          | | **BAA**                            | BAA ←102<sub>16</sub>  | 102<sub>16</sub>  |                          |
  
-Die Zeichenfolge wird also folgendermaßen codiert: 042041100101102<sub>16</sub>. Das sind 7,5 Bytes ((wenn man mit ganzen Bytes arbeiten möchte, wird das mit Nullen zu 8 Byte aufgefüllt)). Die Kompression ist also bei solch kurzen Zeichenketten noch nicht drastisch - wenn man sich jedoch vorstellt, dass das Wörterbuch stets längere Zeichenketten mit einem einzigen 12Bit Code zugreifbar macht, kann die Kompression unter Umständen bei längeren Texten deutlich stärker ins Gewicht fallen.+Die Zeichenfolge wird also folgendermaßen codiert: **042041100101102<sub>16</sub>**. Das sind 7,5 Bytes ((wenn man mit ganzen Bytes arbeiten möchte, wird das mit Nullen zu 8 Byte aufgefüllt)). Die Kompression ist also bei solch kurzen Zeichenketten noch nicht drastisch - wenn man sich jedoch vorstellt, dass das Wörterbuch stets längere Zeichenketten mit einem einzigen 12Bit Code zugreifbar macht, kann die Kompression unter Umständen bei längeren Texten deutlich stärker ins Gewicht fallen.
  
 ==== Decodierung ==== ==== Decodierung ====
  
-Bei der **Decodierung** werden 12-Bit-Blöcke eingelesen. Das Wörterbuch wird während des Vorgangs mit Einträgen befüllt die aus dem ersten Zeichen des aktuellen Eintrag und dem vorangehenden Eintrag bestehen.+Bei der **Decodierung** werden 12-Bit-Blöcke eingelesen. Das Wörterbuch wird während des Vorgangs mit Einträgen befüllt die aus dem ersten Zeichen des aktuellen Eintrag und dem vorangehenden Eintrag bestehen. Wir nehmen den codierten String von oben: **042041100101102<sub>16</sub>**. 
 + 
 +^ Aktueller 12Bit-Block (Hexadezimal) ^ Gefundener Eintrag (erster Buchstabe) ^ Neuer Wörterbucheintrag ^ Ausgabe ^ 
 +| 042 | B (B) |  | B  |  
 +| 041 | A (A) | BA = 100<sub>16</sub> | A | 
 +| 100 | BA (B) | AB = 101<sub>16</sub> | BA | 
 +| 101 | AB (A) | BAA = 102<sub>16</sub> | AB | 
 +| 102 | BAA (B) | ABB = 103<sub>16</sub> | BAA |  
 + 
 +Decodiert lautet der Text also ''BABAABBAA''. 
 + 
 +<WRAP center round box 90%> 
 +**Anmerkung**: Das Wörterbuch musste zur Decodierung hier **nicht** gesondert übertragen werden - es "ensteht" während des Vorgangs. 
 +</WRAP> 
 + 
 + 
 +Für die Aufgaben kannst du die folgenden Arbeitsblätter verwenden: 
 + 
 +  * {{ :faecher:informatik:oberstufe:codierung:lzw:01_lzw-vorlage-codierung.pdf |Vorlage: Codierung}} ([[https://tube.schule.social/w/i9sHdY4SowkBccxgSvLMfb|Erklärung in diesem Video]]) 
 +  * {{ :faecher:informatik:oberstufe:codierung:lzw:01_lzw-vorlage-decodierung.pdf |Vorlage: Decodierung}} ([[https://tube.schule.social/w/7urJEcE76ZQZrYYhiLitD8|Erklärung in diesem Video]]) 
 + 
 + 
 + 
 +---- 
 +{{:aufgabe.png?nolink  |}} 
 +=== (A1) === 
 + 
 +Codiere den Text ''ABABCABCDABCD'' und vergleiche die codierte und die uncodierte Länge miteinander. 
 + 
 +++++ Lösung: |  
 +  * Codiert: 041042100043102044104 
 +  * Der uncodierte Text war 13 Zeichen = 13 Bytes lang 
 +  * Die Codierung benötigt 7*12 Bit = 10,5 Bytes lang, was am Ende 11 Bytes belegt. 
 +++++ 
 + 
 +---- 
 +{{:aufgabe.png?nolink  |}} 
 +=== (A2) === 
 + 
 +Decodiere folgenden Code: ''058 059 05A 101 100 103''. [[faecher:informatik:oberstufe:codierung:zeichencodierung:ascii:start|Die ASCII-Tabelle findest du hier]] 
 + 
 +++++ Lösung: |  
 +Daraus wird der Text: ''XYZYZXYYZX'' 
 +++++ 
 + 
 +---- 
 +{{:aufgabe.png?nolink  |}} 
 +=== (A3) === 
 + 
 +Versuche, den Code ''042041100101041104'' zu decodieren. Welches Problem ergibt sich dabei? 
 + 
 +++++ Lösung: | 
 +Im letzten Schritt wird auf den Eintrag ''104'' verwiesen, der bei der Decodierung jedoch noch nicht existiert. Das ist ein Sonderfall, der auftritt, wenn eine Zeichenfolge mehrfach direkt hintereinander vorkommt. Dann gilt: der „gefundene“ Eintrag entspricht dem vorherigen Eintrag + dem ersten Buchstaben des vorherigen Eintrags. 
 +++++ 
 + 
 +---- 
 +{{:aufgabe.png?nolink  |}} 
 +=== (A4) === 
 +Der folgende LZW-Code: 0 1 2 4 6 5 7 7 3 codiert eine Pixelgrafik, die 4 Pixel breit ist. Die einzelnen auftretenden Pixel haben den folgenden "Grundcode":   
 + 
 +{{ :faecher:informatik:oberstufe:codierung:lzw:pixel.png?200 |}} 
 + 
 +---- 
 +{{:aufgabe.png?nolink  |}} 
 +=== (A5) === 
 + 
 +Erläutere in einem kurzen Text das Grundprinzip der Komprimierung beim LZW-Verfahren. 
 + 
 + 
 +---- 
 +{{:aufgabe.png?nolink  |}} 
 +=== (A6) === 
 + 
 +Begründe, dass das LZW-Verfahren nicht jede Eingabe komprimieren kann.  
 + 
 +++++ Lösung |  
 +Das LZW-Verfahren ist ein verlustfreies Verfahren, d.h. jede Eingabe ist eindeutig wiederherstellbar. Zu jeder 
 +komprimierten Bitfolge gehört damit genau eine Eingabe. Es kann kein verlustfreies Verfahren geben, das 
 +jede Eingabe komprimiert. 
 + 
 +Begründung: Wenn es ein Verfahren gäbe, das jede Eingabe verkürzen kann, könnte man dieses wiederholt anwenden, bis die Ausgabe nur noch 1 Bit lang wäre. Diese könnte genau zwei Werte annehmen, 0 oder 
 +1. Daraus könnte man aber höchstens zwei Eingaben rekonstruieren. 
 +++++ 
 ===== Material ===== ===== Material =====
  
 {{simplefilelist>.:*}} {{simplefilelist>.:*}}
  
  • faecher/informatik/oberstufe/codierung/lzw/start.1664813634.txt.gz
  • Zuletzt geändert: 03.10.2022 18:13
  • von Frank Schiebel