Entropie in der Informatik verstehen und berechnen

Stell dir eine Quelle vor, die Zeichen sendet, zum Beispiel Buchstaben einer Nachricht. Der Informationsgehalt gehört zu einem einzelnen Ereignis, also zu einem bestimmten Zeichen. Er hängt von der Wahrscheinlichkeit p ab, mit der das Zeichen auftritt: I = −log₂ p, gemessen in Bit. Je kleiner die Wahrscheinlichkeit, desto höher der Informationsgehalt. Ein häufiges Zeichen überrascht kaum und trägt wenig Information.

Warum ist das so? Tritt ein Ereignis mit der Wahrscheinlichkeit p ein, wird ein Ereignis aus 1/p gleich wahrscheinlichen Möglichkeiten ausgewählt. Um so viele Möglichkeiten zu unterscheiden, braucht man log₂(1/p) Bit. Ein Zeichen mit p = 0,0625 hat deshalb den Informationsgehalt 4 bit, denn 1/0,0625 = 16 Möglichkeiten brauchen 4 bit.

Die Entropie gehört dagegen zur ganzen Verteilung, also zur Quelle mit allen ihren Zeichen. Man gewichtet den Informationsgehalt jedes möglichen Zeichens mit seiner Wahrscheinlichkeit. Das Ergebnis ist der mittlere Informationsgehalt pro Zeichen. Aus einem einzigen Wert von p kannst du die Entropie deshalb nicht ausrechnen: Jede Teilwahrscheinlichkeit geht in die Rechnung ein.

Beachte: „Information“ heißt hier nicht „Bedeutung“. Der Informationsgehalt sagt nichts darüber, wie wichtig eine Nachricht für dich ist.

Man spricht von Shannon-Entropie, weil das informationstheoretische Verständnis des Begriffs auf Claude E. Shannon zurückgeht. Hier gilt sie für eine kleine Quelle, deren Zeichen unabhängig voneinander auftreten (gedächtnislos). So gehst du vor:

Schritt 1: Schreibe die Wahrscheinlichkeit p jedes Zeichens auf. Sie sollten zusammen 1 ergeben, sonst kann das Ergebnis missverständlich sein. Schritt 2: Bestimme den Informationsgehalt −log₂ p jedes Zeichens. Schritt 3: Multipliziere jeden Informationsgehalt mit seiner Wahrscheinlichkeit und addiere alles. Das ergibt H = −Σ p · log₂ p. Das Zeichen Σ bedeutet „Summe über alle Zeichen“. Ein Zeichen mit p = 0 trägt nichts bei, denn man setzt 0 · log₂ 0 = 0.

Das Ergebnis deutest du so: Die Entropie ist der mittlere Informationsgehalt pro Zeichen. Einfach gesagt ist sie die durchschnittliche Anzahl von Entscheidungen (Bit), die man braucht, um ein Zeichen aus der Zeichenmenge zu bestimmen. Bei einer idealen Münze (Kopf und Zahl je 0,5) ergibt sich 1 bit. Bei einer gezinkten Münze, die im Mittel in 60 % der Fälle Kopf und in 40 % Zahl zeigt, ergibt sich nur noch etwa 0,971 bit. Die Ungewissheit ist hier geringer.

Bei einem idealen Würfel mit sechs gleich wahrscheinlichen Möglichkeiten gilt H = log₂ 6 ≈ 2,585 bit. Bei acht gleich wahrscheinlichen Möglichkeiten ist H = log₂ 8 = 3 bit. Das entspricht drei Würfen mit einer idealen Münze. Die Einheit „Shannon“ (Sh) ist als Informationsgehalt eines Ereignisses mit p = 0,5 definiert, etwa Kopf beim Münzwurf. Auf dieser Seite schreiben wir „bit“.

Die Entropie ist maximal, wenn alle N Zeichen gleich wahrscheinlich sind, also p = 1/N für jedes Zeichen. Dann gilt Hmax = log₂ N. Bei zwei Zeichen (0 und 1, gleich häufig) ist das 1 bit pro Zeichen. Bei vier gleich wahrscheinlichen Zeichen (je 0,25) ist es log₂ 4 = 2 bit. Die Ungewissheit ist am größten, wenn du das nächste Zeichen überhaupt nicht vorhersagen kannst.

Die Entropie ist null, wenn ein Zeichen die Wahrscheinlichkeit 1 hat und alle anderen 0. Dann gibt die Quelle immer dasselbe Zeichen aus. Es gibt keine Unsicherheit darüber, was als Nächstes kommt, und du erhältst keine Information. Die Zeichen mit p = 0 tragen nichts zur Summe bei.

