TD 6 - Dictionnaire par arbre lexicographique


Problème

Pour réaliser un vérificateur orthographique, on doit tester rapidement si un mot existe dans un dictionnaire et aussi pouvoir y ajouter de nouveaux mots. Dans le cas d'un dictionnaire relativement dense, il est intéressant de ne pas répéter les préfixes communs. C'est ce que permet la structure d'arbre lexicographique.

Arbre lexicographique

Un arbre lexicographique (non vide) A est une liste de paires (ci, Ai) où les ci sont des caractères et les Ai sont des arbres lexicographiques. Cela définit bien une structure d'arbre binaire avec pour chaque noeud un caractère, un lien vers un sous-arbre et un lien vers la suite de la liste (qui est aussi un arbre). La liste est ordonnée selon les ci croissants. Une paire (ci, Ai) représente l'ensemble ciAi de tous les mots qui s'écrivent comme ci suivi d'un mot de Ai. L'ensemble des mots de A est alors l'union de tous les ciAi.

Dans cette définition, un chemin de la racine vers un noeud code un préfixe et les mots d'un dictionnaire sont représentées par les feuilles de l'arbre. Cela pose un problème pour identifier les mots qui sont préfixes d'autres mots.
Pour cela, on introduit un caractère spécial "fin de mot" et un mot est alors codé par le chemin de la racine vers un noeud contenant "fin de mot". Il est à noter qu'un noeud "fin de mot" n'a pas de sous-arbre de suffixe mais peut avoir un suivant dans la liste. Pour "fin de mot", on utilisera le caractère d'espace ' ' qui se classe avant tout caractère affichable.

Par exemple, l'arbre correspondant aux 8 mots

a
bac
balle
ballon
bas
base
bus
sac
peut se représenter comme suit :


où le lien horizontal donne les suffixes et le lien vertical donne les suivants dans la liste.

Travail demandé

La classe Dictionnaire.java qui est fournie, contient une méthode init() qui construit l'arbre donné en exemple ci-dessus. Il s'agit de compléter cette classe pour réaliser les fonctions de base sur les arbres lexicographiques.
  1. Écrire une méthode récursive :
    static void print(Dictionnaire d, String racine)
    qui doit afficher tous les mots de d, en ordre et un par ligne, en les préfixant par racine.

    Avec l'exemple fourni, on doit obtenir :

    a
    bac
    balle
    ballon
    bas
    base
    bus
    sac
    
    Écrire une variante :
    static void print2(Dictionnaire d, String racine)
    dans laquelle on aura remplacé une récursion par une itération.

  2. Compléter la méthode
    static boolean existe(String mot, Dictionnaire d)
    qui teste si mot est contenu dans d.
    On utilisera les méthodes suivantes qui s'appliquent à un objet de la classe String :
    mot.length() qui retourne la longueur de mot,
    mot.charAt(0) qui retourne le premier caractère de mot,
    mot.substring(1) qui retourne mot privé de son premier caractère.

    Avec les exemples fournis dans main, on doit obtenir :

    "" n'existe pas
    "a" existe
    "c" n'existe pas
    "bac" existe
    "bal" n'existe pas
    "bas" existe
    "base" existe
    "bache" n'existe pas
    
  3. Compléter la méthode
    static Dictionnaire insere(String mot, Dictionnaire d)
    qui ajoute mot dans d et retourne l'arbre résultant.
    Pour l'ajout de suffixes, on utilisera une méthode annexe
    static Dictionnaire decompose(String mot)
    qui construit l'arbre qui représente mot.

    On commencera par tester avec quelques mots pris sur la ligne de commande. Pour tester avec un nombre de mots plus important, on utilisera la fonction lecture qui permet d'insérer tous les mots d'un fichier.

  4. Écrire une méthode :
    static void dessine(Dictionnaire d, String indent)
    qui permet d'esquisser une représentation arborescente de d.

    Avec l'exemple fourni, on doit obtenir :

     a
     b a c
         l l e
             o n
         s
           e
       u s
     s a c
    

  5. Écrire une méthode :
    static void compile(Dictionnaire d, String indent)
    qui doit imprimer une expression Java qui permet de construire l'arbre d. Une mise en page similaire à celle utilisée dans la méthode init est relativement compliquée à obtenir.
    On pourra commencer par une méthode plus simple qui consiste à écrire un élément par ligne :
        dico =
          d('a',
           d(' ',
            null,
           null),
          d('b',
    ...
    


URL: https://www.enseignement.polytechnique.fr/profs/informatique/Philippe.Chassignet/00-01/TD/td_6.html

Pour toutes suggestions, commentaires ou remarques, email : Philippe.Chassignet@polytechnique.fr