Kann mir jemand die Huffman-Codierung erklären?
Kann mir wer den Algorithmus im wesentlichen erklären? Irgendwie sagen die auf YouTube etc. alle was anderes :(
1 Antwort
Du nimmst immer die beiden Knoten, die gerade die geringsten Wahrscheinlichkeiten haben, und hängst sie als Kinder an einen neuen Knoten. Der neue Knoten bekommt dann die Summe der Wahrscheinlichkeiten der beiden Kinder.
Diesen Schritt wiederholst Du solange, bis alle Knoten zu einem Baum zusammengesetzt sind. Fertig.
Beispiel:
Symbole (Wahrscheinlichkeiten): a (1/8) b (1/4) c (1/16) d (1/16) e (1/2)
c und d haben die geringsten Wahrscheinlichkeiten, sie werden unter dem Knoten K1 zusammengefasst:
K1
/ \
c d
K1 bekommt jetzt die Wahrscheinlichkeit 1/16 + 1/16 = 1/8.
Jetzt haben a und K1 die kleinsten Wahrscheinlichkeiten, also werden sie als nächstes zusammengefasst:
K2
/ \
K1 a
/ \
c d
K2 bekommt jetzt die Wahrscheinlichkeit 1/8 + 1/8 = 1/4.
Jetzt haben b und K2 die kleinsten Wahrscheinlichkeiten, also werden sie als nächstes zusammengefasst:
K3
/ \
K2 b
/ \
K1 a
/ \
c d
K2 bekommt jetzt die Wahrscheinlichkeit 1/4 + 1/4 = 1/2.
Jetzt sind nur noch K3 und e übrig, also werden sie zusammengefasst:
K4
/ \
K3 e
/ \
K2 b
/ \
K1 a
/ \
c d
Fertig. Das ist der Huffman-Baum.
Wenn Du jetzt alle linken Kanten mit 0, und alle rechten Kanten mit 1 beschriftest, erhältst Du die Huffman-Codes wenn Du von der Wurzel ausgehend den Baum bis zu jedem Symbol herunterläufst.
e: 1
b: 01
a: 001
d: 0001
e: 0000
Um eine Nachricht zu kodieren, ersetzt Du einfach jedes Symbol mit dem entsprechenden Code
abedaa wird zu 0010100000001001001
Zum Dekodieren kannst Du entweder in die Tabelle schauen, oder Du traversierst den Baum; Du beginnst wieder bei der Wurzel. Wenn Du eine 0 liest, gehst Du zum linken Kind, wenn Du eine 1 liest, gehst Du zum rechten Kind, bis Du bei einem Symbol angekommen bist.
Alles klar vielen Dank für die Antwort! :)