Effiziente Algorithmen, Kapitel 1.5

1.5 Shannons Source-Coding-Theorem

Zur Wiederholdung: wir betrachten eine endliche Menge $X$ und eine Codierung von $X$ über dem Alphabet ${0, 1}$ . Diese Codierung ist eine Funktion $C : X \to {0, 1}^{*}$ , und sie heißt präfixfrei wenn für alle $x, y \in X$ mit $x \neq y$ gilt:

\begin{array}{r} C (x) ⪯̸ C (y) . \end{array}

Das Codewort $C (x)$ darf also kein Präfix von $C (y)$ sein, und insbesondere muss $C (x) \neq C (y)$ gelten. Wenn $X$ mit einer Wahrscheinlichkeitsverteilung $P : X \to [0, 1]$ ausgestattet ist, dann können wir über die erwartete Codelänge sprechen:

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

Theorem 1.5.1 (Source-Coding-Theorem). Sei $X$ eine endliche Menge und $P$ eine Wahrscheinlichkeitsverteilung über $X$ .

Untere Schranke: wenn $C : X \to {0, 1}^{*}$ ein präfixfreier Code ist, dann gilt $\begin{array}{r} \underset{x \sim P}{E} [| C (x) |] \geq H (P) . \end{array}$
Obere Schranke: es gibt einen präfixfreien Code $C : X \to {0, 1}^{*}$ mit $\begin{array}{r} (1) & | C (x) | \leq ⌈ \log_{2} (\frac{1}{P (x)}) ⌉ \end{array}$ für jedes $x \in X$ , und somit auch $\begin{array}{r} \underset{x \sim P}{E} [| C (x) |] \leq H (P) + 1 . \end{array}$

Beweis (untere Schranke). Sei $C : X \to {0, 1}^{*}$ ein Code. Wir definieren

\begin{aligned} Q : X & \to R \\ x & \mapsto 2^{- | C (x) |} \end{aligned}

Nach Teil $1$ von Reference "theorem-kraft-ineq" not found. Go to put-all-in-one-page.html and read the instructions. (der Kraft-McMillan-Ungleichung) gilt $\sum_{x \in X} Q (x) \leq 1$ . Wir rechnen nun

\begin{aligned} \underset{x \sim P}{E} [| C (x) |] & = \underset{x \sim P}{E} [- \log Q (x)] \\ = \underset{x \sim P}{E} [- \log P (x) - \log Q (x) + \log P (x)] \\ = \underset{x \sim P}{E} [- \log P (x)] + \underset{x \sim P}{E} [\log (\frac{P (x)}{Q (x)})] \\ = H (P) + \underset{x \sim P}{E} [\log (\frac{P (x)}{Q (x)})] . \end{aligned}

Es bleibt zu zeigen, dass der zweite Term dieser Summe nicht negativ ist.

\begin{aligned} \underset{x \sim P}{E} [\log (\frac{P (x)}{Q (x)})] & \geq 0 ⟺ \\ \underset{x \sim P}{E} [\log (\frac{Q (x)}{P (x)})] & \leq 0 . \end{aligned}

Wir rechnen nun weiter mit der linken Seite der letzten Ungleichung. Wenn wir die Zufallsvariable $X \sim P$ wählen - also $Pr [X = x] = P (x)$ und $Y := \frac{Q (X)}{P (X)}$ setzen, dann ist $Y$ auch eine Zufallsvariable, die endlich viele Werte annimmt (höchstens so viele wie $X$ selbst, also maximal $| X |$ viele). Darüberhinaus ist $Y$ auch immer definiert: $X$ nimmt ja nur jene Werte $x \in X$ an, für die $P (x) > 0$ gilt. Und für jedes $x \in X$ gilt ja auch $Q (x) > 0$ . Somit ist $Y = \frac{Q (X)}{P (X)}$ definiert und größer als $0$ , und so ist auch $\log Y$ auch definiert. Die linke Seite der obigen Ungleichung ist also

\begin{array}{r} \underset{P}{E} [\log_{2} (Y)] . \end{array}

Nun ist $Y$ eine Zufallsvariable, die nur endlich viele Werte annimmt, und $\log_{2}$ ist eine konkave Funktion. Wir wenden Jensens Ungleichung Reference "theorem-jensen" not found. Go to put-all-in-one-page.html and read the instructions. an:

\begin{array}{r} \underset{P}{E} [\log_{2} (Y)] \leq \log_{2} (\underset{P}{E} [Y]) . \end{array}

