M1103 Feuille 3

Dans cette feuille d’exercices, nous voulons écrire un programme pour générer automatiquement des tweets de Donald Trump.

Le principe est le suivant : à partir des tweets déjà publiés, produire de nouveaux tweets “faux” mais crédibles reprenant de manière cohérente des morceaux de tweets existant. Par exemple, en partant des deux tweets suivants :

Le chien mange des croquettes.

Le chat mange des souris.

on va générer un nouveau tweet de la manière suivante:

  1. On choisit aléatoirement un début possible: deux premiers mots d’un tweet existant choisi au hasard. Sur l’exemple, on choisit par exemple aléatoirement Le chien. Cela initialise une paire de mots, ici "Le" et "chien", que nous appelons paire courante.

  2. Étant donnée une paire courante, on choisit aléatoirement un mot possible pour continuer la phrase: un mot qui suit déjà les mots de la paire dans les tweets connus. Sur l’exemple, après la paire Le chien, le seul mot possible (car déjà vu dans les tweets) est mange. On choisit donc ce mot et la paire courante devient chien mange. De même, après cette paire, le seul mot suivant possible est des, et la paire courante devient donc mange des. Maintenant, à partir de cette paire, deux mots suivants sont possibles : croquettes ou souris. On va donc choisir aléatoirement un de ces deux mots, par exemple souris. La paire courante devient des souris. Il n’y a maintenant plus de mot suivant possible, on va donc arrêter la génération.

On a ainsi produit le “faux” tweet:

Le chien mange des souris.

Cet exemple est très simple ; à la fin du TP, vous allez générer des “faux” tweets à partir d’une base de 1000 tweets réellement publiés sur le compte de Donald Trump.

Téléchargez le fichier code.zip et ajoutez son contenu (les fichiers pair.cpp, pair.h, distribution.cpp, distribution.h, chain.cpp, chain.h, test.cpp, asserts.h) à un nouveau projet Code::Blocks. Placer le fichier tweets.txt dans le dossier principal de votre projet.

Vous pouvez tester vos fonctions en lançant le programme dont la fonction main est définie dans le fichier test.cpp.

Exercice 1 — Couples de strings

Comme nous avons vu, nous avons besoin de gérer la paire de deux mots successifs. Pour cela, nous allons définir une structure de données pour stocker un tel couple de deux mots consécutifs. Cette structure de données sera la classe Pair dans les fichiers pair.h et pair.cpp que nous allons compléter dans ce premier exercice.

a — Encapsulation de deux strings

La première tâche est de bien encapsuler les deux strings dans les objets de la classe Pair. Nous allons donc créer un constructeur qui prend deux strings, ainsi que deux fonctions getters pour pouvoir y accéder.

Compléter le constructeur déclaré dans la classe Pair et les deux fonctions membres get_first et get_second. La fonction get_first retourne le premier string passé au constructeur, la fonction get_second retourne le deuxième.

b — Égalité de couples

Nous allons stocker des couples de strings dans des vecteurs. Pour pouvoir les retrouver, nous allons implémenter une relation d’égalité pour des couples.

Compléter l’opérateur == pour des instances de la classe Pair. Il retourne true si et seulement si les premiers strings et les deuxièmes strings sont égaux.

Exercice 2 — Mots aléatoires

Pour deviner le prochain mot dans un tweet, nous avons besoin d’un choix aléatoire du mot dans une liste de mots possibles. Cela sera fait dans la classe Distribution dans les fichiers distribution.h et distribution.cpp.

Cette classe va mémoriser un vecteur de mots, et vous allez définir les fonctions permettant d’ajouter des mots à ce vecteur.

Pour représenter efficacement une liste de mots où des mots peuvent apparaître plusieurs fois, il faut utiliser deux vecteurs :

a — Rajout de mots possibles

Chaque instance de la classe Distribution contient une liste de mots possibles, dans laquelle on choisira aléatoirement un élément. Pour commencer, nous allons écrire une fonction pour rajouter des mots à cette liste et une deuxième fonction pour compter le nombre de fois que nous avons rajouté un mot donné.

Compléter les fonctions membres add_string et get_count. La fonction get_count retourne le nombre de fois que add_string a été appelé avec le string donné en argument.

b — Compte total de mots

Nous voulons choisir un mot donné dans la liste des mots possible avec une probabilité proportionnelle au nombre de fois qu’il a été rajouté. Pour cela, nous avons besoin de connaître le nombre total de rajouts (avec des mots quelconques).

