Corrigé du mini-projet Bovary

Le projet demandé est une généralisation du programme donné en exemple lors de l’amphi 04. La généralisation porte sur la taille variable des préfixes, le programme de l’amphi traitant le cas n=2. Par ailleurs le code de construction de la table des préfixes n’avait pas été donnée en amphi.

Code complet de la solution.

Une classe des préfixes

Une bonne décision est de concevoir une classe Prefix des préfixes de n mots. On peut s’inspirer assez directement de la classe Prefix des transparents de l’amphi 04.

Une idée simple est de remplacer les deux champs w1 et w2 de la classes des préfixes de deux mots par un tableau de mots. Soit :

class Prefix {
  final static String start = "<START>", end = "<END>", par = "<PAR>" ;

  private String [] t ;

  Prefix (int n) {
    t = new String [n] ;
    for (int k = 0 ; k < n ; k++)
      t[k] = start ;
  }

  …
}

Le constructeur Prefix (int n) construit le préfixe initial dont les n mots sont <START>. On note au passage que les trois mots spéciaux sont des constantes de la classe Prefix.

Nous avons ensuite, en deux occasions, besoin de construire le préfixe « décalé », (w2, w3, …, wn, w), à partir d’un nouveau mot w et d’un préfixe P = (w1, w2, …, wn−1, wn). Informellemwent on décale les mots de P d’un cran vers la gauche, ce qui libère la position de mot la plus à droite dans laquelle on range w.

Nous écrivons une méthode shift qui prend le mot w en argument et renvoie le préfixe décalé.

 // Glissement du préfixe.
  private Prefix(String [] t) {
    this.t = t ;
  }

  Prefix shift(String w) {
    int n = t.length ;
    String [] tt = new String [n] ;
    for (int k = 0 ; k < n-1 ; k++)
      tt[k] = t[k+1] ;
    tt[n-1] = w ;
    return new Prefix(tt) ;
  }

Vous noterez le constructeur privé qui prend le tableau de mots en argument explicite. Ce constructeur ne peut pas être appelé de l’extérieur de la classe Prefix, et sera appelé de shift exclusivement. On en déduit que tous les préfixes du programme comporteront le même nombre de mots. Vous noterez aussi que shift alloue un nouveau tableau de mots, et ne modifie pas le tableau interne t. Je ne vois d’ailleurs aucun moyen de procéder autrement : chaque prefixe doit posséder son propre tableau de mots.

Le préfixes seront les clés des tables de hachage, il convient donc d’équiper la classe Prefix de méthodes hashCode() et equals(Object o) qui s’appuient sur le contenu des préfixes (sur les n mots du préfixe). Si besoin est, voyez quelques précisions dans la page de suivi.

  // Suffisant en pratique : mélange des hashCode() des mots du préfixe.
  public int hashCode() {
    int r = 0 ;
    for (String s : t) {
      r += 37*r + s.hashCode() ;
    }
    return r ;
  }

  // Égalité structurelle des préfixes.
   public boolean equals(Object o) {
     Prefix op = (Prefix) o;
     int n = t.length ;
     for (int k = 0 ; k < n ; k++) {
       if (! t[k].equals(op.t[k])) return false ; // ! est la négation des boolean.
     }
     return true ;
  }

Vous noterez que le calcul de fonction de hachage est assez simple, (et inspiré directement du hachage des chaînes de Java). Un autre choix possible est la somme des hashCode() des mots du préfixe, qui présente l’inconvénient de produire la même valeur de hachage pour toutes les permutations d’un ensemble de mots donné, ce qui semble innofensif pour l’application traité.

Vous noterez aussi que j’ai écrit la méthode equals en supposant que les tableaux t (i.e. this.t) et op.t ont la même longueur, c’est-à-dire sans me fatiguer à traiter le cas de longueurs distinctes, exclu en pratique.

Construire et exploiter la table

Le programme repose sur une table qui associe chaque préfixe de longueur n du texte initial, au multi-ensemble des mots qui suivent ce préfixe dans le texte initial. Dans la suite, j’explique la construction puis l’exploitation de la table. Toutes les méthodes qui suivent sont des méthodes statiques de la classe Markov.

Construction de la table

L’algorithme suivant (donné dans l’énoncé) décrit exactement comment construire la table qui à chaque préfixe P de taille n du texte associe la liste des mots qui peuvent suivre P dans le texte. z

  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.

En pratique les chapitres sont des noms de fichiers, passés en argument à une méthode build, le second argument est la taille des préfixes.

