Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:codierung:huffmancodierung:start [14.10.2021 18:00] – [Kompression mit Huffman-Codierung] 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:informatik:grundstufe:codierung:einstieg_gruppenarbeit:morsecode:start|Morsecode]] verwendet als Code für das häufig vorkommende ''E'' lediglich ein ''•'' wohingegen ein ''Q'' in den den deutlich längeren Morsecode ''−−•−'' übersetzt wird.
-Beim Morsen muss man neben den beiden Symbolen "kurz" und "lang" auch noch mit Pausen arbeiten, um die unterschiedlichen Zeichen unterscheiden zu können. Das ist nötig, da der Morsecode nicht //präfixfrei// ist, das bedeutet, dass es Codes von Zeichen gibt, die gleichzeitig auch als Anfang eines anderen Codes interpretiert werden können.
-Beispiel: Das ''E'' mit seinem Code ''•'' ist gleichzeitig auch der Anfang des Zeichens ''A'' mit dem Code ''•−''. Damit ist der Morsecode ohne zusätzliche Pause (also einem dritten Zeichen) nicht mehr eindeutig entzifferbar:
-  * ''. - - . . . - . - .'' = ABC
-  * ''. - - . . . - . - .'' = EGFN
-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://people.ok.ubc.ca/ylucet/DS/Huffman.html lässt sich der Algorithmus schrittweise simulieren und visualisieren.
-----
-{{:aufgabe.png?nolink  |}}
-=== (A1) ===
-Lasse mit der Seite die Simulation für den Text „OTTOS MOPS KOTZT“ durchführen und beobachte den Aufbau des Baumes.((Tipp: verringere die Animationsgeschwindigkeit!))