Cours sur les ensembles de mots (dictionnaires)

Informations

• Publié par: Veam
• Nombre de lectures: 64
• Langue: Français

Extrait

INF 421 Luc Maranget
Les ensembles de mots
(dictionnaires)
[e-mail]
http://www.enseignement.polytechnique.fr/profs/
informatique/Luc.Maranget/421/
1Une application concr`ete des arbres
I 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.
Diversion
Lire et ´ecrire les fichiers.
2Du g´en´eral au particulier
Prenons un peu d’avance sur le cours! Les automates (finis) sont
caract´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 en
entr´ee.
Voici par exemple l’automate qui reconnaˆıt le mot coucou.
c o u c o u
ccccccc ooooooo u c o u
X X X X X X X
c o u ccccccc o uuuuuuu
3Plusieurs mots `a la fois
c
s
a e a e
i
s c c
s
Mots reconnus
cas, 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 tries
Il y a plusieurs techniques, certaines tr`es sophistiqu´ees. Ici, pour
simplifier la programmation :
I Au lieu de d´ecorer les liens, on va, comme d’habitude d´ecorer
les sommets de l’arbre (on pousse les ´etiquettes vers le bas).
c s
a e i a e
s s c c
I Au lieu de consid´erer des ´etats finaux (sommets gris´es), on
5identifie les fins de mots par un marqueur (le char ’\0’).
c s
a e iii aaa e
s \0 s \\\0 \\\000 c c
\0 \0 \0 \0
I Et on transforme l’arbre n-aire en arbre binaire :
. Tracer les liens entre fr`eres (de gauche a` droite).
. Supprimer les liens p`ere/fils (sauf vers le premier fils).
. Si on y tient, dessiner un v´eritable arbre binaire (mais a`
quoi bon!).
6Arbre en machine
class Tree {
char val ;
Tree down, next ;
Tree(char val) { this.val = val ; }
Tree(char val, Tree down, Tree next) {
this.val = val ;
this.down = down ; this.next = next ;
}
}
7Cette structure ressemble fortement a` un arbre binaire, mais
attention les deux fils (gauche et droit) jouent des rˆoles distincts :
I Fils gauche : lettre suivante dans le mot.
I Fils droit : lettre suivante dans le dictionnaire.
8
c s
a e
c
\0
\0 c
\0
a e i
s \0
\0 \0 s
\0Une autre interpr´etation, parfois utile
Un dictionnaire est une liste de paires (char × dictionnaire),
(c ,D );···;(c ,D ) avec :
1 1 n n
I Les c sont dans l’ordre : c <···<c .
i 1 n
. La paire (’\0’, ) est le dictionnaire qui ne contient que le
mot vide.
. La paire (c,D) est l’ensemble des mots de la forme cw, ou` w
parcourt D.
. La liste (c ,D );···;(c ,D ) est l’union (disjointe) des
1 1 n n
ensembles de mots (c ,D ),...(c ,D ).
1 1 n n
Dictionnaire vide
Il n’existe pas (i.e. notre construction va le garantir).
I n> 1
I Aucun D n’est vide.
i
9Test d’appartenance
Cette derni`ere interpr´etation est particuli`erement utile pour
programmer les tests d’appartenance :
En toute logique, pour savoir si un mot w est dans un dictionnaire
(c ,D );···;(c ,D ), on doit (surtout) :
1 1 n n
I Si w est le mot vide, alors chercher si c est la marque de fin de
1
mot ou pas.
0
I Sinon w =cw ,
. Trouver le c tel que c =c ,
i i
0
. Chercher w dans D .
i
10