Effiziente Algorithmen, Kapitel 1.1

1.1 Präfixfreie Codes: Huffman Codes

Wir wollen das Steuerungsprotokoll für eine kleine Mini-Drohne entwerfen. Sie soll acht Befehle verstehen:

forward, backward, turn left, turn right, up, down

Wir wollen nun die Menge $X$ der Befehle binär codieren, also eine Funktion $C : X \to {0, 1}^{*}$ definieren. Da es sechs Befehle gibt und $6 \leq 8$ ist, bietet sich folgende Codierung an:

forward	`000`
backward	`001`
turn left	`010`
turn right	`011`
up	`100`
down	`101`

Wir können also jedes $x \in X$ mit drei Bits codieren. Ist das optimal? Naja, wie wäre es denn mit folgendem Code:

forward	`0`
backward	`1`
turn left	`00`
turn right	`01`
up	`10`
down	`11`

Das Problem ist nun, dass wir Bitfolge wie 0010 nicht eindeutig decodieren können. Es könnte [turn left, up] sein, aber auch [turn left, backward, forward]. Welche Eigenschaft braucht $C$ , um eindeutig decodierbar zu sein? Ganz klar: das Ende der Wörter muss eindeutig erkennbar sein. In anderen Worten: $C$ muss präfixfrei sein. Was heißt das?

Definition 1.1.1 Sei $Σ$ ein Alphabet und $x, y \in Σ^{*}$ . Das Wort $x$ ist ein Präfix von $y$ , wenn es ein $u \in Σ^{*}$ gibt mit $y = x u$ . Auf Deutsch gesagt: wenn $y$ mit $x$ beginnt. Wir schreiben $x ⪯ y$ .

Eine Funktion $C : X \to Σ^{*}$ heißt präfixfrei wenn für alle verschiedenen $x, y \in X$ auch $C (x) ⪯̸ C (y)$ gilt.

Der Code im ersten Beispiel ist präfixfrei; der im zweiten nicht. Hier ist ein weiterer Code:

forward	`000`
backward	`001`
turn left	`01`
turn right	`10`
up	`110`
down	`111`

Um Codes und präfixfreie Codes über ${0, 1}^{*}$ zu verstehen, bietet es sich an, die Menge ${0, 1}^{*}$ aller endlichen Strings mit den Knoten des unendlichen Binärbaums zu identifizieren. Ich zeichne diesen Baum hier bis zur Tiefe 3:

Ganz einfach: die Wurzel ist $ϵ$ ; ein Knoten $u \in {0, 1}^{*}$ hat die zwei Kinder $u 0$ und $u 1$ . Eine Codierung $C : X \to {0, 1}^{*}$ ist nun eine Funktion von $X$ in die Menge der Knoten dieses Baumes. Sie ist präfixfrei wenn kein Codewort $C (x)$ Vorfahre eines anderen $C (y)$ ist. Hier nochmal die drei Codes von oben:

Code 1: Ein Blockcode; alle Codewörter haben die gleiche Länge (3).

Und zum Spaß noch ein vierter Code:

Übungsaufgabe 1.1.1 Sei $X$ eine Menge aus $n$ Elementen und $C : X \to {0, 1}^{*}$ ein präfixfreier Code. Zeigen Sie, dass es ein Codewort der Länge mindestens $\log_{2} | X |$ geben muss.

Welche Schranke bekommen Sie, wenn Sie nicht verlangen, dass $C$ präfixfrei ist, sondern nur injektiv (also dass keine zwei verschiedenen Elemente $x, y$ das gleiche Codewort zugewiesen bekommen)?

Erwartete Codelänge

Welcher der obigen Codes ist nun der Beste? Es ist ziemlich klar, dass Code 3 in jeder Hinsicht besser ist als Code 1: es gilt $| C_{3} (x) | \leq | C_{1} (x) |$ , jedes Element braucht in $C_{3}$ also höchstens so viele Bits wie in $C_{1}$ , und manche brauchen weniger (turn left und turn right). Wie vergleichen sich jedoch $C_{3}$ und $C_{4}$ ? Für das Wort forward ist $C_{4}$ besser; für backward sind beide gleich; für alle anderen ist $C_{3}$ besser. Wir können $C_{3}$ und $C_{4}$ also nicht direkt vergleichen. Wüssten wir allerdings, dass jeder zweite Befehl ein forward ist, so wäre $C_{4}$ womöglich der besser Code. Um solche verschiedenen Codes zu vergleichen, benötigen wir den Begriff der erwarteten Codelänge.

Definition 1.1.2 Sei $X$ eine endliche Menge, $P$ eine Wahrscheinlichkeitsverteilung über $X$ und $C : X \to {0, 1}^{*}$ eine Codierung. Die erwartete Codelänge von $C$ für Verteilung $P$ ist

\begin{array}{r} (1) & \underset{X \sim P}{E} [| C (X) |] = \sum_{x \in X} P (x) | C (x) | . \end{array}

Wenn wir $C : X \to {0, 1}^{*}$ als Baum $T$ darstellen, dann sprechen wir gerne von der erwarteten Tiefe des Baumes und schreiben ${avgdepth}_{P} (T)$ für ( $1$ ).

