Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:codierung:huffmancodierung:start [28.09.2022 16:04] – [Erzeugung des Huffman Baums und des Huffman Codes] sbel
+++ faecher:informatik:oberstufe:codierung:huffmancodierung:start [09.01.2025 14:37] (aktuell) – Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
 ====== Kompression mit Huffman-Codierung ======
@@ Zeile 12: / Zeile 11: @@
   * ''. - - . . . - . - .'' = 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.
+Mithilfe der Seite https://cmps-people.ok.ubc.ca/ylucet/DS/Huffman.html lässt sich der Algorithmus schrittweise simulieren und visualisieren.
 ----
@@ Zeile 24: / Zeile 23: @@
+<callout type="important">
 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 30: @@
   - 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.
+</callout>
+==== Mobile-Modell für die Huffman-Codierung ====
+<callout type="important">
+{{  :faecher:informatik:oberstufe:codierung:huffmancodierung:mobile.svg?400|}}
+  - Bestimme die Häufigkeit H<sub>x</sub> aller vorkommenden Zeichen x.
+  - Hänge die Zeichen als "Mobilefiguren" beginnend mit den am wenigsten häufigen Zeichen ans Mobile und achte darauf, dass das Mobile möglichst ausgeglichen ist. Die Präfixfreiheit ergibt sich dadurch, dass sich an den "Anbindepunkten" der Querstäbe keine Zeichen befinden können, damit sind alle inneren Knoten des Baums leer.
+  - 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.
+</callout>
+===== Weitere Übungen =====
 ----
@@ Zeile 54: / Zeile 67: @@
 === (A3) ===
-Für den Text "ABRACADABRA": Erzeuge **von Hand** den Huffman-Baum, erstelle daraus einen Hoffman-Code und codiere damit den Text.
+Für den Text "ABRACADABRA": Erzeuge **von Hand** den Huffman-Baum, erstelle daraus einen Huffman-Code und codiere damit den Text.
 ----
@@ Zeile 62: / Zeile 75: @@
 Decodiere den Code ''0100 1110 1000 1010 0010 0001 11'' mithilfe des folgenden Baumes:
-{{ :faecher:informatik:oberstufe:codierung:huffmancodierung:huffb01.png?400 |}}
+{{ .:huffb01.png?400 |}}
 ++++ Lösung |
@@ Zeile 87: / Zeile 100: @@
   * 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.
+  * Gib einen korrekten Huffman-Baum für die angegebenen Buchstabenhäufigkeiten an.
 ++++ Lösung  |
@@ Zeile 96: / Zeile 109: @@
 {{ :faecher:informatik:oberstufe:codierung:huffmancodierung:huff2lsg.png |}}
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A7) Bildkompression ===
+Mit Hilfe einer "Zwischencodierung" kann man mit dem Huffman Code auch Bilder komprimieren. Betrachte das folgende Bild:
+{{ :faecher:informatik:oberstufe:codierung:huffmancodierung:pfeil.png?nolink&400 |}}
+Untersucht man das Bild jetzt zeilenweise und betrachtet die folgenden 4 möglichen "Pixelpaare", kann man das Bild mit der Huffman-Codierung komprimieren:
+^Pixelpaar ^ Weiß-Weiß ^ Weiß-Schwarz ^Schwarz-Weiß ^Schwarz-Schwarz ^
+^Wie oft? ^    |    |    |
+^Code ^  |   |   |
+  * Wie viele Bits benötigt man, wenn man die Bilddatei so codiert?  Vergleiche mit der Bitweisen Codierung.
+  * Warum ist es nicht sinnvoll, das folgende Bild auf diese Weise zu komprimieren? Begründe!
+{{ :faecher:informatik:oberstufe:codierung:huffmancodierung:streifen.png?nolink&200 |}}
+++++ Hinweis 1 - Zeichenzählung |
+{{ :faecher:informatik:oberstufe:codierung:huffmancodierung:pfeil_huffman.png?nolink |}}
+++++
 ==== Material ====
 {{simplefilelist>.:*}}