Difference between revisions of "Aufgaben:Exercise 1.8: Synthetically Generated Texts"
From LNTwww
m (Text replacement - "Category:Aufgaben zu Informationstheorie" to "Category:Information Theory: Exercises") |
m (Text replacement - "„" to """) |
||
| Line 9: | Line 9: | ||
Mit diesem Programm | Mit diesem Programm | ||
| − | *kann man aus einer gegebenen Textdatei | + | *kann man aus einer gegebenen Textdatei "VORLAGE” die Häufigkeiten von Buchstabentripeln wie "aaa”, "aab”, ... , "xyz”, ... ermitteln und in einer Hilfsdatei abspeichern, |
| − | * danach eine Datei | + | * danach eine Datei "SYNTHESE” erzeugen, wobei das neue Zeichen aus den beiden letzten Zeichen und den abgespeicherten Tripel–Häufigkeiten generiert wird. |
| Line 20: | Line 20: | ||
Nicht angegeben wird, welche Datei von welcher Vorlage stammt. Dies zu ermitteln ist Ihre erste Aufgabe. | Nicht angegeben wird, welche Datei von welcher Vorlage stammt. Dies zu ermitteln ist Ihre erste Aufgabe. | ||
| − | Die beiden Vorlagen basieren auf dem natürlichen Alphabet $(26$ Buchstaben$)$ und dem Leerzeichen ( | + | Die beiden Vorlagen basieren auf dem natürlichen Alphabet $(26$ Buchstaben$)$ und dem Leerzeichen ("LZ”) ⇒ $M = 27$. Bei der deutschen Bibel wurden die Umlaute ersetzt, zum Beispiel "ä” ⇒ "ae”. |
Die $\text{Datei 1}$ weist folgende Eigenschaften auf: | Die $\text{Datei 1}$ weist folgende Eigenschaften auf: | ||
| − | * Die häufigsten Zeichen sind | + | * Die häufigsten Zeichen sind "LZ” mit $19.8\%$, gefolgt von "e” mit $10.2\%$ und "a” mit $8.5\%$. |
| − | * Nach | + | * Nach "LZ” (Leerzeichen) tritt "t” mit $17.8\%$ am häufigsten auf. |
| − | * Vor einem Leerzeichen ist | + | * Vor einem Leerzeichen ist "d” am wahrscheinlichsten. |
| − | * Die Entropienäherungen jeweils mit der Einheit | + | * Die Entropienäherungen jeweils mit der Einheit "bit/Zeichen” wurden wie folgt ermittelt: |
:$$H_0 = 4.76\hspace{0.05cm},\hspace{0.2cm} | :$$H_0 = 4.76\hspace{0.05cm},\hspace{0.2cm} | ||
H_1 = 4.00\hspace{0.05cm},\hspace{0.2cm} | H_1 = 4.00\hspace{0.05cm},\hspace{0.2cm} | ||
| Line 35: | Line 35: | ||
Dagegen ergibt die Analyse von $\text{Datei 2}$: | Dagegen ergibt die Analyse von $\text{Datei 2}$: | ||
| − | * Die häufigsten Zeichen sind | + | * Die häufigsten Zeichen sind "LZ” mit $17.6\%$ gefolgt von "e” mit $14.4\%$ und "n” mit $8.9\%$. |
| − | * Nach | + | * Nach "LZ” ist "d” am wahrscheinlichsten $(15.1\%)$ gefolgt von "s” mit $10.8\%$. |
| − | * Nach | + | * Nach "LZ” und "d” sind die Vokale "e” $(48.3\%)$, "i” $(23\%)$ und "a” $(20.2\%)$ dominant. |
* Die Entropienäherungen unterscheiden sich nur geringfügig von denen der $\text{Datei 1}$. | * Die Entropienäherungen unterscheiden sich nur geringfügig von denen der $\text{Datei 1}$. | ||
* Für größere $k$–Werte sind diese etwas größer, zum Beispiel $H_3 = 3.17$ statt $H_3 = 3.11$. | * Für größere $k$–Werte sind diese etwas größer, zum Beispiel $H_3 = 3.17$ statt $H_3 = 3.11$. | ||
| Line 64: | Line 64: | ||
{Vergleichen Sie die mittleren Wortlängen von $\text{Datei 1}$ und $\text{Datei 2}$ . | {Vergleichen Sie die mittleren Wortlängen von $\text{Datei 1}$ und $\text{Datei 2}$ . | ||
|type="[]"} | |type="[]"} | ||
| − | - Die Wörter der | + | - Die Wörter der "englischen” Datei sind im Mittel länger. |
| − | + Die Wörter der | + | + Die Wörter der "deutschen” Datei sind im Mittel länger. |
{Welche Aussagen gelten für die Entropienäherungen? | {Welche Aussagen gelten für die Entropienäherungen? | ||
|type="[]"} | |type="[]"} | ||
| − | + | + | + "VORLAGE” und "SYNTHESE” liefern ein nahezu gleiches $H_1$. |
| − | + | + | + "VORLAGE” und "SYNTHESE” liefern ein nahezu gleiches $H_2$. |
| − | + | + | + "VORLAGE” und "SYNTHESE” liefern ein nahezu gleiches $H_3$. |
| − | - | + | - "VORLAGE” und "SYNTHESE” liefern ein nahezu gleiches $H_4$. |
| − | {Welche Aussagen treffen für den | + | {Welche Aussagen treffen für den "englischen” Text zu? |
|type="[]"} | |type="[]"} | ||
| − | + Die meisten Wörter beginnen mit | + | + Die meisten Wörter beginnen mit "t”. |
| − | - Die meisten Wörter enden mit | + | - Die meisten Wörter enden mit "t”. |
{Welche Aussagen könnten für deutsche Texte gelten? | {Welche Aussagen könnten für deutsche Texte gelten? | ||
|type="[]"} | |type="[]"} | ||
| − | + Nach | + | + Nach "de” ist "r” am wahrscheinlichsten. |
| − | + Nach | + | + Nach "da” ist "s” am wahrscheinlichsten. |
| − | + Nach | + | + Nach "di” ist "e” am wahrscheinlichsten. |
| Line 111: | Line 111: | ||
'''(3)''' Richtig sind <u>die drei ersten Aussagen</u>, nicht jedoch die Aussage '''(4)''': | '''(3)''' Richtig sind <u>die drei ersten Aussagen</u>, nicht jedoch die Aussage '''(4)''': | ||
| − | *Zur Bestimmung der Entropienäherung $H_k$ müssen $k$–Tupel ausgewertet werden, zum Beispiel für $k = 3$ die Tripel | + | *Zur Bestimmung der Entropienäherung $H_k$ müssen $k$–Tupel ausgewertet werden, zum Beispiel für $k = 3$ die Tripel "aaa”, "aab”, .... |
| − | *Nach der Generierungsvorschrift | + | *Nach der Generierungsvorschrift "Neues Zeichen hängt von den beiden Vorgängern ab” werden $H_1$, $H_2$ und $H_3$ von "VORLAGE” und "SYNTHESE” übereinstimmen, allerdings auf Grund der endlichen Dateilänge nur näherungsweise. |
*Dagegen unterscheiden sich die $H_4$–Näherungen stärker, da bei der Generierung der dritte Vorgänger unberücksichtigt bleibt. | *Dagegen unterscheiden sich die $H_4$–Näherungen stärker, da bei der Generierung der dritte Vorgänger unberücksichtigt bleibt. | ||
| − | *Bekannt ist nur, dass auch bezüglich | + | *Bekannt ist nur, dass auch bezüglich "SYNTHESE” $H_4 < H_3$ gelten muss. |
'''(4)''' Richtig ist hier nur die <u>Aussage 1</u>: | '''(4)''' Richtig ist hier nur die <u>Aussage 1</u>: | ||
| − | *Nach einem Leerzeichen (Wortanfang) folgt | + | *Nach einem Leerzeichen (Wortanfang) folgt "t” mit $17.8\%$, während am Wortende (vor einem Leerzeichen) "t” nur mit der Häufigkeit $<8.3\%$ auftritt. |
| − | *Insgesamt beträgt die Auftrittswahrscheinlichkeit von | + | *Insgesamt beträgt die Auftrittswahrscheinlichkeit von "t” über alle Positionen im Wort gemittelt $7.4\%$. |
| − | *Als dritter Buchstaben nach Leerzeichen und | + | *Als dritter Buchstaben nach Leerzeichen und "t” folgt "h” mit fast $82\%$ und nach "th” ist "e” mit $62%$ am wahrscheinlichsten. |
| − | *Das lässt daraus schließen, dass | + | *Das lässt daraus schließen, dass "the” in einem englischen Text überdurchschnittlich oft vorkommt und damit auch in der synthetischen $\text{Datei 1}$, wie folgende Grafik zeigt. Aber nicht bei allen Markierungen tritt "the” isoliert auf ⇒ direkt vorher und nachher ein Leerzeichen. |
| − | [[File:Inf_A_1_8d_vers2.png|right|frame|Auftreten von | + | [[File:Inf_A_1_8d_vers2.png|right|frame|Auftreten von "...the...” im englischen Text]] |
<br clear=all> | <br clear=all> | ||
'''(5)''' <u>Alle Aussagen</u> treffen zu: | '''(5)''' <u>Alle Aussagen</u> treffen zu: | ||
| − | *Nach | + | *Nach "de” ist tatsächlich "r” am wahrscheinlichsten $(32.8\%)$, gefolgt von "n” $(28.5\%)$, "s” $(9.3\%)$ und "m” $(9.7\%)$. |
| − | *Dafür verantwortlich könnten | + | *Dafür verantwortlich könnten "der”, "den”, "des” und "dem” sein. |
| − | [[File:Inf_A_1_8e_vers2.png|right|frame|Auftreten von | + | [[File:Inf_A_1_8e_vers2.png|right|frame|Auftreten von "der”, "die” und "das” im deutschen Text]] |
| − | * Nach | + | * Nach "da” folgt "s” mit größter Wahrscheinlichkeit: $48.2\%$. |
| − | * Nach | + | * Nach "di” folgt "e” mit größter Wahrscheinlichkeit: $78.7\%$. |
| − | Die Grafik zeigt die $\text{Datei 2}$ mit allen | + | Die Grafik zeigt die $\text{Datei 2}$ mit allen "der”, "die” und "das”. |
Revision as of 16:21, 28 May 2021
Zwei synthetisch erzeugte Textdateien
Der frühere Praktikumsversuch Wertdiskrete Informationstheorie von Günter Söder am Lehrstuhl für Nachrichtentechnik der TU München verwendet das Windows-Programm WDIT. Die hier angegebenen Links führen zur PDF-Version der Praktikumsanleitung bzw. zur ZIP-Version des Programms.
Mit diesem Programm
- kann man aus einer gegebenen Textdatei "VORLAGE” die Häufigkeiten von Buchstabentripeln wie "aaa”, "aab”, ... , "xyz”, ... ermitteln und in einer Hilfsdatei abspeichern,
- danach eine Datei "SYNTHESE” erzeugen, wobei das neue Zeichen aus den beiden letzten Zeichen und den abgespeicherten Tripel–Häufigkeiten generiert wird.
Ausgehend von der deutschen und der englischen Bibelübersetzung haben wir so zwei Dateien synthetisiert, die in der Grafik angegeben sind:
- die $\text{Datei 1}$ (rote Umrandung),
- die $\text{Datei 2}$ (grüne Umrandung)
Nicht angegeben wird, welche Datei von welcher Vorlage stammt. Dies zu ermitteln ist Ihre erste Aufgabe.
Die beiden Vorlagen basieren auf dem natürlichen Alphabet $(26$ Buchstaben$)$ und dem Leerzeichen ("LZ”) ⇒ $M = 27$. Bei der deutschen Bibel wurden die Umlaute ersetzt, zum Beispiel "ä” ⇒ "ae”.
Die $\text{Datei 1}$ weist folgende Eigenschaften auf:
- Die häufigsten Zeichen sind "LZ” mit $19.8\%$, gefolgt von "e” mit $10.2\%$ und "a” mit $8.5\%$.
- Nach "LZ” (Leerzeichen) tritt "t” mit $17.8\%$ am häufigsten auf.
- Vor einem Leerzeichen ist "d” am wahrscheinlichsten.
- Die Entropienäherungen jeweils mit der Einheit "bit/Zeichen” wurden wie folgt ermittelt:
- $$H_0 = 4.76\hspace{0.05cm},\hspace{0.2cm} H_1 = 4.00\hspace{0.05cm},\hspace{0.2cm} H_2 = 3.54\hspace{0.05cm},\hspace{0.2cm} H_3 = 3.11\hspace{0.05cm},\hspace{0.2cm} H_4 = 2.81\hspace{0.05cm}. $$
Dagegen ergibt die Analyse von $\text{Datei 2}$:
- Die häufigsten Zeichen sind "LZ” mit $17.6\%$ gefolgt von "e” mit $14.4\%$ und "n” mit $8.9\%$.
- Nach "LZ” ist "d” am wahrscheinlichsten $(15.1\%)$ gefolgt von "s” mit $10.8\%$.
- Nach "LZ” und "d” sind die Vokale "e” $(48.3\%)$, "i” $(23\%)$ und "a” $(20.2\%)$ dominant.
- Die Entropienäherungen unterscheiden sich nur geringfügig von denen der $\text{Datei 1}$.
- Für größere $k$–Werte sind diese etwas größer, zum Beispiel $H_3 = 3.17$ statt $H_3 = 3.11$.
Hinweise:
- Die Aufgabe gehört zum Kapitel Natürliche wertdiskrete Nachrichtenquellen.
- Bezug genommen wird insbesondere auf die Seite Synthetisch erzeugte Texte.
Fragebogen
Musterlösung
(1) Richtig ist der Lösungsvorschlag 1.
- In der $\text{Datei 1}$ erkennt man viele englische Wörter, in der $\text{Datei 2}$ viele deutsche.
- Sinn ergibt keiner der beiden Texte.
(2) Richtig ist der Lösungsvorschlag 2. Die Abschätzungen von Shannon und Küpfmüller bestätigen unser Ergebnis:
- Die Wahrscheinlichkeit eines Leerzeichens beträgt bei der $\text{Datei 1}$ (Englisch) $19.8\%$.
- Also ist im Mittel jedes $1/0.198 = 5.05$–te Zeichen ein Leerzeichen.
- Die mittlere Wortlänge ergibt sich daraus zu
- $$L_{\rm M} = \frac{1}{0.198}-1 \approx 4.05\,{\rm Zeichen}\hspace{0.05cm}.$$
- Entsprechend gilt für die $\text{Datei 2}$ (Deutsch):
- $$L_{\rm M} = \frac{1}{0.176}-1 \approx 4.68\,{\rm Zeichen}\hspace{0.05cm}.$$
(3) Richtig sind die drei ersten Aussagen, nicht jedoch die Aussage (4):
- Zur Bestimmung der Entropienäherung $H_k$ müssen $k$–Tupel ausgewertet werden, zum Beispiel für $k = 3$ die Tripel "aaa”, "aab”, ....
- Nach der Generierungsvorschrift "Neues Zeichen hängt von den beiden Vorgängern ab” werden $H_1$, $H_2$ und $H_3$ von "VORLAGE” und "SYNTHESE” übereinstimmen, allerdings auf Grund der endlichen Dateilänge nur näherungsweise.
- Dagegen unterscheiden sich die $H_4$–Näherungen stärker, da bei der Generierung der dritte Vorgänger unberücksichtigt bleibt.
- Bekannt ist nur, dass auch bezüglich "SYNTHESE” $H_4 < H_3$ gelten muss.
(4) Richtig ist hier nur die Aussage 1:
- Nach einem Leerzeichen (Wortanfang) folgt "t” mit $17.8\%$, während am Wortende (vor einem Leerzeichen) "t” nur mit der Häufigkeit $<8.3\%$ auftritt.
- Insgesamt beträgt die Auftrittswahrscheinlichkeit von "t” über alle Positionen im Wort gemittelt $7.4\%$.
- Als dritter Buchstaben nach Leerzeichen und "t” folgt "h” mit fast $82\%$ und nach "th” ist "e” mit $62%$ am wahrscheinlichsten.
- Das lässt daraus schließen, dass "the” in einem englischen Text überdurchschnittlich oft vorkommt und damit auch in der synthetischen $\text{Datei 1}$, wie folgende Grafik zeigt. Aber nicht bei allen Markierungen tritt "the” isoliert auf ⇒ direkt vorher und nachher ein Leerzeichen.
Auftreten von "...the...” im englischen Text
(5) Alle Aussagen treffen zu:
- Nach "de” ist tatsächlich "r” am wahrscheinlichsten $(32.8\%)$, gefolgt von "n” $(28.5\%)$, "s” $(9.3\%)$ und "m” $(9.7\%)$.
- Dafür verantwortlich könnten "der”, "den”, "des” und "dem” sein.
Auftreten von "der”, "die” und "das” im deutschen Text
- Nach "da” folgt "s” mit größter Wahrscheinlichkeit: $48.2\%$.
- Nach "di” folgt "e” mit größter Wahrscheinlichkeit: $78.7\%$.
Die Grafik zeigt die $\text{Datei 2}$ mit allen "der”, "die” und "das”.
