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:33] – [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 18: | Zeile 18: | ||
- | <WRAP center round important | + | <WRAP center round important |
- | Die Codierung verläuft nach folgendem Algorithmus: | + | Die Codierung verläuft nach folgendem |
- | 1. 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! |
- | 2. Schreibe den 12-Bit-Code des gefundenen Eintrags in die Ausgabe. | + | - **Schreibe** den Code des **gefundenen Eintrags** in die **Ausgabe**. |
- | 3. 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 |
- | 4. Ggf. 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< | ||
+ | |||
+ | ===== Material ===== | ||
+ | |||
+ | {{simplefilelist> | ||