Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
faecher:informatik:oberstufe:codierung:lzw:start [03.10.2022 16:12] – [Beispiel] Frank Schiebel | faecher:informatik:oberstufe:codierung:lzw:start [03.10.2022 17:08] – [Decodierung] Frank Schiebel | ||
---|---|---|---|
Zeile 28: | Zeile 28: | ||
===== Beispiel ===== | ===== Beispiel ===== | ||
+ | |||
+ | ==== Codierung ==== | ||
+ | |||
{{ : | {{ : | ||
Zeile 39: | Zeile 42: | ||
| **BAA** | | **BAA** | ||
- | Die Zeichenfolge wird also folgendermaßen codiert: 042041100101102< | + | Die Zeichenfolge wird also folgendermaßen codiert: |
+ | |||
+ | ==== 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. Wir nehmen den codierten String von oben: **042041100101102< | ||
+ | |||
+ | ^ Aktueller 12Bit-Block (Hexadezimal) ^ Gefundener Eintrag (erster Buchstabe) ^ Neuer Wörterbucheintrag ^ Ausgabe ^ | ||
+ | | 042 | B (B) | | B | | ||
+ | | 041 | A (A) | BA = 100< | ||
+ | | 100 | BA (B) | AB = 101< | ||
+ | | 101 | AB (A) | BAA = 102< | ||
+ | | 102 | BAA (B) | ABB = 103< | ||
+ | |||
+ | Decodiert lautet der Text also '' | ||
+ | |||
+ | <WRAP center round box 90%> | ||
+ | **Anmerkung**: | ||
+ | </ | ||
+ | |||
+ | |||
+ | Für die Aufgaben kannst du die folgenden Arbeitsblätter verwenden: | ||
+ | |||
+ | * {{ : | ||
+ | * {{ : | ||
+ | |||
+ | |||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A1) === | ||
+ | |||
+ | Codiere den Text '' | ||
+ | |||
+ | ++++ 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. | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A2) === | ||
+ | |||
+ | Decodiere folgenden Code: '' | ||
+ | |||
+ | ++++ Lösung: | | ||
+ | Daraus wird der Text: '' | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A3) === | ||
+ | |||
+ | Versuche, den Code '' | ||
+ | |||
+ | ++++ Lösung: | | ||
+ | Im letzten Schritt wird auf den Eintrag '' | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A4) === | ||
+ | Der folgende LZW-Code: 0 1 2 4 6 5 7 7 3 codiert eine Pixelgrafik, | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A5) === | ||
+ | |||
+ | Erläutere in einem kurzen Text das Grundprinzip der Komprimierung beim LZW-Verfahren. | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (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: | ||
+ | holt 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> | ||