Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:codierung:lzw:start [28.09.2022 18:05] – angelegt sbel
+++ faecher:informatik:oberstufe:codierung:lzw:start [28.09.2022 18:26] – [LZW-Kopression] sbel
@@ Zeile 1: / Zeile 1: @@
 ====== LZW-Kopression ======
+Die LZW-Kopression ist ein **Wörterbuchverfahren** nach Lempel-Ziv-Welch.
+<WRAP center round tip 90%>
+Wörterbuchverfahren hinterlegen **wiederkehrende Zeichenfolgen** in einem **Wörterbuch**. Kommen
+diese Zeichenfolgen dann im zu komprimierenden Text erneut vor, reicht ein Verweis auf diesen
+Eintrag. Das LZW-Verfahren arbeitet dabei mit einem dynamischen Wörterbuch, welches direkt
+während der Kompression selbst erzeugt wird und damit keinen zusätzlichen Speicherplatz
+benötigt.
+</WRAP>
+Um Platz für das Wörterbuch neben den normalen (ASCII-)Zeichen zu schaffen, reichen
+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<sup>12</sup> = 4096 Zeichen und
+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 12-Bit-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
+</WRAP>
+===== Beispiel =====