Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
faecher:informatik:oberstufe:codierung:huffmancodierung:start [14.10.2021 18:17] – [Erzeugung des Huffman Baums und des Huffman Codes] sbel | faecher:informatik:oberstufe:codierung:huffmancodierung:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== Kompression mit Huffman-Codierung ====== | ||
- | |||
- | Bei der herkömmlichen Text-Codierung mithilfe der ASCII-Tabelle besitzt jedes Zeichen eine Codelänge von genau 8 Bit. Die Idee hinter der Huffman-Codierung ist die, dass häufig vorkommende Zeichen mit einer kürzeren Codelänge auskommen als weniger häufig vorkommende Zeichen. | ||
- | |||
- | Ein Beispiel kennst du bereits: [[ faecher: | ||
- | |||
- | Beim Morsen muss man neben den beiden Symbolen " | ||
- | |||
- | Beispiel: Das '' | ||
- | * '' | ||
- | * '' | ||
- | |||
- | Der **Huffman-Code** bildet solch einen präfixfreien Code, der gleichzeitig den häufig vorkommenden Zeichen eine kürzere Codelänge generiert. | ||
- | |||
- | Mithilfe der Seite https:// | ||
- | |||
- | ---- | ||
- | {{: | ||
- | === (A1) === | ||
- | Lasse mit der Seite die Simulation für den Text „OTTOS MOPS KOTZT“ durchführen und beobachte den Aufbau des Baumes.((Tipp: | ||
- | |||
- | ===== Erzeugung des Huffman Baums und des Huffman Codes ===== | ||
- | |||
- | |||
- | Der Code wird mithilfe eines Binärbaums nach dem folgenden Algorithmus aufgebaut: | ||
- | - Bestimme die Häufigkeit H< | ||
- | - Erzeuge Knoten für jedes Zeichen x und markiere dieses mit der zum Zeichen gefundenen Häufigkeit H< | ||
- | - Nimm die beiden Knoten mit der geringsten Häufigkeit, | ||
- | - 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. | ||
- | |||
- | ---- | ||
- | {{: | ||
- | === (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. | ||
- | ++++ |