Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:codierung:lzw:start [28.09.2022 18:14] – sbel
+++ faecher:informatik:oberstufe:codierung:lzw:start [03.10.2022 18:07] – [Tabelle] Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
-====== LZW-Kopression ======
+====== LZW-Kompression ======
-Die LZW-Kopressione ist ein **Wörterbuchverfahren** nach Lempel-Ziv-Welch.
+Die LZW-Kompression ist ein **Wörterbuchverfahren** nach Lempel-Ziv-Welch.
 <WRAP center round tip 90%>
@@ Zeile 18: / Zeile 18: @@
-<WRAP center round important 60%>
+<WRAP center round important 90%>
-Die Codierung verläuft nach folgendem Algorithmus:
+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!
+  - 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.
+  - **Schreibe** den Code des **gefundenen Eintrags** in die **Ausgabe**.
-. Lege aus der eben gefundenen Zeichenkette und dem nachfolgenden Zeichen einen
+  - Lege aus der eben gefundenen Zeichenkette und dem **nachfolgenden** Zeichen einen neuen Wörterbucheintrag mit der nächst möglichen Codierung an.
-neuen Wörterbucheintrag mit der nächst möglichen Codierung an.
+  - Wenn nötig wird das letzte Byte der Ausgabe mit 0 aufgefüllt
-. Ggf. Wird das letzte Byte der Ausgabe mit 0 aufgefüllt
 </WRAP>
+===== Beispiel =====
+{{ :faecher:informatik:oberstufe:codierung:lzw:ab.png|}}
+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((Die ersten 256 Zeichen des 12 Bit Raums, der für die Codierung zur Verfügung steht)). Zum besseren Verständnis des weiteren Ablaufs sollte man im Hinterkopf haben, dass der ASCII Code des großen A 65<sub>10</sub>=41<sub>16</sub> ist, der des großen B 66<sub>10</sub>=42<sub>16</sub>
+^ Noch zu bearbeitende Zeichenkette  ^ Gefundener Eintrag     ^ Ausgabe (12Bit)   ^ Neuer Wörterbucheintrag  ^
+| **B**ABAABBAA                      | B ← 042<sub>16</sub>   | 042<sub>16</sub>  | BA → 100<sub>16</sub>    |
+| **A**BAABBAA                       | A ← 041<sub>16</sub>   | 041<sub>16</sub>  | AB → 101<sub>16</sub>    |
+| **BA**ABBAA                        | BA ← 100<sub>16</sub>  | 100<sub>16</sub>  | BAA	→ 102<sub>16</sub>   |
+| **AB**BAA                          | AB ← 101<sub>16</sub>  | 101<sub>16</sub>  | ABB	→ 103<sub>16</sub>   |
+| **BAA**                            | BAA	←102<sub>16</sub>  | 102<sub>16</sub>  |                          |
+===== Material =====
+{{simplefilelist>.:*}}