Aufgaben:Aufgabe 1.7: Entropie natürlicher Texte: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 40: Zeile 40:
 
{Von welchem Symbolumfang $M$ ging Küpfmüller aus?
 
{Von welchem Symbolumfang $M$ ging Küpfmüller aus?
 
|type="{}"}
 
|type="{}"}
$M \ = $ { 26 }
+
$M \ = \ $ { 26 }
  
  
 
{Welche relative Redundanz $r$ ergibt sich aus Küpfmüllers Entropiewert?
 
{Welche relative Redundanz $r$ ergibt sich aus Küpfmüllers Entropiewert?
 
|type="{}"}
 
|type="{}"}
$r \ = $ { 72.3 3% } $\ \%$
+
$r \ = \ $ { 72.3 3% } $\ \%$
  
  
Zeile 66: Zeile 66:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>1.</b>&nbsp;&nbsp;Der Symbolumfang bei Küpfmüllers Untersuchungen war <u><i>M</i> = 26</u>, 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,
+
'''(1)'''&nbsp; 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 &bdquo;ä&rdquo;, &bdquo;ö&rdquo;, &bdquo;ü&rdquo; und &bdquo;ß&rdquo; vorkommen,
 +
* zwischen Klein&ndash; und Großschreibung unterschieden wird,
 +
* und zudem noch Ziffern und Interpunktionszeichen hinzukommen.
  
:* da hier auch die typisch deutschen Zeichen &bdquo;ä&rdquo;, &bdquo;ö&rdquo;, &bdquo;ü&rdquo; und &bdquo;ß&rdquo; vorkommen,
 
  
:* zwischen Klein&ndash; und Großschreibung unterschieden wird,
+
'''(2)'''&nbsp; Mit dem Entscheidungsgehalt $H_0 = \log_2 \ (31) \approx 4.7 \ \rm bit/Zeichen$ und der Entropie $H = 1.3\ \rm bit/Zeichen $ erhält man für die relative Redundanz:
 
 
:* und zudem noch Ziffern und Interpunktionszeichen hinzukommen.
 
 
 
:<b>2.</b>&nbsp;&nbsp;Mit dem Entscheidungsgehalt <i>H</i><sub>0</sub> = log<sub>2</sub> (31) &asymp; 4.7 und der Entropie <i>H</i> = 1.3 (jeweils mit der Einheit bit/Zeichen) erhält man für die relative Redundanz:
 
 
:$$r = \frac{H_0 - H}{H_0}= \frac{4.7 - 1.3}{4.7}\underline {\hspace{0.1cm}\approx 72.3\,\%}\hspace{0.05cm}.$$
 
:$$r = \frac{H_0 - H}{H_0}= \frac{4.7 - 1.3}{4.7}\underline {\hspace{0.1cm}\approx 72.3\,\%}\hspace{0.05cm}.$$
  
:<b>3.</b>&nbsp;&nbsp;Richtig ist nur der <u>erste Lösungsvorschlag</u>. Laut Küpfmüller benötigt man nur 1.3 Binärzeichen pro Quellenzeichen. Bei einer Datei der Länge <i>N</i> würden also 1.3 &middot; <i>N</i> Binärsymbole ausreichen, allerdings nur dann, wenn
+
'''(3)'''&nbsp; Richtig ist nur der <u>erste Lösungsvorschlag</u>:
 
+
*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.
:* die Quellensymbolfolge unendlich lang ist (<i>N</i> &#8594; &#8734;), und
+
*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 sind.
 
+
*Ein solcher Text ist nie unendlich lang, noch wurde er vorher optimal codiert.
:* diese bestmöglich codiert ist.
 
  
:Dagegen besagt Küpfmüllers Ergebnis und die in der Teilaufgabe (b) errechnete relative Redundanz von mehr als 70% nicht, dass ein Leser den Text noch verstehen kann, wenn 70% der Zeichen ausgelöscht sind. Ein solcher Text
 
  
:* ist nie unendlich lang,
+
'''(4)'''&nbsp; Richtig ist <u>Aussage 2</u>:
 +
*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 es Fehler gibt.
 +
*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..
  
:* noch wurde er vorher optimal codiert.
 
  
:<b>4.</b>&nbsp;&nbsp;Richtig ist <u>Aussage 2</u>. 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 es Fehler gibt. Wenn Sie es weiter versuchen wollen: Für den unteren Block wurde genau die gleiche Zeichenfehlerfolge wie für Block 2 verwendet, das heißt, Fehler gibt es bei den Zeichen 6, 35, 37, usw..
+
Abschließend wird noch der Originaltext angegeben, der auf der Angabenseite nur durch Auslöschungen (<i>Erasures</i>) oder echte Zeichenfehler verfälscht wiedergegeben ist.
  
:Abschließend soll noch der Originaltext angegeben werden, der auf der Angabenseite nur durch Auslöschungen (<i>Erasures</i>) oder echte Zeichenfehler verfälscht wiedergegeben ist.
+
[[Datei:P_ID2318__Inf_A_1_7d.png|Originaltexte]]
[[Datei:P_ID2318__Inf_A_1_7d.png|center|]]
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Version vom 3. Mai 2017, 10:30 Uhr

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 dagegen von $M = 267$ Buchstaben aus, ebenfalls ohne zwischen Groß– und Kleinschreibung zu unterscheiden.


Mit dieser Aufgabe soll gezeigt werden, wie sich

  • Auslöschungen (Erasures) ⇒ man kennt den Ort eines Fehlers,
  • Zeichenfehler (Errors) ⇒ es ist nicht offensichtlich, 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 dieser 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öschwahrscheinlichkeiten 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:

$$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= 100000$ Zeichen könnte man mit $130000$ 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

(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 \ (31) \approx 4.7 \ \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.7 - 1.3}{4.7}\underline {\hspace{0.1cm}\approx 72.3\,\%}\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 sind.
  • Ein solcher Text ist nie unendlich lang, noch wurde er vorher optimal codiert.


(4)  Richtig ist 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 es Fehler gibt.
  • 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 noch der Originaltext angegeben, der auf der Angabenseite nur durch Auslöschungen (Erasures) oder echte Zeichenfehler verfälscht wiedergegeben ist.

Originaltexte