Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:codierung:lzw:start [28.09.2022 18:26] – [LZW-Kopression] sbel
+++ faecher:informatik:oberstufe:codierung:lzw:start [03.10.2022 18:49] – [Decodierung] Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
-====== LZW-Kopression ======
+====== LZW-Kompression ======
-Die LZW-Kopression 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 21: / Zeile 21: @@
 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 neuen Wörterbucheintrag mit der nächst möglichen Codierung an.
+  - 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>
@@ Zeile 29: / Zeile 29: @@
 ===== Beispiel =====
+==== Codierung ====
+{{ :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>  |                          |
+Die Zeichenfolge wird also folgendermaßen codiert: **042041100101102<sub>16</sub>**. Das sind 7,5 Bytes ((wenn man mit ganzen Bytes arbeiten möchte, wird das mit Nullen zu 8 Byte aufgefüllt)). Die Kompression ist also bei solch kurzen Zeichenketten noch nicht drastisch - wenn man sich jedoch vorstellt, dass das Wörterbuch stets längere Zeichenketten mit einem einzigen 12Bit Code zugreifbar macht, kann die Kompression unter Umständen bei längeren Texten deutlich stärker ins Gewicht fallen.
+==== Decodierung ====
+Bei der **Decodierung** werden 12-Bit-Blöcke eingelesen. Das Wörterbuch wird während des Vorgangs mit Einträgen befüllt die aus dem ersten Zeichen des aktuellen Eintrag und dem vorangehenden Eintrag bestehen. Wir nehmen den codierten String von oben: **042041100101102<sub>16</sub>**.
+^ Aktueller 12Bit-Block (Hexadezimal) ^ Gefundener Eintrag (erster Buchstabe) ^ Neuer Wörterbucheintrag ^ Ausgabe ^
+| 042 | B (B) |  | B  |
+| 041 | A (A) | BA = 100<sub>16</sub> | A |
+| 100 | BA (B) | AB = 101<sub>16</sub> | BA |
+| 101 | AB (A) | BAA = 102<sub>16</sub> | AB |
+| 102 | BAA (B) | ABB = 103<sub>16</sub> | BAA |
+Decodiert lautet der Text also ''BABAABBAA''.
+<WRAP center round box 90%>
+**Anmerkung**: Das Wörterbuch musste zur Decodierung hier **nicht** gesondert übertragen werden - es "ensteht" während des Vorgangs.
+</WRAP>
+----
+{{:aufgabe.png?nolink  |}}
+=== (A1) ===
+Codiere den Text ''ABABCABCDABCD'' und vergleiche die codierte und die uncodierte Länge miteinander.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A2) ===
+Decodiere folgenden Code: ''058059060101100103''. [[..:utf8:start#ascii_american_standard_code_for_information_interchange|Die ASCII-Tabelle findest du hier]].
+===== Material =====
+{{simplefilelist>.:*}}