faecher:informatik:oberstufe:codierung:huffmancodierung:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:codierung:huffmancodierung:start [29.11.2023 18:49] – [Weitere Übungen] Frank Schiebelfaecher: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**. 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 29: Zeile 29:
   - Nimm die beiden Knoten mit der geringsten Häufigkeit, die noch nicht verarbeitet wurden. Erzeuge einen neuen Knoten und hänge die beiden gefundenen an diesen an. Markiere den neuen Knoten mit der Summe der beiden Häufigkeiten der angehängten Knoten.   - Nimm die beiden Knoten mit der geringsten Häufigkeit, die noch nicht verarbeitet wurden. Erzeuge einen neuen Knoten und hänge die beiden gefundenen an diesen an. Markiere den neuen Knoten mit der Summe der beiden Häufigkeiten der angehängten Knoten.
   - Wiederhole 3. so lange, bis nur noch ein einzelner Knoten übrig bleibt, an dem sämtliche andere Knoten angehängt wurden.   - 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 1, alle rechten Kanten mit 0. Der Code für ein Zeichen x ergibt sich dann aus dem Weg vom Wurzelknoten bis zu diesem Zeichen.+  - 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> </callout>
  
Zeile 37: Zeile 37:
   - Bestimme die Häufigkeit H<sub>x</sub> aller vorkommenden Zeichen x.   - 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.   - 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 1, alle rechten Kanten mit 0. Der Code für ein Zeichen x ergibt sich dann aus dem Weg vom Wurzelknoten bis zu diesem Zeichen.+  - 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> </callout>
Zeile 67: Zeile 67:
 === (A3) === === (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 100: Zeile 100:
   * Begründe, warum der Baum kein gültiger Huffman-Baum ist.   * 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.   * Erläutere den Nachteil, der beim Codieren des Wortes "BELEBEN" mit diesem Baum auftritt.
-  * Gíb 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  | ++++ Lösung  |
Zeile 113: Zeile 113:
 ---- ----
 {{:aufgabe.png?nolink  |}} {{:aufgabe.png?nolink  |}}
-=== (A6) Bildkompression ===+=== (A7) Bildkompression ===
  
-Mit Hilfe einer "Zwischencodierung" kann man mit dem Huffman Code auch Bilder komprimieren.Betrachte das folgende Bild: +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 |}} 
 +++++
  
-{{ :faecher:informatik:oberstufe:codierung:huffmancodierung:pfeil.png?nolink |}} 
 ==== Material ==== ==== Material ====
  
 {{simplefilelist>.:*}} {{simplefilelist>.:*}}
  • faecher/informatik/oberstufe/codierung/huffmancodierung/start.1701283788.txt.gz
  • Zuletzt geändert: 29.11.2023 18:49
  • von Frank Schiebel