Was ist $E_{P} [Y]$ , der Erwartungswert von $Y$ über der Wahrscheinlichkeitsverteilung $P$ ?

\begin{aligned} \underset{P}{E} [Y] & = \sum_{x \in X} P (x) Y (x) \\ = \sum_{x \in X} P (x) \frac{Q (X)}{P (X)} \\ = \sum_{x \in X} Q (x) . \end{aligned}

Diese Summe ist, nach der Kraft-McMillan-Ungleichung (Reference "theorem-kraft-ineq" not found. Go to put-all-in-one-page.html and read the instructions.) höchstens $1$ , und somit ist ihr Logarithmus höchstens $0$ . $◻$

Anmerkung. Ganz allgemein gilt, mit der gleichen Rechnung wie gerade eben: wenn $P$ und $Q$ zwei Wahrscheinlichkeitsverteilungen über einer Menge $X$ sind und $Q (x) > 0$ ist für alle $x$ mit $P (x) > 0$ , dann ist

\begin{array}{r} (2) & \underset{x \sim P}{E} [\frac{P (x)}{Q (x)}] \end{array}

definiert und nichtnegativ. Der Ausdruck ( $2$ ) ist als Kullback-Leibler-Divergenz bekannt und wird auch mit $K L (P | | Q)$ abgekürzt. Im Lichte der obigen Rechnung hat $K L (P | | Q)$ folgende Interpretation (die mit einer Prise Salz zu nehmen ist): wenn wir davon ausgehen, dass die Elemente $X \sim X$ der Verteilung $Q$ folgen und einen präfixfreien Code konstruieren, der für $Q$ optimal wäre, die wirklich Wahrscheinlichkeitsverteilung jedoch $P$ ist, dann ist $K L (P | | Q)$ der Preis, den wir für diese Fehleinschätzung bezahlen müssen: im Schnitt ist jedes Codewort um $K L (P | | Q)$ länger, als es in einer für $P$ optimalen Verteilung der Fall wäre.

Beweis (obere Schranke). Der Einfachheit halber sei $X = {x_{1}, \dots, x_{n}}$ und $p_{i} := P (x_{i})$ . Wir setzen $l_{i} := ⌈ \log_{2} p_{i} ⌉$ . Der Ausdruck $2^{- l_{i}}$ ist also $p_{i}$ , abgerundet auf die nächstkleinere Zweierpotenz. So würden wir beispielsweise $1 / 7$ auf $1 / 8$ abrunden und $15 / 32$ auf $1 / 4$ . Es gilt

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

Wir können also den zweiten Teil von Reference "theorem-kraft-ineq" not found. Go to put-all-in-one-page.html and read the instructions., der Kraft-McMillan-Ungleichung anwenden und erhalten einen präfixfreien Code ${c_{1}, \dots, c_{n}}$ mit $| c_{i} | = l_{i} = ⌈ \log_{2} p_{i} ⌉$ . Somit ist ( $1$ ) gezeigt. Für die erwartete Codelänge gilt nun

\begin{aligned} \underset{x \sim P}{E} [| C (x) |] & = \underset{x \sim P}{E} [⌈ \log_{2} (\frac{1}{P (x)}) ⌉] \\ < \underset{x \sim P}{E} [1 + \log_{2} (\frac{1}{P (x)})] \\ = 1 + \underset{x \sim P}{E} [\log_{2} (\frac{1}{P (x)})] \\ = 1 + H (P) . \end{aligned}

Somit ist Teil 2 gezeigt. $◻$

Der definierte Code für $X$ weißt individuelle Optimalität auf: es gilt $| C (x) | \leq 1 + \log_{2} (\frac{1}{P (x)})$ für jedes $x$ . Diese individuelle Optimalität gilt aber im Allgemeinen nicht für das Ergebnis des Huffman-Algorithmus:

Übungsaufgabe 1.5.1 Sei $p \in [0, 1]$ und $n \in N$ . Definieren Sie eine Wahrscheinlichkeitsverteilung über ${1, \dots, n}$ mit $P (1) = p$ , so dass $| C^{*} (1) |$ möglichst groß wird; der Code $C^{*}$ ist hier der vom Huffman-Algorithmus erzeugte optimale Code. Zeigen Sie, dass $| C^{*} (1) |$ deutlich größer werden kann als $\log_{2} (\frac{1}{P (1)})$ .