static HashMap<Prefix,String []> build(String [] files, int n) { …

La table d’associations renvoyée sera des préfixes (classe Prefix) vers les tableaux de chaînes. Mais lors de la construction, il sera plus commode de considérer des liste de chaînes. On se donne donc une classe des listes de chaînes WordList tout à fait classique, à part une méthode static String [] toArray(WordList p) qui renvoie le tableau des mots de la liste p.

Puis on déclare une table des préfixes vers les listes de chaînes.

   HashMap<Prefix,WordList> t = new  HashMap<Prefix,WordList> () ;

Ensuite il faut écrire la boucle : « pour tous les chapitres ». Soit :

  for (String name : files) {
    WordReader reader = new WordReader (name) ;
    …
  }

Le lecteur des mots du chapitre étant crée, on peut ensuite lire les mots un par un, jusqu’à la fin du chapitre ainsi :

     String w reader.read() ; // premier mot
     Prefix pref = new Prefix (n) ;

     while (w != null) {
       t.put(pref, new WordList (w,t.get(pref))) ;
       pref = pref.shift(w) ;
       w = reader.read() ; // mot suivant
     }
     t.put(pref, new WordList (Prefix.end,t.get(pref))) ;

On notera :

  1. Le préfixe initial est fabriqué dans par le constructeur Prefix (n) et décalé par pref = pref.shift(w).
  2. Quand la fin du chapitre est atteinte, on ajoute le mot de la fin <END> (c’est-à-dire Prefix.end), aux mots associés aux n derniers mots du chapitre.
  3. On utilise l’astuce que si la table t ne contient pas d’association pour un préfixe P donné, alors l’appel, t.get(P) renvoie null, qui se trouve justement représenter le multi-ensemble vide.

Il reste ensuite à tranformer la table des Prefix vers les WordList en table vers les tableaux de chaînes. Voici un code possible, qui bien évidenment crée une nouvelle table et copie les éléments de l’ancienne table dedans.

    HashMap<Prefix,String []> r = new  HashMap<Prefix,String []> () ;

    for (Map.Entry<Prefix,WordList> e : t.entrySet()) {
      Prefix k = e.getKey() ;
      WordList v = e.getValue() ;
      r.put(k, WordList.toArray(v)) ;
    }

    return r ;
  }

Ce code qui semble quand même abscons est en fait assez simple :

  1. t.entrySet() est l’ensemble des entrées de t, c’est-à-dire l’ensemble des associations, des paires « clé × valeur » que nous avons pris l’habitude de noter (k → v).
  2. Pour une classe des clés K et une classe des valeurs V, Les paires « clé × valeur » sont représentés en java par des objets de type Map.Entry<K,V>.
  3. Et on récupère la clé et la valeur par les méthodes getKey() et getValue(), respectivement.

L’énoncé suggérait une solution un peu différente, en itérant sur l’ensemble des clés t.keySet(). Soit si on veut :

    HashMap<Prefix,String []> r = new  HashMap<Prefix,String []> () ;

    for (Prefix k : t.keySet()) {
      WordList v = t.get(k) ;
      r.put(k, WordList.toArray(v)) ;
    }

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.

Voici un codage en Java, qui suit de très près l’algorithme donné.

    static void chain(HashMap<Prefix,String []> t, int n) {
    Prefix p = new Prefix (n) ;
    Random rand = new Random () ;

    // Boucle infinie.
    for ( ; ; ) {
      // a. Choix du mot suivant w
      String [] ws = t.get(p) ;
      String w = ws[rand.nextInt(ws.length)] ;
      // b. Si mot de la fin, finir
      if (w.equals(Prefix.end)) {
        System.out.println() ;
        return ;
      }
      // c. Affichage de w.
      if (w.equals(Prefix.par)) {
        System.out.println() ;
        System.out.print(Prefix,par) ;
        System.out.println() ;
      } else {
        System.out.print(w + " ") ;
      }
      // d. Décaler le préfixe.
      p = p.shift(w) ;
    }
  }

Tout organiser

Par la méthode main de la classe Markov.

  public static void main (String [] arg) {
    Args a = new Args (arg) ;
    chain(build(a.files,a.prefixLength),a.prefixLength) ;
  }

Bilan rapide

Tous les programmes rendus fonctionnent correctement et ne contiennent que des erreurs mineures. Une erreur rencontrée deux fois regarde le choix uniforme d’une case dans un tableau à l’aide de Math.random(). Il faut écrire :

   String w = t[(int)(Math.random()*t.length)]

Pourquoi ? Comme le dit sa documentation, l’appel Math.random() renvoie un double compris entre 0.0 (inclus) et 1.0 (exclu). Il reste donc à le multiplier par la taille du tableau et à prendre la partie entière du résultat (ce que fait (int)(…)), pour obtenir in tirage uniforme d’un indice entre 0 (inclus) et t.length (exclu).

À mon avis, l’emploi de la classe Random est moins sujet à erreur.

Ce document a été traduit de LATEX par HEVEA