Informationstheorie/Natürliche wertdiskrete Nachrichtenquellen

1. Informationstheorie
2. Entropie wertdiskreter Nachrichtenquellen
3. Natürliche wertdiskrete Nachrichtenquellen

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

Schwierigkeiten bei der Entropiebestimmung

Bisher haben wir uns ausschließlich mit künstlich erzeugten Symbolfolgen beschäftigt.  Nun betrachten wir geschriebene Texte.  Ein solcher Text kann als eine natürliche wertdiskrete Nachrichtenquelle aufgefasst werden, die natürlich auch informationstheoretisch analysiert werden kann, indem man ihre Entropie ermittelt.

Natürliche Texte werden auch in heutiger Zeit (2011) noch oft mit dem 8 Bit–Zeichensatz nach ANSI  ("American National Standard Institute")  dargestellt, obwohl es etliche „modernere” Codierungen gibt. 

Die  $M = 2^8 = 256$  ANSI–Zeichen sind dabei wie folgt belegt:

• Nr.  0   bis   31:   nicht druck– und darstellbare Steuerbefehle,
• Nr.  32   bis  127:   identisch mit den Zeichen des 7 Bit–ASCII–Codes,
• Nr.  128   bis 159:   weitere Steuerzeichen bzw. Alphanumerikzeichen für Windows,
• Nr.  160   bis   255:   identisch mit den Unicode–Charts.

Theoretisch könnte man auch hier die Entropie entsprechend der Vorgehensweise  im letzten Kapitel  als den Grenzübergang der Entropienäherung  $H_k$  für  $k \to \infty$  ermitteln.  Praktisch ergeben sich aber nach dieser Rezeptur unüberwindbare numerische Grenzen:

• Bereits für die Entropienäherung  $H_2$  gibt es  $M^2 = 256^2 = 65\hspace{0.1cm}536$  mögliche Zweiertupel.  Für die Berechnung sind somit ebenso viele Speicherplätze (in Byte) erforderlich.  Geht man davon aus, dass man für eine ausreichend sichere Statistik im Mittel  $100$  Entsprechungen pro Tupel benötigt, so sollte die Länge der Quellensymbolfolge bereits  $N > 6.5 · 10^6$  sein.
• Die Anzahl der möglichen Dreiertupel ist  $M^3 > 16 · 10^7$  und damit ist die erforderliche Quellensymbollänge schon  $N > 1.6 · 10^9$.  Dies entspricht bei  $42$  Zeilen pro Seite und  $80$  Zeichen pro Zeile einem Buch mit etwa  $500\hspace{0.1cm}000$  Seiten.
• Bei einem natürlichen Text reichen die statistischen Bindungen aber sehr viel weiter als über zwei oder drei Zeichen.  Küpfmüller gibt für die deutsche Sprache einen Wert von  $100$  an.  Zur Ermittlung der 100. Entropienäherung benötigt man aber  $2^{800}\approx10^{240}$  Häufigkeiten und für die gesicherte Statistik nochmals um den Faktor  $100$  mehr Zeichen.

Eine berechtigte Frage ist deshalb:   Wie hat  Karl Küpfmüller  im Jahre 1954 die Entropie der deutschen Sprache ermittelt, und vor ihm schon  Claude Elwood Shannon  die Entropie der englischen Sprache?  Eines sei vorweg verraten:   Nicht mit dem oben beschriebenen Ansatz.

Entropieabschätzung nach Küpfmüller

Karl Küpfmüller hat die Entropie von deutschen Texten untersucht.  Er geht bei seiner in  [Küpf54]  veröffentlichten Abschätzung von folgenden Voraussetzungen aus:

• ein Alphabet mit  $26$  Buchstaben  (keine Umlaute und Satzzeichen),
• Nichtberücksichtigung des Leerzeichens,
• keine Unterscheidung zwischen Groß– und Kleinschreibung.

Der Entscheidungsgehalt ergibt sich somit zu  $H_0 = \log_2 (26) ≈ 4.7\ \rm bit/Buchstabe$.

Küpfmüllers Abschätzung basiert auf den folgenden Überlegungen:

(1)  Die  erste Entropienäherung  ergibt sich aus den Buchstabenhäufigkeiten in deutschen Texten.  Nach einer Studie von 1939 ist „e” mit  $16.7\%$  am häufigsten, am seltensten ist „x” mit  $0.02\%$.  Über alle Buchstaben gemittelt ergibt sich 

$$H_1 \approx 4.1\,\, {\rm bit/Buchstabe}\hspace{0.05 cm}.$$