Alles andere liegt dazwischen. Bei zwei Zeichen mit den Wahrscheinlichkeiten p und 1 − p ist die Entropie bei p = 0,5 am größten. Die Kurve ist symmetrisch zu p = 0,5 und fällt bei p → 0 und bei p → 1 auf 0 ab. Auch eine Quelle mit nur einem Zeichen im Alphabet bringt keine neue Information. Deshalb sind mindestens zwei verschiedene Zeichen sinnvoll.

Nimm die Kette 1010101010… Die Wahrscheinlichkeit, eine 0 oder eine 1 zu finden, ist genauso groß wie in einer Kette aus wiederholtem Münzwurf. Die Entropie H₁ einzelner Zeichen ist deshalb für beide Ketten gleich, obwohl die erste Kette weniger zufällig ist. H₁ betrachtet jedes Zeichen einzeln und beachtet nicht, was davor kam.

Bei Zeichenpaaren zeigt sich der Unterschied: Die Kette 1010… liefert H₂ = 1, die Münzkette H₂ = 2. Das deutest du so: Bei 1010… hängt die Wahrscheinlichkeit eines Zeichens vom vorigen Zeichen ab. Die Zeichen sind nicht unabhängig. Wären sie unabhängig, würde Hₙ = n · H₁ gelten. Die bedingte Entropie berücksichtigt vorangegangene Zeichen. Bei einer Quelle, die periodisch ...00100010001000... sendet, ist sie ohne berücksichtigte Zeichen etwa 0,811 bit. Kennt man schon drei Zeichen davor, ist das nächste festgelegt, und die Entropie ist 0.

Entropietests prüfen, wie gut Daten komprimierbar sind oder wie gut Zufallszahlen sind. Bei Zufallszahlen gilt der Test ab einem Mindestwert, zum Beispiel 7 Bit je Byte (ein Datenblock aus mehreren Bit), als bestanden. Es gibt viele solcher Tests, weil die Entropie nicht eindeutig ist: Sie kann bitbasiert oder bytebasiert definiert sein.

Ein Beispiel: Eine Quelle gibt nur die Werte 0xAA (dezimal 170) und 0x55 (dezimal 85) aus, beide mit gleicher Wahrscheinlichkeit. Bitweise ist die Ausgabe zu 50 % 0 oder 1, die normierte Entropie ist 1. Byteweise sind nur zwei von 256 möglichen Werten im Spiel, die normierte Entropie ist 1/8. Ein Hersteller würde die bitweise Entropie 1 angeben. Selbst wenn die Werte gleich wahrscheinlich sind, kann die Folge 0xaaaa viel häufiger sein als 0x5555. Entropietests messen nur Gleichwahrscheinlichkeit, aber keine echte Unvorhersehbarkeit.

Datenkompression verkleinert die Menge digitaler Daten. Dann sinkt der Speicherbedarf, und die Übertragung dauert kürzer. Bei verlustfreier Kompression kann man aus den komprimierten Daten wieder exakt die Originaldaten gewinnen. Das ist zum Beispiel bei ausführbaren Programmdateien notwendig. Dafür entfernt man redundante Informationen. Redundant heißt: Die Daten lassen sich in kürzerer Form darstellen, ohne dass etwas verloren geht.

Die Verbindung zur Entropie: Bei einer kleinen Entropie enthält der Informationstext Redundanzen oder statistische Regelmäßigkeiten. Genau die nutzen verlustfreie Verfahren aus. Sie versuchen, Nachrichten so zu codieren, dass sie sich ihrer Entropie möglichst gut annähern. Ein Beispiel ist der Morse-Code: Häufige Buchstaben der englischen Sprache bekommen kurze Codes, seltene lange Codes.

Ohne Redundanz geht das nicht. Bei völlig zufälligen Daten ist verlustlose Kompression prinzipiell unmöglich. Es fehlt jede erkennbare Struktur, und die „Anleitung“ zum Wiederherstellen müsste die unveränderten Originaldaten enthalten.

Dazu kommt das Taubenschlagprinzip: Auf n Bit kann man eine von 2ⁿ möglichen Informationen speichern. Auf ein Bit weniger passen nur halb so viele: 16 Bit → 2¹⁶ = 65536 Möglichkeiten, 15 Bit → 2¹⁵ = 32768 Möglichkeiten. Könnte man jede Datei um ein Bit verkleinern, müssten sich zwei verschiedene komprimierte Dateien denselben Platz teilen. Dann wäre die Rückgewinnung nicht mehr eindeutig. Deshalb lassen sich viele, aber nicht alle Daten komprimieren. Rein zufällige Daten sind höchstwahrscheinlich unkomprimierbar.