View source for Information Theory/Natural Discrete Sources

 
{{Header
|Untermenü=Entropie wertdiskreter Nachrichtenquellen
|Vorherige Seite=Nachrichtenquellen mit Gedächtnis
|Nächste Seite=Allgemeine Beschreibung
}}

==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 Unicode–Charts.


Theoretisch könnte man auch hier die Entropie entsprechend der Vorgehensweise in [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Verallgemeinerung_auf_k.E2.80.93Tupel_und_Grenz.C3.BCbergang|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 = 65536$ 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 ergibt sich zu $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.000 Seiten.
*Bei einem natürlichen Text reichen die statistischen Bindungen aber sehr viel weiter als 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}$ ≈ $10^{240}$ Häufigkeiten und für die gesicherte Statistik nochmals um den Faktor 100 mehr Zeichen.


Eine berechtigte Frage ist deshalb: Wie hat [https://de.wikipedia.org/wiki/Karl_K%C3%BCpfm%C3%BCller Karl Küpfmüller] im Jahre 1954 die Entropie der deutschen Sprache ermittelt, und vor ihm schon [https://de.wikipedia.org/wiki/Claude_Shannon 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üp54] &nbsp; &rArr; &nbsp; [[Informationstheorie/Natürliche_wertdiskrete_Nachrichtenquellen#Quellenverzeichnis|Quellenverzeichnis]]<ref> [Küp54] Küpfmüller, K.: ''Die Entropie der deutschen Sprache''. Fernmeldetechnische Zeitung 7, 1954, S. 265-272.</ref>  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$. Seine Abschätzung basiert auf den folgenden Überlegungen:


:1.) &nbsp; 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.) &nbsp; Hinsichtlich der '''Silbenhäufigkeit''' wertet Küpfmüller das von F. W. Kaeding herausgegebene „Häufigkeitswörterbuch der deutschen Sprache” aus. Er unterscheidet zwischen Stammsilben, Vorsilben und Endsilben. Er kommt so auf den 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 Ende eines Wortes „en” mit 30% auf.
:*Der Rest von 14% verteilt sich auf bisher nicht erfasste Silben. Küpfmüller nimmt dazu an, dass es davon 4.000 gibt und diese gleichverteilt sind. Er setzt dafür $H_{\text{Rest}} ≈ 2 \ \rm bit/Silbe$ an.


:3.) &nbsp; Für die durchschnittliche Buchstabenzahl je Silbe ermittelte Küpfmüller den Wert 3.03. Daraus schloss er auf die '''dritte Entropienäherung''' hinsichtlich der Buchstaben: &nbsp; $H_3 \approx {8.6}/{3.03}\approx 2.8\,\, {\rm bit/Buchstabe}\hspace{0.05 cm}.$

:Küpfmüllers Abschätzung der Entropienäherung $H_3$ basierte vor allem auf den Silbenhäufigkeiten 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:

:4.) &nbsp; Die 322 häufigsten Wörter liefern einen Entropiebeitrag von $4.5 \ \rm bit/Wort$. Die Beiträge der restlichen 40.000 Wörter wurden geschätzt, wobei 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.) &nbsp; Die Auszählung ergab im Mittel 5.5 Buchstaben pro Wort. Analog zu Punkt (3) wurde so die Entropienäherung für $k = 5.5$ angenähert. Küpfmüller gibt hierfür den Wert $H_{5.5} \approx {11}/{5.5}\approx 2\,\, {\rm bit/Buchstabe}\hspace{0.05 cm}.$ Natürlich kann $k$ gemäß [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Verallgemeinerung_auf_k.E2.80.93Tupel_und_Grenz.C3.BCbergang|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.

[[File:P_ID2303__Inf_T_1_3_S2.png|right|Näherungswerte der Entropie der deutschen Sprache nach Küpfmüller]]
:6.) &nbsp; Man kann nun versuchen, aus diesen drei Punkten 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   [[Informationstheorie/Natürliche_wertdiskrete_Nachrichtenquellen#Quellenverzeichnis|Küpfmüllerschen Originalarbeit [Küp54]]] 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 LNTwww–Autors.  Diese und die braunen Pfeile sollen eigentlich nur zeigen, dass eine solche Extrapolation (vorsichtig formuliert) etwas vage ist.

:7.) &nbsp; 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.) &nbsp; 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 100 bis 200 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 Zahl der Wörter 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 der Silben und ermittelte 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 (≈ 3 Buchstaben, siehe Punkt (3) auf der letzten Seite) entspricht.


