Aufgabe 1.7: Entropie natürlicher Texte
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
- 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
Musterlösung
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.
Abschließend wird der Originaltext angegeben, der auf der Angabenseite nur durch Auslöschungen (Erasures) oder echte Zeichenfehler verfälscht wiedergegeben ist.
