Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:codierung:lzw:start [28.09.2022 18:26] – [LZW-Kopression] sbel
+++ faecher:informatik:oberstufe:codierung:lzw:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ 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 =====