(2)  Hinsichtlich der  Silbenhäufigkeit  wertet Küpfmüller das von  Friedrich Wilhelm Kaeding  1898 herausgegebene „Häufigkeitswörterbuch der deutschen Sprache” aus.  Er unterscheidet zwischen Stammsilben, Vorsilben und Endsilben und kommt so zum mittleren Informationsgehalt aller Silben:

$$H_{\rm Silbe} = \hspace{-0.1cm} H_{\rm Stamm} + H_{\rm Vor} + H_{\rm End} + H_{\rm Rest} \approx 4.15 + 0.82+1.62 + 2.0 \approx 8.6\,\, {\rm bit/Silbe} \hspace{0.05cm}.$$

Hierbei wurden folgende Anteile berücksichtigt:

• Nach der Kaeding–Studie von 1898 bilden die  $400$  häufigsten Stammsilben  (beginnend mit „de”)  $47\%$  eines deutschen Textes und tragen zur Entropie mit  $H_{\text{Stamm}} ≈ 4.15 \ \rm bit/Silbe$  bei.
• Der Beitrag der  $242$  häufigsten Vorsilben – an erster Stelle „ge” mit  $9\%$ – wird von Küpfmüller mit  $H_{\text{Vor}} ≈ 0.82 \ \rm bit/Silbe$ beziffert.
• Der Beitrag der  $118$  meistgebrauchten Endsilben ist  $H_{\text{End}} ≈ 1.62 \ \rm bit/Silbe$.  Am häufigsten tritt am Wortende „en” mit  $30\%$  auf.
• Der Rest von  $14\%$  verteilt sich auf bisher nicht erfasste Silben.  Küpfmüller nimmt dazu an, dass es davon  $4000$  gibt und dass diese gleichverteilt sind.  Er setzt dafür  $H_{\text{Rest}} ≈ 2 \ \rm bit/Silbe$  an.

(3)  Als durchschnittliche Buchstabenzahl je Silbe ermittelte Küpfmüller den Wert  $3.03$.  Daraus schloss er auf die  dritte Entropienäherung  hinsichtlich der Buchstaben:

$$H_3 \approx {8.6}/{3.03}\approx 2.8\,\, {\rm bit/Buchstabe}\hspace{0.05 cm}.$$

(4)  Küpfmüllers Abschätzung der Entropienäherung  $H_3$  basierte vor allem auf den Silbenhäufigkeiten gemäß  (2)  und dem Mittelwert von  $3.03$  Buchstaben pro Silbe. Um eine weitere Entropienäherung  $H_k$  mit größerem  $k$  zu erhalten, analysierte Küpfmüller zusätzlich die Wörter in deutschen Texten.  Er kam zu folgenden Ergebnissen:

• Die  $322$  häufigsten Wörter liefern einen Entropiebeitrag von  $4.5 \ \rm bit/Wort$.
• Die Beiträge der restlichen  $40\hspace{0.1cm}000$ Wörter  wurden geschätzt.  Angenommen wurde, dass die Häufigkeiten von seltenen Wörtern reziprok zu ihrer Ordnungszahl sind.
• Mit diesen Voraussetzungen ergibt sich der mittlere Informationsgehalt (bezogen auf Wörter) zu ca.  $11 \ \rm bit/Wort$.

(5)  Die Auszählung „Buchstaben pro Wort” ergab im Mittel  $5.5$.  Analog zu Punkt  (3)  wurde so die Entropienäherung für  $k = 5.5$  angenähert. Küpfmüller gibt hierfür an:

$$H_{5.5} \approx {11}/{5.5}\approx 2\,\, {\rm bit/Buchstabe}\hspace{0.05 cm}.$$

Natürlich kann  $k$  gemäß  seiner Definition  nur ganzzahlige Werte annehmen.  Diese Gleichung ist deshalb so zu interpretieren, dass sich für  $H_5$  ein etwas größerer und für  $H_6$  ein etwas kleinerer Wert als  $2 \ {\rm bit/Buchstabe}$  ergeben wird.

Näherungswerte der Entropie der deutschen Sprache nach Küpfmüller

(6)  Man kann nun versuchen, aus diesen drei Punkten  $H_1$,  $H_3$,  $H_{5.5}$  durch Extrapolation den Endwert der Entropie für  $k \to \infty$  zu ermitteln.  In nebenstehender Grafik wird dies bei logarithmisch aufgetragener Abszisse verdeutlicht:

• Die durchgehende Linie ist der Küpfmüllerschen Originalarbeit  [Küpf54]  entnommen und führt zum Entropie-Endwert  $H = 1.6 \ \rm bit/Buchstabe$.
• Die grünen Kurven sind zwei Extrapolationsversuche (eines kontinuierlichen Funktionsverlaufes durch drei Punkte) des  $\rm LNTwww$–Autors.
• Diese und die braunen Pfeile sollen eigentlich nur zeigen, dass eine solche Extrapolation  (vorsichtig formuliert)  etwas vage ist.

(7)  Küpfmüller versuchte anschließend, den von ihm mit dieser ersten Abschätzung gefundenen Endwert  $H = 1.6 \ \rm bit/Buchstabe$  mit völlig anderer Methodik – siehe nächster Abschnitt – zu verifizieren. Nach dieser Abschätzung revidierte er sein Ergebnis geringfügig auf 

$$H = 1.51 \ \rm bit/Buchstabe.$$

(8)  Claude E. Shannon hatte drei Jahre vorher nach völlig anderer Vorgehensweise für die englische Sprache den Entropiewert  $H ≈ 1 \ \rm bit/Buchstabe$  angegeben, allerdings unter Berücksichtigung des Leerzeichens.  Um seine Ergebnisse mit Shannom vergleichen zu können, hat Küpfmüller das Leerzeichen nachträglich in sein Ergebnis eingerechnet.

• Der Korrekturfaktor ist der Quotient aus der mittleren Wortlänge ohne Berücksichtigung des Leerzeichens  $(5.5)$  und der mittleren Wortlänge mit Berücksichtigung des Leerzeichens  $(5.5+1 = 6.5)$.
• Diese Korrektur führte zu Küpfmüllers endgültigem Ergebnis: 

$$H =1.51 \cdot {5.5}/{6.5}\approx 1.3\,\, {\rm bit/Buchstabe}\hspace{0.05 cm}.$$

Eine weitere Entropieabschätzung von Küpfmüller

Der Vollständigkeit halber seien hier noch Küpfmüllers Überlegungen dargelegt, die ihn zum Endergebnis  $H = 1.51 \ \rm bit/Buchstabe$  führten.  Da es für die Statistik von Wortgruppen oder ganzen Sätzen keine Unterlagen gab, schätzte er den Entropiewert der deutschen Sprache wie folgt ab:

• Ein beliebiger zusammenhängender deutscher Text wird hinter einem bestimmten Wort abgedeckt.  Der vorhergehende Text wird gelesen, und der Leser soll versuchen, das folgende Wort aus dem Zusammenhang mit dem vorhergehenden Text zu ermitteln.
• Bei sehr vielen solcher Versuche ergibt die prozentuale Zahl der Treffer ein Maß für die Bindungen zwischen Wörtern und Sätzen.  Es zeigt sich, dass bei ein und derselben Textart (Romane, wissenschaftliche Schriften, usw.) ein und desselben Autors relativ schnell  (bei etwa hundert bis zweihundert Versuchen)  ein konstanter Endwert dieses Trefferverhältnisses erreicht wird.
• Das Trefferverhältnis hängt aber ziemlich stark von der Art des Textes ab.  Für verschiedene Texte ergeben sich Werte zwischen  $15\%$  und  $33\%$, mit dem Mittelwert bei  $22\%$.  Das heißt aber auch:   Im Durchschnitt können  $22\%$  der Wörter in einem deutschen Text aus dem Zusammenhang heraus ermittelt werden.
• Anders ausgedrückt:   Die Wörterzahl eines langen Textes kann mit dem Faktor  $0.78$  reduziert werden, ohne dass der Nachrichtengehalt des Textes eine signifikante Einbuße erfährt.  Ausgehend vom Bezugswert  $H_{5.5} = 2 \ \rm bit/Buchstabe$  $($siehe Punkt  (5)  im letzten Abschnitt$)$  für ein mittellanges Wort ergibt sich somit die Entropie  $H ≈ 0.78 · 2 = 1.56 \ \rm bit/Buchstabe$.
• Küpfmüller überprüfte diesen Wert mit einer vergleichbaren empirischen Untersuchung hinsichtlich der Silben und ermittelte so den Reduktionsfaktor  $0.54$  (hinsichtlich Silben).  Als Endergebnis nennt Küpfmüller  $H = 0.54 · H_3 ≈ 1.51 \ \rm bit/Buchstabe$, wobei  $H_3 ≈ 2.8 \ \rm bit/Buchstabe$  der Entropie einer Silbe mittlerer Länge  $($etwa drei Buchstaben, siehe Punkt  (3)  auf der letzten Seite$)$  entspricht.

