Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:codierung:huffmancodierung:start [14.10.2021 18:10] – sbel
+++ faecher:informatik:oberstufe:codierung:huffmancodierung:start [30.09.2022 13:08] – [Erzeugung des Huffman Baums und des Huffman Codes] sbel
@@ Zeile 12: / Zeile 12: @@
   * ''. - - . . . - . - .'' = EGFN
-Der **Huffman-Code** bildet solch einen präfixfreien Code, der gleichzeitig den häufig vorkommenden Zeichen eine kürzere Codelänge generiert.
+Der **Huffman-Code** bildet solch einen präfixfreien Code, der gleichzeitig den häufig vorkommenden Zeichen eine kürzere Codelänge generiert. Der Huffman-Code ist eine sogenannte **Entropiekodierung**.
 Mithilfe der Seite https://people.ok.ubc.ca/ylucet/DS/Huffman.html lässt sich der Algorithmus schrittweise simulieren und visualisieren.
@@ Zeile 23: / Zeile 23: @@
 ===== Erzeugung des Huffman Baums und des Huffman Codes =====
+{{.:huff2.png?400 |}}
+<WRAP center round important 90%>
 Der Code wird mithilfe eines Binärbaums nach dem folgenden Algorithmus aufgebaut:
   - Bestimme die Häufigkeit H<sub>x</sub> aller vorkommenden Zeichen x.
@@ Zeile 30: / Zeile 32: @@
   - Wiederhole 3. so lange, bis nur noch ein einzelner Knoten übrig bleibt, an dem sämtliche andere Knoten angehängt wurden.
   - Markiere alle linken Kanten mit 0, alle rechten Kanten mit 1. Der Code für ein Zeichen x ergibt sich dann aus dem Weg vom Wurzelknoten bis zu diesem Zeichen.
+</WRAP>
 ----
@@ Zeile 35: / Zeile 39: @@
 === (A2) ===
-**(a)** Erzeuge aus dem Baum, den du oben generiert hast, die Codierung für jedes einzelne Zeichen (inklusive Leerzeichen)
+**(A)** Erzeuge aus dem Baum, den du oben generiert hast, die Codierung für jedes einzelne Zeichen (inklusive Leerzeichen)
 Anmerkung: Je nach Anordnung der Buchstaben und Knoten im Baum ist dieser Code nicht eindeutig.
@@ Zeile 44: / Zeile 48: @@
 |Code | 01 | ...| ... | ... |
-Wieviel Bit/Byte hat die ASCII Codierung des Textes in Anspruch genommen, wieviele Bit benötigt der Satz, wenn er mit dem Huffman-Code codiert wird?
-**(b)** Codiere den Text mit dem gefundenen Code.#
-**(c)** Welche Information benötigt ein Mitschüler, um deinen Code decodieren und den ursprünglichen Text wiederherstellen zu können?
+**(B)** Codiere den Text mit dem gefundenen Code. Wieviel Bit/Byte hat die ASCII Codierung des Textes in Anspruch genommen, wieviele Bit benötigt der Satz, wenn er mit dem Huffman-Code codiert wird?
+**(C)** Welche Information benötigt ein Mitschüler, um deinen Code decodieren und den ursprünglichen Text wiederherstellen zu können?
+----
+{{:aufgabe.png?nolink  |}}
+=== (A3) ===
+Für den Text "ABRACADABRA": Erzeuge **von Hand** den Huffman-Baum, erstelle daraus einen Hoffman-Code und codiere damit den Text.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A4) ===
+Decodiere den Code ''0100 1110 1000 1010 0010 0001 11'' mithilfe des folgenden Baumes:
+{{ .:huffb01.png?400 |}}
+++++ Lösung |
+''SIMSALABIM''
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A5) ===
+In welchen Fällen ist die Huffman-Codierung am effizientesten und warum?
+++++ Lösung |
+Wenn ein großer Anteil des Textes aus wenigen unterschiedlichen Buchstaben besteht, denn die häufigsten Buchstaben werden zuletzt in den Baum eingebaut und haben darum den kürzesten Code.
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A6) ===
+Gegeben ist der folgende Baum:
+{{ .:huff2.png |}}
+  * Begründe, warum der Baum kein gültiger Huffman-Baum ist.
+  * Erläutere den Nachteil, der beim Codieren des Wortes "BELEBEN" mit diesem Baum auftritt.
+  * Geben Sie einen korrekten Huffman-Baum für die angegebenen Buchstabenhäufigkeiten an.
+++++ Lösung  |
+  * Der linke Teilbaum hat das Gewicht 2 und hätte mit B zusammengefasst werden müssen.
+  * Jedes Codewort hat die Länge 2, damit wird das Wort mit insgesamt 14 Bit gespeichert. Dieser Wert ist
+nicht optimal.
+{{ :faecher:informatik:oberstufe:codierung:huffmancodierung:huff2lsg.png |}}
+++++
+==== Material ====
+{{simplefilelist>.:*}}