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:08] – [Erzeugung des Huffman Baums und des Huffman Codes] sbel | faecher:informatik:oberstufe:codierung:huffmancodierung:start [28.09.2022 18:07] – [Kompression mit Huffman-Codierung] 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 35: | Zeile 35: | ||
=== (A2) === | === (A2) === | ||
- | **(a)** Erzeuge aus dem Baum, den du oben generiert hast, die Codierung für jedes einzelne Zeichen (inklusive Leerzeichen) | + | **(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. | Anmerkung: Je nach Anordnung der Buchstaben und Knoten im Baum ist dieser Code nicht eindeutig. | ||
Zeile 44: | Zeile 44: | ||
|Code | 01 | ...| ... | ... | | |Code | 01 | ...| ... | ... | | ||
- | **(b)** Codiere den Text mit dem gefundenen Code. | ||
+ | **(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> |