Huffman Codierung, Beweisidee

[zsanzhar]

Sei T der Baum eines optimalen Präfix-Codes (d.h. L(T,f) ist minimal für die gegebenen Häufigkeiten. Seien u, v ∈ A zwei Buchstaben mit den geringsten Häufigkeiten. Dann gibt es einen optimalen Baum, so dass u und v benachbart sind (d. h. beide haben einen gemeinsamen Elternknoten).

Hat jemand eine Idee, wie ich das zeigen kann? Ich glaube, dass dieses Eigenschaft stimmt, aber ich weiß nicht, wie ich das zeigen kann.

 

[C.J.]

Wenn ich an den Algorithmus für die Berechnung der Kodierung denke, dann werden im ersten Schritt die zwei Buchstaben mit den geringsten Häufigkeiten zu einem Baum zusammengefasst. Da der Algorithmus nicht vorschreibt, welche Buchstaben man auswählt, wenn die Wahl mehrdeutig ist, muss er auch dann eine optimale Lösung berechnen, wenn ich mir die Zeichen beliebig aussuche, also z.B. zwei bestimmte Zeichen u und v.

Informationen von hier: https://de.wikipedia.org/wiki/Huffman-Kodierung

 

[zsanzhar]

Ja,das verstehe ich, aber wie ich das zeigen soll, ist mir unklar
T ist ja hier ein Baum eines opt Präfix Code(L(T, f) = Summe von f(Anzahl von Häufigkeiten) * Anzahl Bits) und wenn ein Baum opt ist, haben ja die dann denn gleichen Elternknoten, keine Ahnung wie ich dieses Eigenschaft zeigen soll (((