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 [28.09.2022 18:14] – sbel | faecher:informatik:oberstufe:codierung:lzw:start [03.10.2022 18:59] – [Decodierung] Frank Schiebel | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== LZW-Kopression | + | ====== LZW-Kompression |
- | Die LZW-Kopressione | + | Die LZW-Kompression |
<WRAP center round tip 90%> | <WRAP center round tip 90%> | ||
Zeile 16: | Zeile 16: | ||
Zeichenkombinationen beinhalten, wovon die ersten 256 Einträge bei Texten fest mit den ASCII-Zeichen | Zeichenkombinationen beinhalten, wovon die ersten 256 Einträge bei Texten fest mit den ASCII-Zeichen | ||
vorbelegt sind. | vorbelegt sind. | ||
+ | |||
+ | |||
+ | <WRAP center round important 90%> | ||
+ | Die Codierung verläuft nach folgendem **Algorithmus**: | ||
+ | |||
+ | - Lies eine **möglichst lange** Zeichenkette ein, die bereits im Wörterbuch steht. Zu Beginn ist das jeweils nur ein einzelnes Zeichen! | ||
+ | - **Schreibe** den Code des **gefundenen Eintrags** in die **Ausgabe**. | ||
+ | - Lege aus der eben gefundenen Zeichenkette und dem **nachfolgenden** Zeichen einen neuen Wörterbucheintrag mit der nächst möglichen Codierung an. | ||
+ | - Wenn nötig wird das letzte Byte der Ausgabe mit 0 aufgefüllt | ||
+ | </ | ||
+ | |||
+ | ===== Beispiel ===== | ||
+ | |||
+ | ==== Codierung ==== | ||
+ | |||
+ | |||
+ | {{ : | ||
+ | Die Zeichenkette '' | ||
+ | |||
+ | ^ Noch zu bearbeitende Zeichenkette | ||
+ | | **B**ABAABBAA | ||
+ | | **A**BAABBAA | ||
+ | | **BA**ABBAA | ||
+ | | **AB**BAA | ||
+ | | **BAA** | ||
+ | |||
+ | Die Zeichenfolge wird also folgendermaßen codiert: **042041100101102< | ||
+ | |||
+ | ==== 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) === | ||
+ | |||
+ | |||
+ | ===== Material ===== | ||
+ | |||
+ | {{simplefilelist> | ||