Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:codierung:huffmancodierung:start [29.11.2023 18:21] – Frank Schiebel
+++ faecher:informatik:oberstufe:codierung:huffmancodierung:start [09.01.2025 14:37] (aktuell) – Frank Schiebel
@@ Zeile 13: / Zeile 13: @@
 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 31: / Zeile 31: @@
   - 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 56: / 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 89: / 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 100: / Zeile 111: @@
 ++++
+----
+{{: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>.:*}}