Effiziente Algorithmen, Kapitel 1.2

1.2 Kraft-McMillan-Ungleichung

Wir hatten eine binäre Codierung einer Menge $X$ definiert als Funktion $C : X \to {0, 1}^{*}$ . In diesem Teilkapitel interessieren wir uns nur für das Bild dieser Funktion, also die Menge der Codewörter. Wir betrachten daher einen Code als endliche Menge $C \subseteq {0, 1}^{*}$ . Er ist präfixfrei wenn $x ⪯̸ y$ für alle $x, y \in C, x \neq y$ gilt. Die Kraft-McMillan-Ungleichung, die wir in diesem Kapitel zeigen werden, wird leicht verständlich, wenn wir uns präfixfreie Codes als Binärbäume vorstellen.

Theorem 1.2.1 (Kraft-McMillan-Ungleichung). Sei $C \subseteq {0, 1}^{*}$ ein präfixfreier Code. Dann gilt

\begin{array}{r} (1) & \sum_{c \in C} 2^{- | c |} \leq 1 . \end{array}

Umgekehrt gilt: wenn $l_{1}, \dots, l_{n}$ natürliche Zahlen sind mit

\begin{array}{r} \sum_{i = 1}^{n} 2^{- l_{i}} \leq 1, \end{array}

dann gibt es einen präfixfreien Code ${c_{1}, \dots, c_{n}}$ mit $| c_{i} | = l_{i}$ .

Beweis. Für den ersten Teil setzen wir $l := max {| c | | c \in C}$ , also die Länge des längsten Codeworts in $C$ . Für jedes $c \in C$ definieren wir die Menge

\begin{array}{r} X_{c} := {x \in {0, 1}^{l} | c ⪯ x} \end{array}

In Worten: $X_{c}$ ist die Menge, die wir erhalten, wenn wir alle Möglichkeiten betrachten, $c$ zu einem String der Länge $l$ zu erweitern. Die Schranke folgt aus zwei einfachen Beobachtungen über die Mengen $X_{c}$ :

