Aufgaben:Aufgabe 1.8: Synthetisch erzeugte Texte: Unterschied zwischen den Versionen
Aus LNTwww
| Zeile 3: | Zeile 3: | ||
}} | }} | ||
| − | [[Datei:P_ID2324__Inf_A_1_8.png|right|]] | + | [[Datei:P_ID2324__Inf_A_1_8.png|right|Zwei synthetisch erzeugte Textdateien]] |
| − | |||
| − | : | + | Der frühere Praktikumsversuch [http://www.lntwww.de/downloads/Sonstiges/Texte/Wertdiskrete_Informationstheorie.pdf Wertdiskrete Informationstheorie] von Günter Söder am Lehrstuhl für Nachrichtentechnik der Technischen Universität München verwendet das Windows-Programm [http://www.lntwww.de/downloads/Sonstiges/Programme/WDIT.zip 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 Datei 1 (rote Umrandung), | ||
| + | * die Datei 2 (grüne Umrandung) | ||
| − | |||
| − | + | Nicht bekannt gegeben 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 '''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_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} | ||
| Zeile 37: | Zeile 32: | ||
H_4 = 2.81\hspace{0.05cm}. $$ | H_4 = 2.81\hspace{0.05cm}. $$ | ||
| − | + | Dagegen ergibt die Analyse von '''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 Datei 1. | |
| + | * Für größere $k$–Werte sind diese etwas größer, zum Beispiel $H_3 = 3.17$ statt $H_3 = 3.11$. | ||
| − | |||
| − | :* Die | + | ''Hinweise:'' |
| + | *Die Aufgabe gehört zum Kapitel [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]]. | ||
| + | *Bezug genommen wird insbesondere auf die Seite [[Informationstheorie/Natürliche_wertdiskrete_Nachrichtenquellen#Synthetisch_erzeugte_Texte|Synthetisch erzeugte Texte]]. | ||
| − | |||
| − | + | Weiter ist anzumerken, dass unsere Analyse basierend auf der „Bibel” eher auf einen gleichen Entropiewert für Englisch und Deutsch schließen lässt. | |
| + | *Dafür spricht auch, dass beide Übersetzungen nahezu gleich groß sind (ca. 4 Millionen Zeichen). | ||
| + | *Hätte Deutsch eine um 30% größere Entropie als Englisch, dann müsste nach unserer Meinung die englische Version um 30% länger sein, wenn man von gleichem Inhalt der beiden Übersetzungen ausgeht. | ||
| + | *Wir erheben aber keinen Anspruch auf die Richtigkeit unserer Argumentation. | ||
| Zeile 69: | Zeile 68: | ||
{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 | + | + VORLAGE und SYNTHESE liefern ein nahezu gleiches $H_1$. |
| − | + VORLAGE und SYNTHESE liefern ein nahezu gleiches | + | + VORLAGE und SYNTHESE liefern ein nahezu gleiches $H_21$. |
| − | + VORLAGE und SYNTHESE liefern ein nahezu gleiches | + | + VORLAGE und SYNTHESE liefern ein nahezu gleiches $H_3$. |
| − | - VORLAGE und SYNTHESE liefern ein nahezu gleiches | + | - VORLAGE und SYNTHESE liefern ein nahezu gleiches $H_4$. |
Version vom 3. Mai 2017, 11:07 Uhr
Der frühere Praktikumsversuch Wertdiskrete Informationstheorie von Günter Söder am Lehrstuhl für Nachrichtentechnik der Technischen Universität 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 Datei 1 (rote Umrandung),
- die Datei 2 (grüne Umrandung)
Nicht bekannt gegeben 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 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 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 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 Nachrichtenquellen mit Gedächtnis.
- Bezug genommen wird insbesondere auf die Seite Synthetisch erzeugte Texte.
Weiter ist anzumerken, dass unsere Analyse basierend auf der „Bibel” eher auf einen gleichen Entropiewert für Englisch und Deutsch schließen lässt.
- Dafür spricht auch, dass beide Übersetzungen nahezu gleich groß sind (ca. 4 Millionen Zeichen).
- Hätte Deutsch eine um 30% größere Entropie als Englisch, dann müsste nach unserer Meinung die englische Version um 30% länger sein, wenn man von gleichem Inhalt der beiden Übersetzungen ausgeht.
- Wir erheben aber keinen Anspruch auf die Richtigkeit unserer Argumentation.
Fragebogen
Musterlösung
- 1. Richtig ist der Lösungsvorschlag 1. In der Datei 1 erkennt man viele englische Wörter, in der Datei 2 viele deutsche. Sinn ergibt keiner der beiden Texte.
- 2. Die Wahrscheinlichkeit eines Leerzeichens beträgt bei der Datei 1 (Englisch) 19.8%. Also ist im Mittel jedes 1/0.198 = 5.05–tes 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 Datei 2 (Deutsch):
- $$L_{\rm M} = \frac{1}{0.176}-1 \approx 4.68\,{\rm Zeichen}\hspace{0.05cm}.$$
- Richtig ist somit der Lösungsvorschlag 2. Die Abschätzungen von Shannon und Küpfmüller bestätigen unser Ergebnis.
- 3. Zur Bestimmung der Entropienäherung Hk müssen k–Tupel ausgewertet werden, zum Beispiel für k = 3 Tripel: „aaa”, „aab”, .... Nach der Generierungsvorschrift „Neues Zeichen hängt von den beiden Vorgängern ab” werden H1, H2 und H3 von VORLAGE und SYNTHESE übereinstimmen, allerdings auf Grund der endlichen Dateilänge nur näherungsweise.
- Dagegen unterscheiden sich die H4–Näherungen stärker, da bei der Generierung der dritte Vorgänger unberücksichtigt bleibt. Bekannt ist nur, dass auch bezüglich SYNTHESE H4 < H3 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 Datei 1, wie die folgende Grafik zeigt. Nicht bei allen Markierungen tritt „the” isoliert auf ⇒ direkt vorher und nachher ein Leerzeichen.
- 5. 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.
- Weiterhin gilt:
- Nach „da” folgt „s” mit größter Wahrscheinlichkeit: 48.2%.
- Nach „di” folgt „e” mit größter Wahrscheinlichkeit: 78.7%.
- Alle Aussagen treffen somit zu. Die Grafik zeigt die Datei 2 mit allen „der”, „die” und „das”.
