Mit Google fortfahren
Entropie in der Informatik verstehen und berechnen
Die Entropie misst die durchschnittliche Unsicherheit einer diskreten Informationsquelle. Je ungewisser ihr nächstes Symbol ist, desto größer ist ihre Entropie. Mit Logarithmen zur Basis 2 wird sie in Bit pro Symbol angegeben.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Von Wahrscheinlichkeit zu Information
Warum überrascht dich eine seltene Nachricht stärker als eine erwartete? Die Informationstheorie beschreibt diesen Unterschied mit dem Informationsgehalt eines Ergebnisses $x$:
$$I(x)=-\log_2 p(x)=\log_2\frac{1}{p(x)}$$
Dabei ist $p(x)$ die Wahrscheinlichkeit des Ergebnisses. Je kleiner $p(x)$ ist, desto größer ist $I(x)$.
Informationsgehalt
Der Informationsgehalt $I(x)$ misst die Überraschung eines einzelnen Ergebnisses. Bei einem sicheren Ergebnis mit $p(x)=1$ gilt $I(x)=0$ Bit. Bei $p(x)=0{,}5$ gilt $I(x)=1$ Bit.
Die Entropie betrachtet dagegen alle möglichen Ergebnisse einer Quelle und mittelt deren Informationsgehalte nach ihren Wahrscheinlichkeiten.
Informationsgehalt gehört zu einem Ergebnis. Entropie gehört zur gesamten Wahrscheinlichkeitsverteilung.
Bei einer fairen Münze haben „Kopf“ und „Zahl“ jeweils die Wahrscheinlichkeit $0{,}5$. Jedes Ergebnis besitzt daher den Informationsgehalt
$$-\log_2(0{,}5)=1\ \text{Bit}.$$
Vor dem Wurf ist offen, welches der beiden Ergebnisse eintritt. Nach dem Wurf ist diese Unsicherheit beseitigt.
Entropie Schritt für Schritt berechnen
Für eine diskrete Zufallsvariable $X$ mit den möglichen Ergebnissen $x_1,\dots,x_n$ und Wahrscheinlichkeiten $p_1,\dots,p_n$ lautet die Shannon-Entropie:
$$H(X)=-\sum_{i=1}^{n}p_i\log_2p_i$$
Die Wahrscheinlichkeiten müssen zusammen 1 ergeben. Für ein unmögliches Ergebnis verwendet man die Konvention $0\log_2 0:=0$; es trägt nichts zur Summe bei.
So gehst du vor:
- Notiere alle möglichen Ergebnisse und ihre Wahrscheinlichkeiten.
- Prüfe, ob die Wahrscheinlichkeiten zusammen 1 ergeben.
- Berechne für jedes Ergebnis $I(x_i)=-\log_2p_i$.
- Gewichte jeden Informationsgehalt mit $p_i$.
- Addiere die Beiträge und deute die Einheit Bit pro Symbol.
Die Quelle ABBCAADA enthält acht Zeichen. Es gelten
- $p_A=4/8=0{,}5$,
- $p_B=2/8=0{,}25$,
- $p_C=p_D=1/8=0{,}125$.
Die Informationsgehalte sind 1 Bit für A, 2 Bit für B und jeweils 3 Bit für C und D. Daher:
$$H=0{,}5\cdot1+0{,}25\cdot2+0{,}125\cdot3+0{,}125\cdot3=1{,}75\ \text{Bit/Zeichen}.$$
Das Ergebnis ist ein Mittelwert. Es behauptet nicht, dass jedes einzelne Zeichen genau $1{,}75$ Bits besitzt.
Maximum, Minimum und Vergleich
Bei $n$ möglichen Symbolen ist die Entropie am größten, wenn alle Symbole gleich wahrscheinlich sind:
$$H_{\max}=\log_2 n$$
Damit gilt immer:
$$0\le H(X)\le\log_2 n$$
Entropie 0 bedeutet: Ein Ergebnis ist sicher. Maximale Entropie bedeutet: Die Verteilung ist gleichmäßig und die Unsicherheit innerhalb dieses Modells am größten.
Ein fairer sechsseitiger Würfel hat sechs gleich wahrscheinliche Ergebnisse. Deshalb gilt
$$H=\log_2 6\approx2{,}585\ \text{Bit pro Wurf}.$$
Ein fairer achtseitiger Würfel hat $H=\log_2 8=3$ Bit. Drei Bit passen hier genau, weil $2^3=8$ gleich wahrscheinliche Möglichkeiten unterschieden werden können.
Für Quellen mit unterschiedlich großen Alphabeten kann die normierte Entropie hilfreich sein:
$$H_{\mathrm{norm}}=\frac{H}{H_{\max}}$$
Sie liegt zwischen 0 und 1. Ein Wert von 1 bedeutet Gleichverteilung bezogen auf das gewählte Alphabet.
Die Logarithmusbasis bestimmt die Einheit. Basis 2 liefert Bit. Auch die gewählte Symbolisierung zählt: Dieselben Daten können auf Bit- und Byteebene unterschiedlich bewertet werden.
Abhängigkeiten verändern die Unsicherheit
Reichen gleiche Häufigkeiten aus, um eine Folge zu beurteilen? Nein. Vergleiche diese beiden Quellen:
- Die periodische Folge
1010101010...wechselt immer vorhersehbar. - Eine unabhängige faire Binärquelle wählt jedes Zeichen neu mit gleicher Wahrscheinlichkeit.
Bei beiden treten 0 und 1 gleich häufig auf. Ihre Einzelzeichenentropie ist deshalb jeweils 1 Bit. Trotzdem ist nach einer 1 das nächste Zeichen der periodischen Folge bereits bestimmt.
Für Zeichenblöcke der Länge $n$ verwendet man:
$$H_n=-\sum_{w}p(w)\log_2p(w)$$
Die Summe läuft über die möglichen Wörter $w$ der Länge $n$. Für unabhängige, gleich verteilte Zeichen gilt $H_n=nH_1$. Bei Abhängigkeiten kann die Entropie pro Zeichen kleiner sein.
Bedingte Entropie
Die bedingte Entropie $H(Y\mid X)$ misst, wie viel Unsicherheit über $Y$ übrig bleibt, wenn $X$ bekannt ist. Ist das nächste Zeichen durch das vorige vollständig bestimmt, beträgt diese Restunsicherheit 0.
Gleiche Einzelzeichenhäufigkeiten bedeuten nicht gleiche Struktur. Um Reihenfolgen zu untersuchen, brauchst du Blockwahrscheinlichkeiten oder bedingte Wahrscheinlichkeiten.
Entropie setzt eine Grenze für Kompression
Verlustfreie Kompression muss die ursprünglichen Daten vollständig wiederherstellen können. Häufige Symbole erhalten in geeigneten variablen Codes kurze Codewörter, seltene längere. So nähert sich die mittlere Codelänge der Entropie.
Für einen geeigneten eindeutig decodierbaren Binärcode mit mittlerer Codelänge $L$ gilt als grundlegende Grenze:
$$H\le L$$
Dabei werden $H$ und $L$ jeweils in Bit pro Symbol verglichen. Entropie ist also keine fertige Codierung, sondern eine theoretische Untergrenze für die durchschnittliche verlustfreie Darstellung im verwendeten Quellenmodell.
Für die Verteilung $p_A=1/2$, $p_B=1/4$, $p_C=p_D=1/8$ hat ein fester Code für vier Symbole stets Länge 2 Bit:
- A →
00 - B →
01 - C →
10 - D →
11
Ein variabler Präfixcode kann lauten:
- A →
1 - B →
01 - C →
000 - D →
001
Kein Codewort ist der Anfang eines anderen; deshalb ist der Code ohne Trennzeichen eindeutig decodierbar. Seine mittlere Länge ist
$$L=\frac12\cdot1+\frac14\cdot2+\frac18\cdot3+\frac18\cdot3=1{,}75\ \text{Bit/Zeichen}.$$
Hier stimmt $L$ mit der Entropie überein. Huffmans Verfahren konstruiert für gegebene Einzelzeichenhäufigkeiten einen optimalen Präfixcode, indem es wiederholt die zwei kleinsten Gewichte verbindet.
Kleine Entropie weist auf statistische Regelmäßigkeiten und damit auf Kompressionspotenzial hin. Trotzdem garantiert kein verlustfreies Verfahren, dass jede mögliche Eingabe kürzer wird. Außerdem kann ein Modell, das nur Einzelzeichen zählt, Regelmäßigkeiten in längeren Folgen übersehen.
Typische Denkfehler sicher vermeiden
„Hohe Entropie beweist Zufälligkeit.“ Das stimmt nicht. Eine Häufigkeitsmessung kann unerkannte Abhängigkeiten enthalten. Sie beweist auch nicht, ob eine Folge von einer echten oder einer pseudozufälligen Quelle stammt.
„Entropie ist die Zahl möglicher Ergebnisse.“ Das stimmt nur nach einer Umformung für Gleichverteilung: Dann ist $H=\log_2 n$. Bei ungleichen Wahrscheinlichkeiten brauchst du die vollständige Shannon-Formel.
„Ein seltenes Symbol senkt immer die Entropie.“ Ein seltenes Symbol hat hohen Informationsgehalt. Sein Beitrag zur Entropie ist aber $p\cdot I$ und wird mit seiner kleinen Wahrscheinlichkeit gewichtet. Entscheidend ist stets die ganze Verteilung.
„Redundanz ist immer schlecht.“ Bei Kompression möchte man statistische Redundanz verringern. Für Fehlererkennung und Fehlerkorrektur kann man dagegen bewusst zusätzliche Bits einbauen. Das sind verschiedene Ziele.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Entropie in der Informatik
- Wahrscheinlichkeit → Informationsgehalt eines Ergebnisses
- Verteilung → mittlere Information $H(X)$
- Gleichverteilung → maximale Entropie $\log_2n$
- Abhängigkeit → Block- und bedingte Entropie
- Quellenmodell → gewählte Symbole und erfasste Muster
- Kompression → Untergrenze der mittleren Codelänge