Huffman-Bäume

Ein Huffman-Baum wird erstellt, indem man die Zeichen entsprechend ihrer Häufigkeit (= Paare von Symbolen und Häufigkeit) aufsteigend in einer Liste sortiert und dann immer die beiden kleinsten von ihnen zusammenfügt und das Konstrukt dann wieder in die Liste zurücklegt. Am Ende bleibt dann nur noch ein Ding. Dieses ist dann der Huffman-Baum.

Er wird beschriftet, indem alle linken Teilbäume eine 0 und alle rechten eine 1 bekommen. Die Codierung erfolgt dann von oben nach unten (= bis das gewünschte Symbol erreicht ist).

In einer Funktion ist zu unterscheiden, ob es sich um ein Blatt handelt oder nicht.

Keine Kommentare:

Kommentar veröffentlichen