Die vielleicht als sehr kritisch empfundenen Bemerkungen auf dieser und der vorherigen Seite sollen die Bedeutung von Küpfmüllers Entropieabschätzung nicht herabsetzen, eben so wenig wie Shannons Beiträge zur gleichen Thematik.

• Sie sollen nur auf die großen Schwierigkeiten hinweisen, die bei dieser Aufgabenstellung auftreten.
• Dies ist vielleicht auch der Grund dafür, dass sich seit den 1950er Jahren niemand mehr mit dieser Problematik intensiv beschäftigt hat.

Einige eigene Simulationsergebnisse

Die Angaben von Karl Küpfmüller hinsichtlich der Entropie der deutschen Sprache sollen nun mit einigen (sehr einfachen) Simulationsergebnissen verglichen werden, die vom Autor dieses Kapitels (Günter Söder) am Lehrstuhl für Nachrichtentechnik der Technischen Universität München im Rahmen eines Praktikums erarbeitet wurden.  Die Resultate basieren auf

• dem Windows-Programm  WDIT  ⇒  der Link verweist auf die ZIP-Version des Programms;
• der zugehörigen Praktikumsanleitung  Wertdiskrete Informationstheorie   ⇒   der Link verweist auf die PDF-Version;
• der deutschen Bibel im ASCII–Format mit  $N \approx 4.37 \cdot 10^6$  Zeichen. Dies entspricht einem Buch mit  $1300$  Seiten bei  $42$  Zeilen pro Seite und  $80$  Zeichen pro Zeile.

Der Symbolumfang wurde auf  $M = 33$  reduziert und umfasst die Zeichen a,  b,  c,  ... ,  x,  y,  z,  ä,  ö,  ü,  ß,  $\rm LZ$,  $\rm ZI$,  $\rm IP$.  Nicht unterschieden wurde bei unserer Analyse zwischen Groß– und Kleinbuchstaben.

Gegenüber Küpfmüllers Analyse wurden hier also noch zusätzlich berücksichtigt:

• die deutschen Umlaute  ä,  ö,  ü  und  ß, die etwa  $1.2\%$  des Bibeltextes ausmachen,
• die Klasse  $\rm IP$  (Interpunktion) mit ca.  $3\%$,
• die Klasse  $\rm ZI$  (Ziffer) mit ca.  $1.3\%$  wegen der Vers–Nummerierung innerhalb der Bibel,
• das Leerzeichen  $\rm (LZ)$  als das häufigste Zeichen  $(17.8\%)$, noch vor dem „e”  $(12.8\%)$.

Die nachfolgende Tabelle fasst die Ergebnisse zusammen.  $N$  bezeichnet die jeweils analysierte Dateigröße in Schriftzeichen (Byte).  Der Entscheidungsgehalt  $H_0$  sowie die Entropienäherungen  $H_1$,  $H_2$  und  $H_3$  wurden jeweils aus  $N$  Schriftzeichen ermittelt und sind jeweils in „bit/Schriftzeichen” angegeben.

Entropiewerte (in bit/Schriftzeichen) der deutschen Bibel

• Betrachten Sie diese Ergebnisse bitte nicht als wissenschaftliche Untersuchung.
• Es ist nur der Versuch, Studierenden die behandelte Thematik in einem Praktikum näher zu bringen.
• Grundlage dieser Untersuchung war die Bibel, da uns sowohl deren deutsche als auch die englische Fassung im geeigneten ASCII–Format zur Verfügung stand.

Die Ergebnisse obiger Tabelle lassen sich wie folgt zusammenfassen:

