Entropie erklärt

1948 stellte ein Ingenieur an den Bell Labs, Claude Shannon, eine Frage, die noch niemand präzise gefasst hatte: Wie viel Information enthält eine Nachricht? Seine Antwort war eine Zahl, gemessen in Bit, die nicht davon abhängt, was eine Nachricht bedeutet, sondern davon, wie überraschend sie ist. Diese Zahl, die Entropie, setzt jedem Kompressionsprogramm, jeder Netzwerkverbindung und jedem Speichermedium Grenzen, und sie erklärt, warum manche Texte auf einen Bruchteil ihrer Größe schrumpfen, während sich andere überhaupt nicht zusammenpressen lassen.

Balken von Buchstabenwahrscheinlichkeiten, die von häufig zu selten verblassen, mit der Entropiekurve, die sinkt, je mehr Kontext bekannt ist
Balken von Buchstabenwahrscheinlichkeiten, die von häufig zu selten verblassen, mit der Entropiekurve, die sinkt, je mehr Kontext bekannt ist

Information ist Überraschung

Shannons Einsicht war, Information danach zu messen, wie unerwartet eine Nachricht ist, nicht danach, was sie bedeutet. Kennt man die Antwort schon, erfährt man durch sie nichts; hätte sie eines von tausend Dingen sein können, erfährt man viel. Eine Nachricht, die eine von zwei gleich wahrscheinlichen Möglichkeiten auswählt, trägt ein Bit. Eine von vier braucht zwei Bit, eine von acht drei Bit, und allgemein braucht eine von N gleich wahrscheinlichen Möglichkeiten log₂ N Bit. Ein Symbol, das mit der Wahrscheinlichkeit p auftritt, trägt daher −log₂ p Bit: Je seltener es ist, desto mehr verrät es.

Shannons Formel

Die Entropie ist die durchschnittliche Information pro Symbol: H = −Σ p log₂ p, summiert über alle Symbole mit ihrer Wahrscheinlichkeit p. Für eine faire Münze ist H gleich 1 Bit. Für eine Münze, die in 90 % der Fälle Kopf zeigt, sind es nur 0,47 Bit, weil das Ergebnis meist keine Überraschung ist. Die Entropie ist am größten, wenn alle Symbole gleich wahrscheinlich sind, log₂ n Bit für n Symbole, und null, wenn ein Symbol sicher ist. Shannon wählte den Namen auf Anraten von John von Neumann, weil dieselbe Formel in der Physik vorkommt, wo die Entropie Unordnung misst.

Claude Shannon, der 1948 bei Bell Labs präzise bestimmte, wie viel Information eine Nachricht enthält, und sie in Bits maß.
Claude Shannon, der 1948 bei Bell Labs präzise bestimmte, wie viel Information eine Nachricht enthält, und sie in Bits maß.

Die Grenze der Kompression

Shannons Quellencodierungstheorem besagt, dass kein verlustfreier Code im Mittel weniger Bit pro Symbol verwenden kann als die Entropie der Quelle und dass Codes ihr beliebig nahe kommen können. Die Huffman-Codierung, 1952 von David Huffman als Student erfunden, gibt häufigen Symbolen kurze und seltenen lange Codes und kommt bis auf ein Bit pro Symbol an die Entropie heran; die arithmetische Codierung kommt noch näher. Die Entropie ist also nicht nur eine Beschreibung, sondern eine harte Grenze: Eine Datei aus zufälligen Bytes mit 8 Bit Entropie pro Byte lässt sich überhaupt nicht komprimieren.

David Huffman, fotografiert als Professor an der UC Santa Cruz. Als Doktorand am MIT fand er 1951 seinen optimalen Code in einer Hausarbeit für Robert Fanos Kurs.
David Huffman, fotografiert als Professor an der UC Santa Cruz. Als Doktorand am MIT fand er 1951 seinen optimalen Code in einer Hausarbeit für Robert Fanos Kurs.

Kontext und Redundanz

Die Buchstaben eines Textes sind nicht unabhängig. Im Englischen folgt auf Q ein U, auf einen Punkt ein Großbuchstabe, und ein englisches Wort, das mit INFORMA beginnt, geht fast sicher mit TION weiter. Berücksichtigt man die vorherigen Symbole, erhält man die bedingte Entropie, die kleiner ist als die Entropie der einzeln gezählten Symbole. Der Unterschied ist die Redundanz: der Teil der Nachricht, der sich hätte vorhersagen lassen. Kompressionsprogramme wie ZIP, das das Deflate-Verfahren nutzt, finden wiederholte Zeichenfolgen und ersetzen sie durch kurze Verweise, und moderne Kompressoren sagen jedes Symbol aus seinem Kontext vorher.