Die vielleicht als zu kritisch empfundenen Bemerkungen auf dieser Seite sollen die Bedeutung von Küpfmüllers Entropieabschätzung nicht herabsetzen, eben so wenig wie Shannon's 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 [http://en.lntwww.de/downloads/Sonstiges/Programme/WDIT.zip WDIT] &nbsp;&rArr;&nbsp; der Link verweist auf die ZIP-Version des Programms; 
*der zugehörigen Praktikumsanleitung [http://en.lntwww.de/downloads/Sonstiges/Texte/Wertdiskrete_Informationstheorie.pdf Wertdiskrete Informationstheorie]  &nbsp;&rArr;&nbsp; der Link verweist auf die PDF-Version;
*einer ASCII–Version der deutschen Bibel mit fast $N = 4.37 \cdot 10^6$  Schriftzeichen, was bei 42 Zeilen pro Seite und 80 Zeichen pro Zeile etwa einem Buch mit 1300 Seiten entsprechen würde. Der Symbolumfang wurde auf $M = 33$ reduzier und umfasst die Zeichen
:'''a''',  '''b''',  '''c''',  ... ,  '''x''',  '''y''',  '''z''',  '''ä''',  '''ö''',  '''ü''', '''ß''',  '''LZ''',  '''ZI''',  '''IP'''.
Nicht unterschieden wurde bei unserer Analyse zwischen Groß– und Kleinbuchstaben. Gegenüber Küpfmüllers Analyse wurden hier noch zusätzlich berücksichtigt:
*die deutschen Umlaute '''ä''',  '''ö''',  '''ü''' und '''ß''', die etwa 1.2% des Bibeltextes ausmachen,
*die Klasse '''IP''' (Interpunktion) mit ca. 3%,
*die Klasse '''ZI''' (Ziffer) mit ca. 1.3% in Folge der Vers–Nummerierung innerhalb der Bibel,
*das Leerzeichen ('''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 &bdquo;bit/Schriftzeichen&rdquo; angegeben. 

[[File:P_ID2267__Inf_T_1_3_S3.png|Entropiewerte (in bit/Schriftzeichen) der deutschen Bibel]]

''Hinweis'': Betrachten Sie diese Ergebnisse bitte nicht als Teil einer wissenschaftlichen Untersuchung, sondern nur als den Versuch, Studierenden die in diesem Kapitel behandelte Thematik in einem Praktikum näher zu bringen. Als Grundlage dieser Untersuchung wurde von der Bibel ausgegangen, da uns sowohl deren deutsche als auch die englische Fassung im geeigneten ASCII–Format zur Verfügung gestellt wurden.	 

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 sehr vage) möglich.
*Verzichtet man auf die Auswertung der Ziffern ('''ZI''', Zeile 2 ⇒ $M = 32$) und zusätzlich auf die Auswertung der Interpunktionszeichen ('''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 (LZ, Zeile 4 &rArr; $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 $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–Nummern).
*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 unsere eigenen Recherchen als nicht so bedeutend ansehen, 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 Deutsch etwas zu niedrig sind, unter Anderem, weil
*der Symbolumfang deutlich größer ist, als von Shannon und Küpfmüller bei ihren Analysen berücksichtigt – beispielsweise 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 
[Küp54]<ref> Küpfmüller, K.: ''Die Entropie der deutschen Sprache''. Fernmeldetechnische Zeitung 7, 1954, S. 265-272.</ref>
[Küp54][1] 
<ref> Küpfmüller, K.: ''Die Entropie der deutschen Sprache''. Fernmeldetechnische Zeitung 7, 1954, S. 265-272.</ref> entnommen wurden. Der zugrundeliegende Symbolumfang ist M = 27, das heißt, berücksichtigt sind alle Buchstaben (ohne Umlaute und „ß”) sowie das Leerzeichen.
*Die '''Buchstabennäherung nullter Ordnun'''g geht von gleichwahrscheinlichen Zeichen aus. Hier ist kein Unterschied zwischen Deutsch (rot) und Englisch (blau) festzustellen.
*Bei der '''ersten Buchstabennäherung''' werden bereits die unterschiedlichen Häufigkeiten berücksichtigt, bei den Näherungen höherer Ordnung auch die vorangegangenen Zeichen.
*Bei einer '''Synthese 4. Ordnung'''  ⇒  die Wahrscheinlichkeit für einen neuen Buchstaben hängt von den drei zuletzt ausgewählten Zeichen ab – erkennt man bereits sinnhafte Worte.
*Die Wortnäherung '''1. Ordnung''' synthetisiert Sätze gemäß den Wortwahrscheinlichkeiten, die Näherung '''2. Ordnung''' berücksichtigt zusätzlich noch das vorherige Wort.

[[File:P_ID2269__Inf_T_1_3_S4.png|Künstlich erzeugte deutsche und englische Texte]]

Weitere Information zur synthetischen Erzeugung von deutschen und englischen Texten finden Sie in [[Aufgaben:1.8_Synthetisch_erzeugte_Texte|Aufgabe A1.8]].

 	 
== Aufgaben zu Kapitel 1.3  ==	 

==Quellenverzeichnis==
</references>



{{Display}}