Effiziente Algorithmen, Kapitel 1.6

1.6 Schranken für nicht-präfixfreie Codes

In den letzten Kapiteln haben wir gelernt, dass die erwartete Codelänge eines präfixfreien Codes $C : X \to {0, 1}^{*}$ durch die Entropy $H (P)$ der Verteilung $P$ auf $X$ bestimmt ist (bis auf plus minus 1). In diesem Teilkapitel fragen wir uns: was können wir die erwartete Codelänge eines nicht notwendigerweise präfixfreien Codes sagen?

Ich bin urpsrünglich davon ausgegangen, dass diese Frage mit Google innerhalb von 5 Minuten beantwortet sein sollte. Ich lag falsch und konnte tatsächlich erst einmal keine Referenz dafür finden. Mittlerweile hat Immanuel Engel sie gefunden, vielen Dank! Ich könnte nun einfach Mehlhorn (1971) und Bayer (1975) zitieren. Auf der anderen Seite ist dies eine gute Gelegenheit, die Vorlesung zu pausieren und eine längere Übungssitzung. einzuleiten.

Übungsaufgabe 1.6.1 Sei $C : X \to {0, 1}^{*}$ ein nicht präfixfreier Code. Wie können Sie ihn präfixfrei machen? Wie ändert sich dadurch die erwartete Codelänge?

Übungsaufgabe 1.6.2 Machen Sie $C$ präfixfrei, indem Sie ein Trennungszeichen $;$ hinzufügen. Sie erhalten nun einen Code $C^{'} : X \to {0, 1,;}$ . Anstatt diesen jetzt wieder binär zu codieren, lernen Sie, mit ternären Codes zu leben. Können Sie die erwartete Codelänge eines ternären Codes mit der Shannon-Entorpie in Verbindung setzen?

Übungsaufgabe 1.6.3 Gehen Sie noch radikaler vor: versuchen Sie, für eine Wahrscheinlichkeitsverteilung $P$ auf $X$ den optimalen nicht-präfixfreien Code zu konstruieren. Wie schaut dieser aus? Was ist seine erwartete Codelänge?

Wir haben nun also gesehen, dass ein optimaler nicht präfixfreier Code einfach die Menge ${0, 1}^{*}$ von unten ( $ϵ$ ) nach oben auffüllt mit absteigenden Wahrscheinlichkeiten. So ist zum Beispiel der optimale Code für die Wahrscheinlichkeitsverteilung $[(a : 0.2), (b : 0.1), (c : 0.4), (d : 0.3)]$ einfach $C : [c \mapsto ϵ, d \mapsto 0, a \mapsto 1, b \mapsto 00]$ . Die Struktur von $C$ ist also einfach: reihe die Elemente von ${0, 1}^{*}$ der Länge sortiert aufsteigend und reihe die Elementen von $X$ nach Wahrscheinlichkeit absteigend sortiert. Dann weiße jedem $x \in X$ das entsprechende Codewort in der Reihe zu. Statt uns über $C : X \to {0, 1}^{*}$ und seine erwartete Codelänge bei der Wahrscheinlichkeiten $P$ Gedanken zu machen, können wir $P$ einfach als Wahrscheinlichkeitsverteilung über ${0, 1}^{*}$ betrachten und uns fragen, wie die beiden Größens

\begin{array}{r} H (P) \end{array}

und

\begin{array}{r} \underset{x \sim P}{E} [| x |] \end{array}

zusammenhängen.

Beobachtung 1.6.1 Sei $μ \in R$ . Sie wollen eine Verteilung $P$ auf ${0, 1}^{*}$ definieren mit $E_{x \sim P} [| x |] = μ$ , wollen aber $H (P)$ so groß wie möglich machen. Wenn nun $| x | = | y |$ zwei Bitstrings gleicher Länge sind, was können Sie über $P (x)$ und $P (y)$ sagen?

Wir haben nun gesehen, dass eine Verteilung, die bei festem $E_{x \sim P} [| x |]$ die Entropie maximiert, den Elementen in jedem Level, also in jeder Menge ${0, 1}^{n}$ gleiche Wahrscheinlichkeiten zuweisen muss. Dass es also Wahrscheinlichkeiten $p_{0}, p_{1}, p_{2}$ gibt mit $\sum_{k = 0}^{\infty} p_{k} = 0$ und

\begin{array}{r} P (x) = \frac{p_{k}}{2^{k}} für alle x \in {0, 1}^{k} . \end{array}

Übungsaufgabe 1.6.4 Schreiben Sie $H (P)$ als Ausdruck in den $p_{i}$ .

Übungsaufgabe 1.6.5 Für einen gegebenen Erwartungswert $μ$ : welche Wahrscheinlichkeitsverteilung $P$ über $N$ mit $E_{x \sim P} [x] = μ$ hat maximale Entropie?

Tip: Schreiben Sie $p_{0}, p_{1}, p_{2}, \dots$ für die Wahrscheinlichkeiten der jeweiligen natürlichen Zahlen. Schreiben Sie $H (P)$ als (unendliche) Summe in den $p_{i}$ . Jetzt "rütteln" Sie an den $p_{i}$ .

Wie können Sie an den $p_{i}$ rütteln, ohne dass sich $E [X]$ ändert?
Was ist die "einfachste" Rüttelbewegung, die möglichst wenige $p_{i}$ verändert?
Schreiben Sie die Aussage "die Rüttelbewegung erhöht die Entropie nicht" formal als Ungleichung in den $p_{i}$ , an denen Sie rütteln.