Le trente-sixième chapitre de Madame Bovary

Votre programme est à rendre par courier électronique à Luc.Maranget@inria.fr avant le 11 janvier 2008, 23h59.
Trop tard : Solution.

Questions posées avant le 11 janvier et mes réponses disponibles ici.

Ce document en Pdf.

Objectif

Suivre la technique « chaîne de Markov » décrite lors de l’amphi 04 pour faire écrire par un ordinateur un chapitre plausible de Madame Bovary de Gustave Flaubert (qu’il nous pardonne, notre œuvre n’arrivera pas à la cheville de la sienne).

Ce qu’il faut faire

Écrire le programme Markov qui produit, à la demande, des chapitres dans le style de Madame Bovary.

Pour un entier n ≥ 1 donné, le texte produit est tel que :

L’entier n est donné en argument de la ligne de commande. Ainsi, la commande

% java Markov 3

produit un texte plutôt étrange, par exemple1 :

Un soir que la fenêtre était ouverte, et que, assise au bord, elle venait de s’échapper dans le jardin. Emma, tout exprès, avait retiré la clef de sol, et s’occupait volontiers de littérature après son dîner, quand il ne jouait pas aux cartes. M. Homais le considérait pour son instruction ; madame Homais l’affectionnait pour sa complaisance, car souvent il accompagnait au jardin les petits Homais, marmots toujours barbouillés, fort mal élevés et quelque peu lymphatiques, comme leur mère. Ils avaient pour les soigner, outre la bonne, Justin, l’élève en pharmacie, un arrière-cousin de M. Homais et peut-être les pesanteurs du déjeuner, restait indécis et comme sous la fascination du pharmacien qui répétait :

[…]

– Oui, du capharnaüm ! La clef qui enferme les acides avec les alcalis caustiques ! Avoir été prendre une bassine de réserve ! Une bassine à couvercle ! et dont jamais peut-être je ne me sens pas en mon assiette ; il faudra même un de ces hommes d’ardeurs taciturnes qui travaillent la nuit dans les livres, et portent enfin, à soixante ans, quand vient l’âge des rhumatismes, une brochette de croix, sur leur habit noir, mal fait. Elle aurait voulu ne rien entendre, ne rien voir, afin de ne pas payer, d’emprunter, de souscrire des billets, puis de renouveler ces billets, qui s’enflaient à chaque échéance nouvelle, elle avait fini par préparer au sieur Lheureux était encore si longue, qu’il n’y fallait pas songer. D’ailleurs, imaginant qu’elle y mettait de la délicatesse, Charles insista davantage ; si bien qu’elle demeurait fort embarrassée dans sa velléité de sacrifice, lorsque l’apothicaire vint à propos lui fournir une occasion.

Le texte ci-dessus est de toute évidence dérivé de l’œuvre de Flaubert. Dérivé est d’ailleurs le mot juste, on perçoit un certain flottement dans l’écriture.

Plus sérieusement, on notera par exemple, que le chapitre numéro 28 commence par « Un soir que [Charles l’écoutait,…] ». La jolie sentence « Emma, tout exprès, avait retiré la clef de sol, […] » n’est pas de Flaubert, mais Flaubert a écrit :

Il est donc établi que « retiré la clef de » et « la clef de sol, » sont deux suites de n+1 = 4 mots qui permettent de relier la clef de la barrière à la clef de sol.

Algorithme

Ce qu’est exactement un mot est expliqué (si on peut dire) plus loin comme étant défini par la classe des lecteurs de mots fournie. Disons pour le moment qu’il existe, dans les textes fournis, un mot un peu spécial <PAR> qui indique les sauts de paragraphes. Il est également commode de considérer deux mots supplémentaires <START> et <END> qui marquent le début et la fin d’un chapitre. Notez que ces mots ne sont pas présents dans les textes fournis, et n’ont pas besoin de l’être.

L’algorithme emploie une table de hachage dont les clés sont des suites de n mots et les valeurs des multi-ensembles (ensembles avec répétitions possibles des éléments) de mots. Il se décompose en deux phases, construction de la table et production du texte.

Construction de la table

  1. Pour chaque chapitre,
    1. Soit P préfixe, noté w1, w2, …, wn−1, wn et valant initialement <START>, <START>, …, <START>, <START>.
    2. Pour chaque mot w du chapitre en cours,
      1. Ajouter w aux mots associés à P,
      2. Le préfixe P devient w2, w3, … wn, w.
    3. Ajouter <END> aux mots associés à P.

Production du texte

  1. Soit P un préfixe, valant initialement <START>, <START>, …, <START>, <START>.
  2. Boucle,
    1. Choisir w parmi les mots associés à P, selon une loi uniforme.
    2. Si w est <END>, alors terminer.
    3. Afficher w.
    4. Le préfixe P devient w2, w3, … wn, w.

Sans chercher à produire une présentation parfaite, l’affichage devra être lisible (espaces entre les mots, sauts de lignes avant et après le mot <PAR>).

Difficultés prévisibles

Un « multi-ensemble » de mots est facilement représenté soit comme une liste soit comme un tableau. Sans que cela soit un jugement définitif, on peut dire que la liste est plus appropriée dans la phase de construction, tandis que le tableau est plus approprié dans la phase de production du texte (pour choisir le n+1-ième mot, cf. le cours.) Une solution simple est de convertir les listes en tableaux entre les deux phases de l’algorithme.

On peut iterer sur les associations d’une HashMap<K,V> de la bibliothèque de la manière suivante :

  HashMap<K,Vt = …
  for (K k : t.keySet()) {
    V v = t.get(k) ;
    I[k,v]
  }

Le code ci-dessus exécute I[k,v] pour toutes les associations (kv) contenues dans la table t. Les derniers transparents de l’amphi 04 donnent quelques explications.

Enfin, souvenez-vous qu’une fois qu’une clé est rangée dans la table, cette clé ne doit pas changer.

Fichiers fournis

Les chapitres de Madame Bovary

Le texte de Madame Bovary est donné sous la forme de 35 fichiers (un par chapitre de 01.txt à 35.txt) dans l’archive bovary.tar.gz à désarchiver ainsi :

% tar zxf bovary.tar.gz

Vous disposez maintenant d’un sous-répertoire bovary qui contient les 35 chapitres. Le texte est soumis à cette licence.

Lecture des mots

Récupérez la classe des lecteurs des mots WordReader qui est conforme à la description donnée en cours. et compilez la.

Cette classe comprend entre autres, un constructeur new WordReader (String filename) qui prend un nom de fichier en argument ; ainsi qu’une méthode main d’essai :

% java WordReader bovary/01.txt
[Nous]
[étions]
[à]
[l'Etude,]
[quand]
[le]
[Proviseur]
[entra]
[suivi]
[d'un]
  ...
[<PAR>]
 ...

Outre les mots du premier chapitre écrit par Flaubert, vous voyez apparaître des mots <PAR> qui indiquent simplement les paragraphes. Ces mots <PAR> sont à traiter comme des mots ordinaires.

Interface de votre programme

Votre programme Markov doit obligatoirement se comporter ainsi.


1
Le texte est légèrement modifié pour des raisons de présentation typographique.
2
À la relire, je trouve cette phrase impressionnante : deux scènes en quinze mots.

Ce document a été traduit de LATEX par HEVEA