Cours sur les ensembles de mots (dictionnaires)

INF 421 Luc MarangetLes ensembles de mots(dictionnaires)Luc.Maranget@inria.frhttp://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/1Une application concr`ete des arbresI Comment repr´esenter un dictionnaire.I Rechercher un mot.I Construire le dictionnaire (a` partir d’une liste de mots)I Sauver/relire le dictionnaire.I Fonctionnalit´es avanc´ees :. Jouer aux mots-crois´es.. Proposer des corrections.I Intersection de deux dictionnaires.DiversionLire et ´ecrire les fichiers.2Du g´en´eral au particulierPrenons un peu d’avance sur le cours! Les automates (finis) sontcaract´eris´es par :I Un ensemble d’´etats, dont certains sont finaux et un est initial.I Des transitions entre ´etats, qui « mangent » des caract`eres enentr´ee.Voici par exemple l’automate qui reconnaˆıt le mot coucou.c o u c o uccccccc ooooooo u c o uX X X X X X Xc o u ccccccc o uuuuuuu3Plusieurs mots `a la foiscsa e a eis c csMots reconnuscas, ce, ces, ci, sa, sac, sec.Tous les chemins qui m`enent a` un ´etat « final » (sommet gris).(Un tel arbre s’appelle parfois un trie).4R´ealisation des triesIl y a plusieurs techniques, certaines tr`es sophistiqu´ees. Ici, poursimplifier la programmation :I Au lieu de d´ecorer les liens, on va, comme d’habitude d´ecorerles sommets de l’arbre (on pousse les ´etiquettes vers le bas).c sa e i a es s c cI Au lieu de consid´erer des ´etats finaux (sommets gris´es), on5identifie les fins de mots par un marqueur ...