def Huffman ($\X$: eine endliche Menge, $P$: eine Verteilung auf $\X$):

1. Initialisierung. Erschaffe für jedes $x \in \X$ einen Baum $T_x$, der nur aus einem Wurzelknoten besteht, welcher selbst $x$ ist. Das Gewicht von $T_x$ sei $w(T_x) := P(x)$. Sei $\mathcal{T}$ die Menge dieser Bäume.
3. while $|\mathcal{T}| \gt 1$:
   1. Wähle zwei Bäume $T_0, T_1 \in \mathcal{T}$ mit den kleinsten Gewichten $w(T_0), w(T_1)$.
   2. Erschaffe einen Binärbaum $T$ mit einem neuen Wurzelknoten $u$ und linkem Teilbaum $T_0$ und rechtem Teilbaum $T_1$.
   3. Setze $w(T) := w(T_0) + w(T_1)$.
   4. Beschrifte die Kante von $u$ zu $T_0$ mit $0$ und die nach $T_1$ mit $1$.
4. Nun hat $\mathcal{T}$ die Größe $1$, also $\mathcal{T} =\{T\}$.
5. Die Blätter von $T$ sind genau die Elemente $x \in X$.
6. Setze $C(x) := $ die Folge von Beschriftungen entlang des Pfades von der Wurzel zum Blatt $x$
7. return $C$

Beweis. Wir verwenden Induktion über $n := |\mathcal{X}|$. Wenn $n=1$ ist, dann terminiert Huffman, ohne die while-Schleife auch nur ein einziges Mal durchlaufen zu haben. $T$ ist ein Baum, der nur aus der Wurzel besteht, das einzige Codewort ist $\epsilon$, die erwartete Codelänge ist somit $0$, was offensichtlich optimal ist.

Wenn $n \geq 2$ ist, dann seien $x_0, x_1 \in \mathcal{X}$ die beiden Elemente kleinster Wahrscheinlichkeit, die in Zeile 3.1 im ersten Schleifendurchlauf ausgewählt werden. Wir bauen nun eine neue Wahrscheinlichsverteilung, indem wir $x_0$ und $x_1$ verschmelzen. Formal: Sei $y$ ein neues Element und sei $\mathcal{Y} := \mathcal{X} \cup \{y\} \setminus \{x_0, x_1\} $. Wir definieren eine Wahrscheinlichkeitsverteilung $Q$ auf $\mathcal{Y}$ via

\begin{align*} Q(z) & := \begin{cases} P(x_0) + P(x_1) & \textnormal{ falls $z = y$,} \\ P(z) & \textnormal{ sonst.} \end{cases} \end{align*}

Die Mengen $\mathcal{Y}$ und die Verteilung $Q$ ist das, was Hufmann zu Beginn des zweiten Schleifendurchlaufs "sieht". Nach Induktion findet Hufmann optimalen Code/Binärbaum $T$ für $(\mathcal{Y}, Q)$. In diesem Baum $T$ gibt es ein Blatt $y$. Sei $S$ der Baum, der entsteht, wenn wir $y$ die zwei Kinder $x_0$ und $x_1$ hinzufügen. $S$ ist genau der Baum, mit den Huffman in Zeile 5 endet.

Behauptung: $S$ ist optimal für $(\mathcal{X}, P)$.

Beweis: Wir betrachten die erwartete Tiefe von $S$ und $T$. Die Tiefe eines zufälligen Elements $x \in \mathcal{X}$ ist gleich in $S$ und $T$, außer, wenn es sich um die "kollabierten" Elemente $x_0, x_1$ handelt. In diesem Falle ist sie $\depth(y,T)$ plus eins, weil wir ja noch die Kante von $y$ nach $x$ gehen müssen. Formal:

\begin{align*} \avgdepth_P(S) & = \sum_{x \in \mathcal{X}} P(x) \depth(x, S) \\ & = \sum_{z \in \mathcal{X} \setminus \{x_0, x_1\}} P(z) \depth(z,S) + P(x_0) \depth(x_0,S) + P(x_1) \depth(x_1,S) \\ & = \sum_{z \in \mathcal{Y}} Q(z) \depth(z,T) - Q(y) \depth(y,T) \\ & \quad + P(x_0) (\depth(y,T)+1) + P(x_1) (\depth(y,T)+1) \\ & = \avgdepth_Q(T) + P(x_1) + P(x_0) \end{align*}

Nach Induktion ist $\avgdepth_Q(T)$ optimal für $(\mathcal{Y}, Q)$. Sei nun $S'$ ein optimaler Baum für $(\mathcal{X}, P)$. Seien $v$ ein tiefstes Blatt in $S'$. Da $S'$ ein vollständiger Binärbaum ist, hat $v$ einen Geschwisterknoten $w$, der auch ein Blatt ist. Den Elternknoten von $v$ und $w$ nennen wir $y$. Was geschieht, wenn wir $v$ mit $x_0$ vertauschen? Da $v$ mindestens so tief ist wie $x_0$ und mindestens so häufig, kann die Vertauschung die erwartete Codelänge nur verringern; analog, wenn wir $w$ mit $x_1$ vertauschen. Nach Vertauschung erhalten wir einen neuen Baum, dessen erwartete Codelänge höchstens die von $S'$ ist; dieser ist also auch optimal. Wir nehmen nun also an, dass $S'$ optimal ist und $x_0, x_1$ Geschwisterblätter in $S'$ sind mit Elternknoten $y$. Sei $T'$ der Baum, der ensteht, wenn wir $x_0$ und $x_1$ entfernen. $T'$ ist ein Baum mit Blättermenge $\mathcal{Y}$, und nach ähnlicher Rechnung wie oben gilt

\begin{align*} \avgdepth_P(S') = \avgdepth_Q(T') + P(x_1) + P(x_0) \ . \end{align*}

Nun gilt

\begin{align*} \avgdepth_P(S) & = \avgdepth_Q(T) + P(x_1) + P(x_0) \tag{Rechnung oben} \\ & \leq \avgdepth_Q(T') + P(x_1) + P(x_0) \tag{$T$ ist optimal für $(\mathcal{Y}, Q)$} \\ & = \avgdepth_P(S') \ . \end{align*}

Die $S$ ist also gleich gut oder besser als $S'$ und ist somit auch optimal. \(\square\)