Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:codierung:lzw:start [28.09.2022 18:13] – sbel
+++ faecher:informatik:oberstufe:codierung:lzw:start [28.09.2022 18:26] – [LZW-Kopression] sbel
@@ Zeile 1: / Zeile 1: @@
 ====== LZW-Kopression ======
-Die LZW-Kopressione ist ein **Wörterbuchverfahren** nach Lempel-Ziv-Welch.
+Die LZW-Kopression ist ein **Wörterbuchverfahren** nach Lempel-Ziv-Welch.
 <WRAP center round tip 90%>
@@ Zeile 10: / Zeile 10: @@
 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 =====