Difference between revisions of "Aufgaben:Exercise 1.8: Synthetically Generated Texts"
From LNTwww
| Line 56: | Line 56: | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | { | + | {Which templates were used for the text synthesis shown here?? |
|type="()"} | |type="()"} | ||
| − | + Die $\text{ | + | + Die $\text{File 1}$ (red) is based on an English template. |
| − | - Die $\text{ | + | - Die $\text{File 1}$ (red) is based on a German template. |
| − | + | {Compare the mean word lengths of $\text{File 1}$ and $\text{File 2}$ . | |
| − | { | ||
|type="[]"} | |type="[]"} | ||
| − | - | + | - The words of the "English" file are longer on average. |
| − | + | + | + The words of the "German" file are longer on average. |
| − | { | + | {Which statements apply to the entropy approximations? |
|type="[]"} | |type="[]"} | ||
+ "VORLAGE" und "SYNTHESE" liefern ein nahezu gleiches $H_1$. | + "VORLAGE" und "SYNTHESE" liefern ein nahezu gleiches $H_1$. | ||
Revision as of 22:52, 13 June 2021
Two synthetically generated text files
The former practical course attempt Value Discrete Information Theory by Günter Söder at the Chair of Communications Engineering at the TU Munich uses the Windows programme WDIT. The links given here lead to the PDF version of the practical course instructions or to the ZIP version of the programme.
With this programme
- one can determine the frequencies of letter triplets such as "aaa", "aab", ... , "xyz", ... and save them in an auxiliary file,
- then create a file "SYNTHESE" whereby the new character is generated from the last two characters and the stored triple frequencies.
Starting with the German and English Bible translations, we have thus synthesised two files, which are indicated in the diagram:
- die $\text{Datei 1}$ (red border),
- die $\text{Datei 2}$ (green border)
It is not indicated which file comes from which template. Determining this is your first task.
The two templates are based on the natural alphabet $(26$ letters$)$ and the space ("LZ") ⇒ $M = 27$. In the German Bible, the umlauts have been replaced, for example "ä" ⇒ "ae".
$\text{File 1}$ has the following characteristics:
- The most frequent characters are "LZ" with $19.8\%$, followed by "e" with $10.2\%$ and "a" with $8.5\%$.
- After "LZ" (space), "t" occurs most frequently with $17.8\%$ .
- Before a space, "d" is most likely.
- The entropy approximations in each case with the unit "bit/character" were determined as follows:
- $$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}. $$
In contrast, the analysis of $\text{file 2}$:
- The most frequent characters are "LZ" with $17.6\%$ followed by "e" with $14.4\%$ and "n" with $8.9\%$.
- After "LZ", "d" is the most likely $(15.1\%)$ followed by "s" with $10.8\%$.
- After "LZ" and "d", the vowels "e" $(48.3\%)$, "i" $(23\%)$ and "a" $(20.2\%)$ are dominant.
- The entropy approximations differ only slightly from those of $\text{file 1}$.
- For larger $k$–values, these are slightly larger, for example $H_3 = 3.17$ instead of $H_3 = 3.11$.
Hints:
- The task belongs to the chapter Natural discrete value message sources.
- Reference is made in particular to the page Synthetically generated texts.
Questions
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".