• In allen Zeilen nehmen die Entropienäherungen  $H_k$  mit wachsendem  $k$  monoton ab.  Der Abfall verläuft konvex, das heißt, es ist  $H_1 - H_2 > H_2 - H_3$.  Die Extrapolation des Endwertes  $(k \to \infty)$  ist aus den jeweils ermittelten drei Entropienäherungen nicht (oder nur äußerst vage) möglich.
• Verzichtet man auf die Auswertung der Ziffern  $(\rm ZI$, Zeile 2   ⇒   $M = 32)$  und zusätzlich auf die Auswertung der Interpunktionszeichen  $(\rm IP$, Zeile 3   ⇒   $M = 31)$, so nehmen die Entropienäherungen  $H_1$  $($um  $0.114)$,  $H_2$  $($um  $0.063)$  und  $H_3$  $($um  $0.038)$  ab.  Auf den Endwert  $H$  als dem Grenzwert von  $H_k$  für  $k \to \infty$  wirkt sich der Verzicht auf Ziffern und Interpunktion voraussichtlich kaum aus.
• Lässt man bei der Auswertung noch das Leerzeichen  $(\rm LZ$, Zeile 4   ⇒   $M = 30)$  außer Betracht, so ergibt sich nahezu die gleiche Konstellation wie von Küpfmüller ursprünglich betrachtet. Der einzige Unterschied sind die eher seltenen deutschen Sonderzeichen ä,  ö,  ü  und  ß.
• Der in der letzten Zeile angegebene  $H_1$–Wert  $(4.132)$  stimmt mit dem von Küpfmüller ermittelten Wert  $H_1 ≈ 4.1$  sehr gut überein.  Hinsichtlich der  $H_3$–Werte gibt es aber deutliche Unterschiede:   Unsere Analyse ergibt  $H_3 ≈ 3.4$, während Küpfmüller  $H_3 ≈ 2.8$  nennt (alle Angaben in bit/Buchstabe).
• Aus der Auftrittshäufigkeit des Leerzeichens  $(17.8\%)$  ergibt sich hier eine mittlere Wortlänge von  $1/0.178 - 1 ≈ 4.6$, ein kleinerer Wert als von Küpfmüller  ($5.5$)  angegeben.  Die Diskrepanz lässt sich zum Teil mit unserer Analysedatei „Bibel” erklären (viele Leerzeichen aufgrund der Vers–Nummerierung).
• Interessant ist der Vergleich der Zeilen 3 und 4.  Berücksichtigt man das Leerzeichen, so wird zwar  $H_0$  von  $\log_2 \ (30) \approx 4.907$  auf  $\log_2 \ (31) \approx 4.954$  vergrößert, aber man verringert dadurch  $H_1$  $($um den Faktor  $0.98)$,  $H_2$  $($um  $0.96)$  und  $H_3$  $($um  $0.93)$. Küpfmüller hat diesen Faktor intuitiv mit  $85\%$  berücksichtigt.

Obwohl wir diese eigene Recherche als eher unbedeutend erachten, so glauben wir doch, dass für heutige Texte die von Shannon angegebenen  $1.0 \ \rm bit/Buchstabe$  für die englische Sprache und auch Küpfmüllers  $1.3 \ \rm bit/Buchstabe$  für die deutsche Sprache etwas zu niedrig sind, unter Anderem, weil

• der Symbolumfang heute größer ist, als von Shannon und Küpfmüller in den 1950er Jahren berücksichtigt; zum Beispiel gilt für den ASCII–Zeichensatz  $M = 256$,
• die vielfachen Formatierungsmöglichkeiten (Unterstreichungen, Fett- und Kursivschrift, Einrückungen, Farben) den Informationsgehalt eines Dokuments weiter erhöhen.

Synthetisch erzeugte Texte

In der Grafik sind künstlich erzeugte deutsche und englische Texte angegeben, die aus  [Küpf54]  entnommen sind.  Der zugrundeliegende Symbolumfang ist  $M = 27$,  das heißt, berücksichtigt sind alle Buchstaben  (auch bei „Deutsch” ohne Umlaute und ß)  sowie das Leerzeichen.

Künstlich erzeugte deutsche und englische Texte

• Die  „Buchstabennäherung nullter Ordnung”  geht jeweils von gleichwahrscheinlichen Zeichen aus.  Es gibt deshalb keinen Unterschied zwischen Deutsch (rot) und Englisch (blau).

• Die  „erste Buchstabennäherung”  berücksichtigt bereits die unterschiedlichen Häufigkeiten, die Näherungen höherer Ordnung auch die vorangegangenen Zeichen.

• Bei der  „Synthese 4. Ordnung”  erkennt man schon sinnhafte Worte.  Hier hängt die Wahrscheinlichkeit für einen neuen Buchstaben von den drei letzten ausgewählten Zeichen ab.

• Die  „Wortnäherung erster Ordnung”  synthetisiert Sätze gemäß den Wortwahrscheinlichkeiten. Die  „Wortnäherung zweiter Ordnung”  berücksichtigt auch das vorherige Wort.

Weitere Information zur synthetischen Erzeugung von deutschen und englischen Texten finden Sie in der  Aufgabe 1.8.

Aufgaben zum Kapitel

Aufgabe 1.7: Entropie natürlicher Texte

Aufgabe 1.8: Synthetisch erzeugte Texte