$| X_{c} | = 2^{l - | c |}$ . Das gilt, weil es noch $l - | c |$ Stellen "aufzufüllen" gibt, um die Länge $l$ zu erreichen.
Die Mengen $X_{c}$ sind paarweise disjunkt: wenn $x \in X_{c} \cap X_{c^{'}}$ sein sollte, dann sind $c ⪯ x$ und $c^{'} ⪯ x$ beides Präfixe von $x$ . Wenn nun ohne Beschränkung der Allgemeinheit $| c | \leq | c^{'} |$ gilt, so muss auch $c ⪯ c^{'}$ gelten: $c$ muss also ein Präfix von $c^{'}$ sein. Da $C$ präfixfrei ist, geht das nur, wenn $c = c^{'}$ ist. Die Mengen $X_{c}$ sind also paarweise disjunkt.

Da ${0, 1}^{l} \supseteq ⋃_{c \in C} X_{c}$ gilt, folgt aus den beiden Beobachtungen

\begin{aligned} 2^{l} & \geq | ⋃_{c \in C} X_{c} | \\ (weil paarweise disjunkt) & = \sum_{c \in C} | X_{c} | \\ (Wegen Punkt 1 oben.) & = \sum_{c \in C} 2^{l - | c |} . \end{aligned}

Wenn wir beide Seiten durch $2^{l}$ dividieren, erhalten wir $\sum_{c \in C} 2^{- | c |} \leq 1$ , wie behauptet. Somit haben wir den ersten Teil der Kraft-McMillan-Ungleichung gezeigt.

Alternativer Beweis. Falls Ihnen das zu schnell ging, können wir uns einen Binärbaum der Tiefe $l := max {| c | | c \in C}$ vorstellen und für jeden inneren Knoten die linke ausgehende Kante mit $0$ und die rechte mit $1$ beschriften. Somit entspricht jeder Knoten $v$ nun einem String $x \in {0, 1}^{*}$ von Länge höchstens $l$ , nämlich entsprechend den Labels auf den Kanten vom Wurzelknoten zu $v$ ; die Wurzel selbst trägt den leeren String $ϵ$ . Wir können nun einen präfixfreien Code $C$ als Menge von Knoten darstellen, die "unabhängig" ist, in der also kein Knoten Vorfahre eines anderen ist. Der Code

\begin{array}{r} C = {11, 001, 010, 100, 0001, 0111} \end{array}

entspricht der Menge der rot markierten Knoten:

Wir löschen nun alle Knoten, die einen roten Knoten als echten Vorfahren haben. Da keine zwei roten Knoten Vorfahren voneinander sind, wird dabei kein roter Knoten selbst gelöscht:

Dies ist ein vollständiger Binärbaum $T$ . Da jeder rote Knoten ein Blatt von $T$ ist, es aber womöglich weitere Blätter gibt, so gilt

\begin{array}{r} \sum_{c \in C} 2^{- | c |} \leq \sum_{b : Blatt von T} 2^{- depth (b, T)} . \end{array}

Es bleibt zu zeigen, dass letztere Summe gleich 1 ist:

Behauptung 1.2.2 Sei $T$ ein vollständiger Binärbaum. Dann gilt

\begin{array}{r} \sum_{b : Blatt von T} 2^{- depth (b, T)} = 1 . \end{array}

Beweis. Wir könnten uns einfach klar machen, dass ein Zufallslauf, der bei der Wurzel beginnt und immer zufällig eines der beiden Kinder nimmt, bis er ein Blatt erreicht, natürlich nach Definition immer ein Blatt erreicht, und zwar das Blatt $b$ genau mit Wahrscheinlichkeit $2^{depth (b, T)}$ . Somit definiert er eine Wahrscheinlichkeitsverteilung auf den Blättern und die Behauptung folgt unmittelbar.

Wenn Ihnen das zu schnell ging, so können wir gerne einen Beweis per Induktion über die Struktur von $T$ führen. Wenn $T$ aus einem einzelnen Knoten $b$ besteht, dann gilt $depth (b, T) = 0$ und somit ist die Summe gleich $1$ .

Für den Induktionsschritt bezeichne $r$ die Wurzel von $T$ und $T_{L}, T_{R}$ den linken bzw. rechten Teilbaum von $T$ . Es gilt

\begin{aligned} (2) & \sum_{b : Blatt von T} 2^{- depth (b, T)} & = \sum_{b : Blatt von T_{L}} 2^{- depth (b, T)} + \sum_{b : Blatt von T_{R}} 2^{- depth (b, T)} \end{aligned}

Für ein Blatt $b$ in $T_{L}$ gilt $depth (b, T) = depth (b, T_{L}) + 1$ ; analog für $T_{R}$ . Somit ist

\begin{aligned} (2) & = \sum_{b : Blatt von T_{L}} 2^{- depth (b, T_{L}) - 1} + \sum_{b : Blatt von T_{R}} 2^{- depth (b, T) - 1} \\ = \frac{1}{2} \cdot \sum_{b : Blatt von T_{L}} 2^{- depth (b, T_{L})} + \frac{1}{2} \cdot \sum_{b : Blatt von T_{R}} 2^{- depth (b, T_{R})} \end{aligned}

Nach Induktionshypothese ist jede der beiden Summen in der letzten Zeile gleich $1$ , und somit ist auch der Gesamtausdruck gleich $1$ . $◻$

Beweis des zweiten Teils. Wir nehmen an, dass die vorgegebenen Längen aufsteigend sortiert sind: $l_{1} \leq l_{2} \leq \dots \leq l_{n}$ . Wir nehmen nun einen vollständigen Binärbaum der Tiefe $l_{n}$ und färben alle Knoten weiß. Dann gehen wir die gewünschten Längen $l_{i}$ von klein nach groß durch: für jedes $l_{i}$ nehmen wir einen beliebigen weißen Knoten $v_{i}$ von Tiefe $i$ und setzen das Codewort $c_{i}$ auf das Label von $v_{i}$ (das sich durch die Kantenlabel ergibt, wenn wir von der Wurzel nach $v_{i}$ laufen). Dann färben wir $v_{i}$ blau und löschen wir alle echten Nachfahren von $v_{i}$ .

Das einzige, was wir prüfen müssen ist, dass wir in jedem Schritt einen weißen Knoten $v_{i}$ von Tiefe $l_{i}$ finden. Das ist der Fall: anfangs hat der Baum $2^{l_{n}}$ Blätter, alle weiß; wenn wir einen Knoten $v_{i}$ für $c_{i}$ auswählen, dann verschwinden $2^{l_{n} - l_{i}}$ weiße Blätter, falls $v_{i}$ selbst keine Blatt ist; falls $v_{i}$ ein Blatt ist, also $l_{i} = l_{n}$ , dann wird $v_{i}$ blau gefärbt; in jedem Fall nimmt die Anzahl der weißen Blätter um $2^{l_{n} - l_{i}}$ ab. Nach $k$ Schritten ist die Anzahl der weißen Blätter also

\begin{aligned} 2^{l_{n}} - \sum_{i = 1}^{k} 2^{l_{n} - l_{k}} = 2^{l_{n}} (1 - \sum_{i = 1}^{k} 2^{- l_{i}}) \\ (3) & \geq & 2^{l_{n}} (\sum_{i = k + 1}^{n} 2^{- l_{i}}), \end{aligned}

da nach Annahme $\sum_{i = 1}^{n} 2^{- l_{i}} \leq 1$ gilt; weiße Blätter übrig. Wenn $k = n$ ist sind wir fertig; wenn $k < n$ ist, dann ist ( $???$ ) größer als $0$ , also gibt es noch ein weißes Blatt; somit hat dieses Blatt auch einen weißen Vorfahren auf Tiefe $k + 1$ und wir können einen passenden Knoten $v_{k + 1}$ finden. $◻$