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 [03.10.2022 17:55] – [Beispiel] Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
-====== LZW-Kopression ======
+====== LZW-Kompression ======
+Die LZW-Kompression 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 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 =====
+Die Zeichenkette ''BABAABBAA'' soll mit LZW codiert werden. Das Wörterbuch ist zu Beginn des Vorgangs im Bereich von 000<sub>16</sub> bis 0FF<sub>16</sub> mit den ASCII-Zeichen befüllt.
+===== Material =====
+{{simplefilelist>.:*}}