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 [14.10.2021 18:04] – [Aufgaben] 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. | ||
+ | </ | ||
+ | |||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A2) === | ||
+ | |||
+ | **(A)** Erzeuge aus dem Baum, den du oben generiert hast, die Codierung für jedes einzelne Zeichen (inklusive Leerzeichen) | ||
+ | Anmerkung: Je nach Anordnung der Buchstaben und Knoten im Baum ist dieser Code nicht eindeutig. | ||
+ | |||
+ | Am besten machst du das in einer Tabelle: | ||
+ | |||
+ | |Zeichen | O | M | T | ... | | ||
+ | |Häufigkeit | 4 | 1 | 4 | ... | | ||
+ | |Code | 01 | ...| ... | ... | | ||
+ | |||
+ | |||
+ | |||
+ | **(B)** Codiere den Text mit dem gefundenen Code. Wieviel Bit/Byte hat die ASCII Codierung des Textes in Anspruch genommen, wieviele Bit benötigt der Satz, wenn er mit dem Huffman-Code codiert wird? | ||
+ | |||
+ | **(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> |