Aufgaben:Aufgabe 1.7: Entropie natürlicher Texte

• Zurück zum Buch

Text mit Auslöschungen bzw. Fehlern

Anfang der 1950er Jahre schätzte  Claude E. Shannon  die Entropie  $H$  der englischen Sprache mit einem bit pro Zeichen ab.  Kurze Zeit später kam  Karl Küpfmüller  bei einer empirischen Untersuchung der deutschen Sprache auf einen Entropiewert von  $H =1.3\ \rm bit/Zeichen$, also einen etwas größeren Wert.  Die Ergebnisse von Shannon und Küpfmüller beruhen dabei interessanter Weise auf zwei völlig unterschiedlichen Methoden.

Die differierenden Ergebnisse lassen sich eher nicht mit den geringen Differenzen hinsichtlich des Symbolumfangs  $M$  erklären:

• Shannon ging von  $26$  Buchstaben und dem Leerzeichen aus  ⇒  $M = 27$.
• Küpfmüller ging nur von  $M = 26$  Buchstaben aus  (also ohne Leerzeichen).

Beide machten keine Unterscheidung zwischen Groß– und Kleinschreibung.

Mit dieser Aufgabe soll gezeigt werden, wie sich

• Auslöschungen  („Erasures”)   ⇒   man kennt den Ort eines Fehlers, bzw.
• Zeichenfehler  („Errors”)   ⇒   es ist für den Leser nicht klar erkennbar, was falsch und was richtig ist,

auf die Verständlichkeit eines Textes auswirken.  Unser Text beinhaltet dabei auch die typisch deutschen Buchstaben „ä”,  „ö”,  „ü”  und  „ß”  sowie Ziffern und Interpunktion. Außerdem wird zwischen Groß– und Kleinschreibung unterschieden.

In der Abbildung ist ein Text, der von Küpfmüllers Vorgehensweise handelt, in sechs Blöcke der Länge zwischen  $N = 197$  bis  $N = 319$  aufgeteilt.  Beschrieben ist die Überprüfung seiner  ersten Analyse  auf völlig anderem Wege, die zum Ergebnis  $H =1.51\ \rm bit/Zeichen$  führte.

• In den oberen fünf Blöcken erkennt man „Erasures” mit verschiedenen Auslöschungswahrscheinlichkeiten zwischen  $10\%$  und  $50\%$.
• Im letzten Block sind „Zeichenfehler” mit  $20$–prozentiger Verfälschungswahrscheinlichkeit eingefügt.

Der Einfluss solcher Zeichenfehler auf die Lesbarkeit eines Textes soll in der Teilaufgabe  (4)  verglichen werden mit dem zweiten (rot umrandeten) Block, für den die Wahrscheinlichkeit eines Erasures ebenfalls  $20\%$  beträgt.

Hinweise:

• Die Aufgabe gehört zum Kapitel  Natürliche wertdiskrete Nachrichtenquellen.
• Bezug genommen wird insbesondere auf die beiden Seiten

Entropieabschätzung nach Küpfmüller,  sowie 

Eine weitere Entropieabschätzung von Küpfmüller.

• Für die  relative Redundanz  einer Folge gilt mit dem Entscheidungsgehalt  $H_0$  und der Entropie  $H$  gilt:

$$r = \frac{H_0 - H}{H_0}\hspace{0.05cm}.$$

Fragebogen

1

Von welchem Symbolumfang  $M$  ging Küpfmüller aus?

$M \ = \ $

2

Welche relative Redundanz  $r$  ergibt sich aus Küpfmüllers Entropiewert?

$r \ = \ $ $\ \%$

3

Wie lässt sich das Ergebnis der Teilaufgabe  (2)  interpretieren?  Gehen Sie jeweils von einer Textdatei mit  $M = 26$  unterschiedlichen Zeichen aus.

	Eine solche Textdatei hinreichender Länge  $(N \to \infty)$  könnte man mit  $1.3 \cdot N$  Binärsymbolen darstellen.
	Eine solche Textdatei mit  $N= 100\hspace{0.1cm}000$  Zeichen könnte man mit  $130\hspace{0.1cm}000$  Binärsymbolen darstellen.
	Ein Leser kann den Text auch dann noch verstehen (oder zumindest erahnen), wenn  $70\%$  der Zeichen ausgelöscht sind.

4

Was erschwert die Verständlichkeit eines Textes mehr?

	$20\%$  Auslöschungen („Erasures”),
	eine Zeichenfehlerwahrscheinlichkeit von  $20\%$.

Musterlösung

Musterlösung

(1)  Der Symbolumfang bei Küpfmüllers Untersuchungen war  $\underline{M = 26}$,  da er im Gegensatz zu Shannon das Leerzeichen zunächst nicht berücksichtigte.

Bei dem vorgegebenen deutschen Text dieser Aufgabe ist der Symbolumfang deutlich größer,

• da hier auch die typisch deutschen Zeichen „ä”,  „ö”,  „ü”  und  „ß”  vorkommen,
• zwischen Klein– und Großschreibung unterschieden wird,
• und zudem noch Ziffern und Interpunktionszeichen hinzukommen.

(2)  Mit dem Entscheidungsgehalt  $H_0 = \log_2 \ (26) \approx 4.67 \ \rm bit/Zeichen$  und der Entropie  $H = 1.3\ \rm bit/Zeichen $  erhält man für die relative Redundanz:

$$r = \frac{H_0 - H}{H_0}= \frac{4.67 - 1.3}{4.67}\underline {\hspace{0.1cm}\approx 72.2\,\%}\hspace{0.05cm}.$$

(3)  Richtig ist nur der erste Lösungsvorschlag:

• Laut Küpfmüller benötigt man nur  $1.3$  Binärzeichen pro Quellenzeichen.
• Bei einer Datei der Länge  $N$  würden also  $1.3 \cdot N$  Binärsymbole ausreichen, allerdings nur dann, wenn die Quellensymbolfolge unendlich lang ist  $(N \to \infty)$  und diese bestmöglich codiert wurde.
• Dagegen besagt Küpfmüllers Ergebnis und die in der Teilaufgabe  (2)  errechnete relative Redundanz von mehr als  $70\%$ nicht, dass ein Leser den Text noch verstehen kann, wenn  $70\%$  der Zeichen ausgelöscht wurden.
• Ein solcher Text ist weder unendlich lang, noch wurde er vorher optimal codiert.

(4)  Richtig ist die Aussage 2:

• Testen Sie es selbst:   Der zweite Block der Grafik auf der Angabenseite ist leichter zu entschlüsseln als der letzte Block, weil man weiß, wo Fehler sind.
• Wenn Sie es weiter versuchen wollen:   Für den unteren Block  (F)  wurde genau die gleiche Zeichenfehlerfolge wie für Block  (B)  verwendet, das heißt, Fehler gibt es bei den Zeichen  $6$,  $35$,  $37$,  usw.

Originaltexte

Abschließend wird der Originaltext angegeben, der auf der Angabenseite nur durch Auslöschungen (Erasures) oder echte Zeichenfehler verfälscht wiedergegeben ist.