Beispiel. Nehmen wir eine Wahrscheinlichkeitsverteilung $P$ auf unserer Menge $X$ der sechs Drohnenbefehle und vergleichen die beiden Codes $C_{3}$ und $C_{4}$ .

$x$	$P (x)$	$C_{3} (x)$	$C_{4} (x)$
`forward`	$0.4$	`000`	`0`
`backward`	$0.1$	`001`	`101`
`turn left`	$0.2$	`01`	`110`
`turn right`	$0.2$	`10`	`111`
`up`	$0.05$	`110`	`1000`
`down`	$0.05$	`111`	`1001`

Die erwartete Codelänge von $C_{3}$ für Verteilung $P$ ist

\begin{array}{r} 0.4 \times 3 + 0.1 \times 3 + 0.2 \times 2 + 0.2 \times 2 + 0.05 \times 3 + 0.05 \times 3 = 2.6 \end{array}

Für $C_{4}$ erhalten wir

\begin{array}{r} 0.4 \times 1 + 0.1 \times 3 + 0.2 \times 3 + 0.2 \times 3 + 0.05 \times 4 + 0.05 \times 4 = 2.3 \end{array}

Für Verteilung $P$ ist $C_{4}$ also besser als $C_{3}$ .

Übungsaufgabe 1.1.2 Finden Sie eine Verteilung $Q$ auf $X$ , für die $C_{3}$ besser ist als $C_{4}$ .

Optimale Codes: Huffman-Coding

Wenn wir nun eine Verteilung $P$ gegeben haben, wie können wir den für $P$ optimalen Code berechnen? Dies geht erstaunlich einfach mit einem Greedy-Algorithmus, dem Huffman-Coding.

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

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 $T$ die Menge dieser Bäume.
while $| T | > 1$ :
1. Wähle zwei Bäume $T_{0}, T_{1} \in 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$ .
Nun hat $T$ die Größe $1$ , also $T = {T}$ .
Die Blätter von $T$ sind genau die Elemente $x \in X$ .
Setze $C (x) :=$ die Folge von Beschriftungen entlang des Pfades von der Wurzel zum Blatt $x$
return $C$

Hier ein Beispiellauf mit unserer Menge ${$ forward, backward, turn left, turn right, up, down $}$ und der Wahrscheinlichkeitsverteilung $P$ .

Theorem 1.1.3 Der Code $C$ , den der Huffman-Algorithmus findet, ist optimal, d.h. hat die kürzeste erwartete Codelänge aller präfixfreien Codes für $X$ und Verteilung $P$ .

Beweis. Wir verwenden Induktion über $n := | 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 $ϵ$ , die erwartete Codelänge ist somit $0$ , was offensichtlich optimal ist.

Wenn $n \geq 2$ ist, dann seien $x_{0}, x_{1} \in 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 $Y := X \cup {y} ∖ {x_{0}, x_{1}}$ . Wir definieren eine Wahrscheinlichkeitsverteilung $Q$ auf $Y$ via

\begin{aligned} Q (z) & := {\begin{cases} P (x_{0}) + P (x_{1}) & falls z = y, \\ P (z) & sonst. \end{cases} \end{aligned}

Die Mengen $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 $(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 $(X, P)$ .

Beweis: Wir betrachten die erwartete Tiefe von $S$ und $T$ . Die Tiefe eines zufälligen Elements $x \in 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{aligned} {avgdepth}_{P} (S) & = \sum_{x \in X} P (x) depth (x, S) \\ = \sum_{z \in X ∖ {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 Y} Q (z) depth (z, T) - Q (y) depth (y, T) \\ + P (x_{0}) (depth (y, T) + 1) + P (x_{1}) (depth (y, T) + 1) \\ = {avgdepth}_{Q} (T) + P (x_{1}) + P (x_{0}) \end{aligned}

Nach Induktion ist ${avgdepth}_{Q} (T)$ optimal für $(Y, Q)$ . Sei nun $S^{'}$ ein optimaler Baum für $(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 $Y$ , und nach ähnlicher Rechnung wie oben gilt

\begin{array}{r} {avgdepth}_{P} (S^{'}) = {avgdepth}_{Q} (T^{'}) + P (x_{1}) + P (x_{0}) . \end{array}

Nun gilt

\begin{aligned} (Rechnung oben) & {avgdepth}_{P} (S) & = {avgdepth}_{Q} (T) + P (x_{1}) + P (x_{0}) \\ (T ist optimal für (Y, Q)) & \leq {avgdepth}_{Q} (T^{'}) + P (x_{1}) + P (x_{0}) \\ = {avgdepth}_{P} (S^{'}) . \end{aligned}

Die $S$ ist also gleich gut oder besser als $S^{'}$ und ist somit auch optimal. $◻$

Somit sehen wir: der Hufmman-Algorithmus findet den optimalen präfixfreien Code für eine gegebene Wahrscheinlichkeitsverteilung. In den nächsten Kapiteln werden wir sehen, wie sich das zur Entropie verhält, einem fundamentalen Komplexitätsmaß von Wahrscheinlichkeitsverteilungen.