Wie viel Information steckt im Englischen?

Buchstabe für Buchstabe gezählt, mit den Häufigkeiten des Englischen, trägt ein Buchstabe etwa 4,1 Bit, gegenüber 4,7 für zufällig gewählte Buchstaben. 1951 ging Shannon weiter: Er zeigte Menschen den Anfang eines Textes, ließ sie den nächsten Buchstaben raten und zählte, wie viele Versuche sie brauchten. Aus ihren Antworten schätzte er, dass Englisch nur etwa 0,6 bis 1,3 Bit pro Buchstabe trägt. Mit anderen Worten: Rund drei Viertel des geschriebenen Englisch sind Redundanz, und deshalb lässt sich ein Text mit fehlenden Buchstaben meist trotzdem lesen.

Zufall und Passwörter

Die Entropie misst auch Unvorhersagbarkeit, und davon hängt Sicherheit ab. Ein Schlüssel oder Passwort, das gleichverteilt aus N Möglichkeiten gewählt wird, hat log₂ N Bit Entropie, und ein Angreifer muss im Mittel etwa die Hälfte davon ausprobieren. Ein zufälliges Passwort aus 12 der 26 Kleinbuchstaben hat etwa 56 Bit; ein gängiges Wort hat weit weniger, egal wie lang es ist. Zufallszahlengeneratoren werden geprüft, indem man kontrolliert, ob ihre Ausgabe die volle Entropie einer Zufallsquelle hat, und Betriebssysteme sammeln Entropie aus dem Rauschen von Zeitmessungen, um sie zu initialisieren.

Wo Entropie auftaucht

Die Entropie entscheidet, wie viele Bit ein Telefonat, ein Foto oder ein Videostream braucht und wie nahe ein Modem oder eine WLAN-Verbindung an die Kapazität ihres Kanals herankommt. Biologen messen mit ihr die Information in der DNA, wo vier Basen höchstens je 2 Bit tragen können, und die Vielfalt eines Ökosystems. Im maschinellen Lernen wählen Entscheidungsbäume die Frage, die die Entropie am stärksten senkt, und mit der Kreuzentropie als Verlustfunktion werden die meisten neuronalen Netze trainiert. Sprachwissenschaftler vergleichen Sprachen anhand ihrer Entropie pro Zeichen und pro Wort.

Selbst ausprobieren

Öffnen Sie den Entropie-Rechner, um einen beliebigen Text nach Zeichen, Wörtern oder Bytes zu messen. Vergleichen Sie einen Absatz mit zufälligen Buchstaben, Bits, Ziffern und DNA, sehen Sie die Überraschung jedes Symbols, wie viel Information der Text im Vergleich zu seiner Speichergröße enthält und wie die Bit pro Symbol sinken, je mehr Kontext bekannt ist – neben dem, was ZIP tatsächlich erreicht.

Häufig gestellte Fragen

Warum wird Entropie in Bit gemessen?

Weil Shannon Logarithmen zur Basis 2 verwendete, sodass eine Ja-Nein-Entscheidung zwischen gleichwertigen Möglichkeiten als eine Einheit zählt. Mit dem natürlichen Logarithmus ist die Einheit das Nat, etwa 1,44 Bit, und mit der Basis 10 das Hartley, etwa 3,32 Bit; Physiker und manche Statistiker verwenden diese.

Kann ein Text mehr Entropie haben als log₂ seines Alphabets?

Nein. Bei n verschiedenen Symbolen beträgt die Entropie höchstens log₂ n Bit pro Symbol, und das nur, wenn alle gleich häufig sind. Jedes Ungleichgewicht und jede Vorhersagbarkeit aus dem Kontext senkt sie.

Ist die Entropie der Informationstheorie dieselbe wie in der Physik?

Die Formeln haben dieselbe Gestalt: Boltzmann und Gibbs schrieben die physikalische Entropie als Summe über die Wahrscheinlichkeiten der mikroskopischen Zustände eines Systems. Die Bedeutung ist verwandt, denn beide messen, wie viel man nicht weiß, und Physiker haben inzwischen gezeigt, dass das Löschen eines Bits an Information eine kleine Wärmemenge freisetzen muss.

Warum bringt es nichts, eine komprimierte Datei noch einmal zu komprimieren?

Ein guter Kompressor entfernt den größten Teil der Redundanz, sodass seine Ausgabe fast zufällig ist, mit nahezu 8 Bit Entropie pro Byte. Es bleibt nichts mehr zu entfernen, und erneutes Komprimieren macht die Datei wegen des Overheads des Kompressors meist sogar etwas größer.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Entropie-Rechner öffnen