TD5, Entropie de l’anglais et générer de l’anglais "aléatoire"

INF558 Introduction à la théorie de l’information

7 février 2020

Le but de ce TD est double

  1. il s’agit dans un premier temps de construire un modèle simple mais assez précis pour un texte en anglais et d’utiliser ce modèle pour estimer l’entropie de l’anglais.
  2. Dans un deuxième temps on utilisera ce modèle simplifié pour générer un texte ayant plus ou moins l’air d’être anglais.

1  Un modèle markovien de l’anglais

Nous allons utiliser ici un modèle markovien d’ordre n invariant dans le temps. En d’autres termes nous supposons que la source X1,X2,… de l’anglais est telle qu’il existe une fonction f(x1,x2,…,xn+1) telle que pour tout t ≥ 1:

p
Xt+n=xn+1|(Xt,Xt+1,…,Xt+n−1)=(x1,x2,…,xn)
f(x1,x2,…,xn+1).

Vous utiliserez les textes en anglais qui se trouvent ici ou ici.

Pour construire le modèle on comptera le nombre d’occurrences n(x1,…,xn+1) d’un (n+1)-uplet de lettres parmi les (n+1)-uplets de lettres consécutives du/des textes que l’on utilise pour construire le modèle. On utilisera ensuite ce comptage pour estimer les probabilités conditionnelles via la formule

p(xn+1|x1 … xn) = 
n(x1 … xn xn+1)
 
a
 n(x1 … xn a)
.

Il est conseillé d’utiliser la classe java HashMap. Vous pouvez aussi utiliser les classes suivantes Markov.java et Next.java. La dernière classe peut être utilisée par exemple pour représenter un modèle markovien par une HashMap d’un ensemble de couples clés/valeur. Les clés correspondent aux chaînes de caractère de taille n x1 x2xn que l’on peut trouver parmi n lettres consécutives des textes d’apprentissage et les valeurs représenteront toutes les lettres possibles pouvant suivre x1 x2xn ( ainsi que la fréquence avec laquelle la lettre suit x1 x2xn). On pourra utiliser la classe Next.java pour représenter ces valeurs.

Réaliser différentes modélisations markoviennes du texte pour un ordre n variant de 1 à 10 et calculer l’entropie correspondant à chaque modélisation.

2  Simuler de l’anglais “aléatoire”

Utilisez maintenant ces modèles approximatifs pour simuler un texte anglais. Il doit produire un texte en anglais qui a les mêmes statistiques que celles que vous avez calculées (mais bien sûr le texte n’est pas censé avoir une signification).


Ce document a été traduit de LATEX par HEVEA