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:13] – sbel | faecher:informatik:oberstufe:codierung:lzw:start [03.10.2022 17:38] – [LZW-Kompression] 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%> | ||
- | Wörterbuchverfahren hinterlegen wiederkehrende Zeichenfolgen in einem Wörterbuch. Kommen | + | Wörterbuchverfahren hinterlegen |
- | diese Zeichenfolgen dann im zu komprimierenden Text vor, reicht ein Verweis auf diesen | + | diese Zeichenfolgen dann im zu komprimierenden Text erneut |
Eintrag. Das LZW-Verfahren arbeitet dabei mit einem dynamischen Wörterbuch, | Eintrag. Das LZW-Verfahren arbeitet dabei mit einem dynamischen Wörterbuch, | ||
während der Kompression selbst erzeugt wird und damit keinen zusätzlichen Speicherplatz | während der Kompression selbst erzeugt wird und damit keinen zusätzlichen Speicherplatz | ||
benötigt. | benötigt. | ||
</ | </ | ||
+ | |||
+ | Um Platz für das Wörterbuch neben den normalen (ASCII-)Zeichen zu schaffen, reichen | ||
+ | 8 Bit nicht aus. Für gewöhnlich werden 12 Bit für jedes Zeichen bzw. jeden | ||
+ | Wörterbucheintrag verwendet. Das Wörterbuch kann also maximal 2< | ||
+ | Zeichenkombinationen beinhalten, wovon die ersten 256 Einträge bei Texten fest mit den ASCII-Zeichen | ||
+ | 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 ===== | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ===== Material ===== | ||
+ | |||
+ | {{simplefilelist> | ||