Huffman-Code

Von Hang, Marius, Jan, Molitor und Jules

Der Huffman Code

• Verfahren, um eine Nachricht binär zu kodieren• Kodierung ist abhängig von der Häufigkeit der

Buchstaben im Text– Die so kodierte Nachricht ist kürzer als z.B. per ASCII

kodiert• (Je häufiger ein Zeichen verwendet wird, desto kürzer sein

Code. Bei selten genutzten Zeichen kann der Code aber länger als 8 Bit sein)

– Schwierigkeit: Fehlende Trennzeichen• Kein Code eines Buchstabens darf so enden, wie ein anderer

beginnt

Funktionsweise des Huffman-Verfahrens

Häufigkeit / Buchstabe wird berechnet

Liste aller Buchstaben wird nach Häufigkeit dieser sortiert

Die beiden am seltensten vorkommenden Buchstaben werden an die Zweige eines Binär-Baums gehängt

Der Baum wird wieder in die Liste der Buchstaben einsortiert (Summe der Häufigkeit aller Buchstaben) – Prozess beginnt von vorne

Kodierung eines Textes

• Text: „Dies ist ein Test-Text, um die Kodierung per Huffman-Verfahren zu veranschaulichen.“

111010001100100 00001001001 1100001111…

Aufgabe

• Erstelle zu diesem Satz einen Kodierungsbaum mit Hilfe der gegebenen Häufigkeitsanalyse:– „Weit hinten, hinter den Wortbergen, fern der

Länder Vokalien und Konsonantien leben die Blindtexte.„

– e: 16 | n: 15 | t, i: 7 | r, d : 6 | o, l: 4 | b: 3 | w, k, h, a: 2 | ä, x, v, u, s, g, f : 1• Anmerkung: Sonderzeichen werden nicht kodiert (ä,. )