Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende ÜberarbeitungLetzte ÜberarbeitungBeide Seiten der Revision | ||
faecher:informatik:oberstufe:codierung:huffmancodierung:start [14.10.2021 18:11] – [Erzeugung des Huffman Baums und des Huffman Codes] 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: | ||
* '' | * '' | ||
- | 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:// | Mithilfe der Seite https:// | ||
Zeile 23: | Zeile 23: | ||
===== Erzeugung des Huffman Baums und des Huffman Codes ===== | ===== Erzeugung des Huffman Baums und des Huffman Codes ===== | ||
+ | {{.: | ||
+ | <WRAP center round important 90%> | ||
Der Code wird mithilfe eines Binärbaums nach dem folgenden Algorithmus aufgebaut: | Der Code wird mithilfe eines Binärbaums nach dem folgenden Algorithmus aufgebaut: | ||
- Bestimme die Häufigkeit H< | - Bestimme die Häufigkeit H< | ||
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. | - 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. | - 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. | ||
+ | </ | ||
+ | |||
---- | ---- | ||
Zeile 50: | Zeile 54: | ||
**(C)** Welche Information benötigt ein Mitschüler, | **(C)** Welche Information benötigt ein Mitschüler, | ||
+ | ---- | ||
+ | {{: | ||
+ | === (A3) === | ||
+ | |||
+ | Für den Text " | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A4) === | ||
+ | |||
+ | Decodiere den Code '' | ||
+ | |||
+ | {{ .: | ||
+ | |||
+ | ++++ Lösung | | ||
+ | '' | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (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. | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (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 " | ||
+ | * 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. | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | ++++ | ||
+ | ==== Material ==== | ||
+ | {{simplefilelist> |