Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:codierung:lzw:start [03.10.2022 17:01] – [Decodierung] Frank Schiebel
+++ faecher:informatik:oberstufe:codierung:lzw:start [14.01.2025 09:36] (aktuell) – [Codierung] Frank Schiebel
@@ Zeile 33: / Zeile 33: @@
 {{ :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>
+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  ^
+Die Codes ab 100<sub>16</sub> stehen dann für Wörterbucheinträge zur Verfügung - der erste Wörterbucheintrag bekommt den Code 100<sub>16</sub>, der zweite 101<sub>16</sub> u.s.w. So kann jedes Zeichen/Zeichenkombination des Wörterbuchs mit 12Bit codiert werden.
-| **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>    |
+{{ :faecher:informatik:oberstufe:codierung:lzw:lzw-codierung-beispiel.png?nolink |}}
-| **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.
@@ Zeile 46: / Zeile 43: @@
 ==== 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>**.
+Bei der **Decodierung** werden 12-Bit-Blöcke eingelesen.
+Das Wörterbuch wird während des Vorgangs mit Einträgen befüllt die aus allen Zeichen des Vorangehenden Eintrags und **dem ersten Zeichen**((Achtung Falle!)) des aktuellen Eintrags bestehen.
-^ Aktueller 12Bit-Block (Hexadezimal) ^ Gefundener Eintrag (erster Buchstabe) ^ Neuer Wörterbucheintrag ^ Ausgabe ^
+Wir nehmen den codierten String von oben: **042 041 100 101 102<sub>16</sub>**.
-| 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 |
+{{ :faecher:informatik:oberstufe:codierung:lzw:lzw-decodierung-beispiel.png?nolink |}}
 Decodiert lautet der Text also ''BABAABBAA''.
@@ Zeile 85: / Zeile 80: @@
 === (A2) ===
-Decodiere folgenden Code: ''058059060101100103''. [[..:utf8:start#ascii_american_standard_code_for_information_interchange|Die ASCII-Tabelle findest du hier]].
+Decodiere folgenden Code: ''058 059 05A 101 100 103''. [[faecher:informatik:oberstufe:codierung:zeichencodierung:ascii:start|Die ASCII-Tabelle findest du hier]]
 ++++ Lösung: |
@@ Zeile 107: / Zeile 102: @@
 {{ :faecher:informatik:oberstufe:codierung:lzw:pixel.png?200 |}}
+----
+{{:aufgabe.png?nolink  |}}
+=== (A5) ===
+Erläutere in einem kurzen Text das Grundprinzip der Komprimierung beim LZW-Verfahren.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A6) ===
+Begründe, dass das LZW-Verfahren nicht jede Eingabe komprimieren kann.
+++++ Lösung |
+Das LZW-Verfahren ist ein verlustfreies Verfahren, d.h. jede Eingabe ist eindeutig wiederherstellbar. Zu jeder
+komprimierten Bitfolge gehört damit genau eine Eingabe. Es kann kein verlustfreies Verfahren geben, das
+jede Eingabe komprimiert.
+Begründung: Wenn es ein Verfahren gäbe, das jede Eingabe verkürzen kann, könnte man dieses wiederholt anwenden, bis die Ausgabe nur noch 1 Bit lang wäre. Diese könnte genau zwei Werte annehmen, 0 oder
+. Daraus könnte man aber höchstens zwei Eingaben rekonstruieren.
+++++
 ===== Material =====
 {{simplefilelist>.:*}}