Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste ÜberarbeitungBeide Seiten der Revision | ||
faecher:informatik:oberstufe:codierung:huffmancodierung:start [28.09.2022 18:01] – [Erzeugung des Huffman Baums und des Huffman Codes] sbel | faecher:informatik:oberstufe:codierung:huffmancodierung:start [29.09.2022 08:32] – 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 24: | Zeile 24: | ||
+ | <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 31: | ||
- 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 83: | Zeile 86: | ||
Gegeben ist der folgende Baum: | 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. | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | ++++ | ||