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 17:38] – [LZW-Kompression] Frank Schiebel | faecher:informatik:oberstufe:codierung:lzw:start [03.10.2022 18:29] – [Decodierung] Frank Schiebel | ||
---|---|---|---|
Zeile 21: | Zeile 21: | ||
Die Codierung verläuft nach folgendem **Algorithmus**: | 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! | + | - 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. | + | - **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. | - 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 | - Wenn nötig wird das letzte Byte der Ausgabe mit 0 aufgefüllt | ||
Zeile 29: | Zeile 29: | ||
===== Beispiel ===== | ===== 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 = 10116 | ||
+ | BA | ||
+ | 101 | ||
+ | AB (A) | ||
+ | BAA = 10216 | ||
+ | AB | ||
+ | 102 | ||
+ | BAA (B) | ||
+ | ABB = 10316 | ||
+ | BAA | ||
===== Material ===== | ===== Material ===== |