Vorlesung Informatik 1 - Teil B: Theorie
2.5 Entropie einer Datenquelle
Informationsgehalt eines Ereignisses:
Der Informationsgehalt eines Ereignisses hängt mit seiner Auftrittswahrscheinlichkeit p zusammen, wobei 0 < p < 1.
Morgen früh wird die Sonne aufgehen: geringer Informationsgehalt weil äußerst wahrscheinlich.
Morgen früh wird die Sonne nicht aufgehen: hoher Informationsgehalt weil äußerst unwahrscheinlich.
In der Informatik ist das Ereignis das Auftreten eines Zeichens zi aus dem Zeichenvorrat Z= {z1, z2, z3, ..., zn} \) und sein Informationsgehalt H ist definiert als:
H (zi) = log2 1/p (zi) = -log2 p(i) [bit]
Die Maßeinheit für den Informationsgehalt ist wieder [bit].
Auftrittswahrscheinlichkeiten gibt es nur in Zusammenhang mit einer Datenquelle. Eine Datenquelle Q über einem Zeichenvorrat Z ist ein Strom von Zeichen aus Z . Das kann ein Buch, eine Datei, eine Radiosendung oder ein Stream im Internet sein.
Beispiel: Z= { b, e, h, n}
Eine Datenquelle Q über diesem Zeichensatz könnte z.B. der Satz "neben eben heben" sein. Darin kommen die Zeichen mit unterschiedlicher Häufigkeit n vor: b: 3 mal e: 6 mal, h: 1 mal und n: 4 mal. Insgesamt besteht der Satz aus 14 Buchstaben.
Somit berechnet sich die Auftrittswahrschenlichkeit der Zeichen zu:
| Zeichen | n | p |
|---|---|---|
| b | 3 | 0,2143 |
| e | 6 | 0,4286 |
| h | 1 | 0,0714 |
| n | 4 | 0,2857 |
| Summe: | 14 | 1 |
Die Summe der Auftrittswahrscheinlichkeiten aller Zeichen ist immer 1.
In der Regel treten die Zeichen ziin Z mit unterschiedlicher Wahrscheinlichkeit p(zi) auf, z.B. ist in der deutschen Sprache der Buchstabe e viel häufiger als der Buchstabe y.
Multipliziert man den Informationsgehalt eines Zeichens mit seiner Auftrittswahrscheinlichkeit, bekommt man den gewichteten Informationsgehalt eines Zeichens.
Die Summe dieser gewichteten Informationsgehalte ist die Entropie der Datenquelle Q über dem Zeichensatz Z= \lbrace{z1, z2, z3, ..., zn} :
H(Q) = Σ p(zi) H(zi) = Σp(zi) log2 1/{p (zi) = - Σ p(zi) log2 p (zi) [bit]
Sie gibt an, wie viel Information mindestens notwendig ist, um ein Zeichen der Datenquelle ohne Verluste speichern zu können.
Die Entropie ist die untere Schranke der Informationsmenge, mit der eine Datenquelle noch verlustfrei codiert werden kann. Sie hängt von den Unterschieden der Auftrittswahrscheinlichkeiten ab:
- die Entropie ist am größten, wenn alle Zeichen gleich wahrscheinlich sind
- die Entropie ist am geringsten, wenn die Auftrittswahrscheinlichkeiten stark voneinander abweichen.
Beispiel:
Zeichenvorrat Z= { A, B, C, D }, Datenquelle Q= "AACCCCBD"
Das häufigste Zeichen ist C mit p(C)= 1/2, dann kommt A mit p(A)= 1/4, B und D treten mit der Wahrscheinlichkeit p(B)=p(D)= 1/8 auf.
Die Summe der Wahrscheinlichkeiten ist 1. Die Entropie H ist dann:
H=p(A) H(A) + P(B) H(B) + P(C) H(C) + P(D) H(D) = 2/4 + 3/8 +1/2 + 3/8 = 1,75 [bit]
Die Bedeutung dieser Zahl: es ist möglich, diese Datenquelle mit 1,75 [bit] pro Zeichen verlustfrei zu speichern.
Wären alle Zeichen gleich wahrscheinlich, also z.B. bei der Datenquelle Q'= "AABBCCDD", dann wäre die Entropie 2 bit.
Wir erinnern uns an Kapitel 1.6: mittlerer Entscheidungsgehalt. Dieser berücksichtigt nicht die Unterschiede der Auftrittswahrscheinlichkeiten der Zeichen, sondern setzt die Wahrscheinlichkeit aller Zeichen zu 1/4. Dann ergibt sich ein mittlere Entscheidungsgehalt von 2 [bit].
Daraus folgt:
- Mit 2 Bit kann man die Zeichen mit fester Wortlänge codieren, z.B. A: 00, B: 01, C:10, D:11
- es muss eine Codierung geben, die auch mit 1,75 Bit pro Zeichen auskommt - die lernen wir im nächsten Kapitel kennen.
Wenn alle Zeichen mit der gleichen Wahrscheinlich \(p\) auftreten, ist die Entropie gleich dem mittleren Entscheidungsgehalt:
H(Q) = - Σ p log2 p =log_2 p Σ p = log2 n
Die DPCM verringert bei vielen Ton- und Bild-Datenquellen die Entropie und wird deshalb häufig vor einer Entropiecodierung durchgeführt.