Compléter la fonction membre get_total_count. Elle renvoie le nombre total d’appels à add_string.

c — Choix aléatoire

La fonction membre random de la classe Distribution retourne un mot aléatoire dans la liste de mots qui ont été rajoutés. Un mot qui a été rajouté \(n\) fois est choisi avec probabilité \(n/T\)\(T\) est le compte total de mots dans la liste.

Compléter la fonction membre random pour quelle renvoie un élément aléatoire parmi les string rajoutés, avec une probabilité proportionnelle au nombre de fois que le mot a été rajouté.

Si le compte total est nul, c’est-à-dire aucun string n’a été rajouté, renvoyer le string “END”.

Exercice 3 — Construire un tweet

Nous allons maintenant implémenter la classe Chain (dans les fichiers chain.h et chain.cpp) qui garde pour chaque couple de mots possible, une instance de la classe Distribution. La distribution pour un couple donné détermine le choix du mot suivant.

Nous allons garder dans une donnée membre un objet de type Pair correspondant à la paire courant (les deux mots les plus récemment choisis).

Après un choix initial pour les deux premiers mots, nous allons choisir itérativement un mot pour rajouter à la fin du tweet courant. Nous allons mettre à jour la donnée membre en prenant en compte le nouveau mot choisi.

a — Trouver les deux premiers mots

Pour commencer un tweet, nous avons besoin de déterminer les deux premiers mots. Pour cela, nous allons stocker dans la Chain un vecteur de Pair possible pour commencer un tweet (notamment ceux que Donald Trump a effectivement utilisés au début d’un tweet).

Nous allons rajouter des couples possible (sans doublon) pour le début de tweet avec la fonction membre add_start_pair. La fonction membre init choisit aléatoirement un couple qui a été rajouté avec add_start_pair. Nous voulons pouvoir regarder la paire courante (c’est-à-dire le couple des deux mots les plus récents dans le tweet) an appelant la fonction membre get_current.

Sur l’exemple ci-dessus, le paramètre de la méthode add_start_pair sera donc successivement remplacé par la paire Le chien et la paire Le chat. La méthode init() va choisir aléatoirement une de ces deux paires dans le tableau, sur l’exemple Le chien, et la stocker dans la paire courante. Enfin, la méthode get_current va retourner cette paire courante qui a été stockée.

Compléter les fonction membres add_start_pair, init et get_current décrites ci-dessus. Chaque couple rajouté doit avoir la même probabilité d’être choisi dans la fonction init. Avant avoir rajouté des couples avec add_start_pair ou avant d’avoir appelé init, la fonction get_current peut renvoyer un Pair quelconque.

b — Trouver le mot suivant

Maintenant que nous savons choisir les deux premiers mots du tweet, nous allons choisir itérativement le mot suivant, en fonction des deux mot précédents. La fonction membre add_string_to_pair prend en argument un string et un Pair. Elle doit rajouter le string donné à la distribution correspondante au couple donné. Pour cela il est nécessaire de stocker non seulement un vecteur de couples mais aussi un vecteur de distributions. Si le couple donné n’est pas encore stocké, il faudra le rajouter au vecteur et créer une nouvelle distribution pour le couple.

La fonction next retourne le prochain mot selon la fonction random de la distribution du couple courant, c’est-à-dire celui retourné par la fonction get_current. Elle met aussi à jour le couple courant avec le nouveau mot. S’il n’existe pas de mot suivant possible, elle renvoie le string “END”.

Sur l’exemple ci-dessus, les paramètres de la méthode add_string_to_pair seront donc successivement remplacés par :

À la fin, le tableau des paires stocké contiendra donc

Le chien chien mange mange des Le chat chat mange

et le tableau des distributions contiendra

"mange" "des" "croquettes","souris" "mange" "des"
1 1 1 , 1 1 1

La méthode next va chercher la distribution correspondant à la paire courante, tirer aléatoirement un mot dans cette distribution, et mettre à jour la paire courante. Sur l’exemple, lorsque la paire courante est mange des, la distribution correspondant est

"croquettes","souris"
1 , 1

et la méthode va donc choisir aléatoirement entre ces deux mots suivants.

Compléter les fonctions membres add_string_to_pair et next décrites ci-dessus.

c — Tweets complets

Votre code, avec la fonction read et la boucle à la fin de fonction main que nous vous avons fournies, permet de générer de nouveau tweet à partir d’une base de données de tweet qui est stockée dans le fichier tweets.txt. Après avoir lancé le programme, vous verrez des tweets aléatoirement générés.

retour au site web du cours