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:04] – [Aufgaben] 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. | ||
- | |||
- | ===== Aufgaben ===== | ||
- | |||
- | 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. |