Dictionnaire
Les programmes de correction orthographique ont besoin de
tester rapidement si un mot fait partie du dictionnaire ou non, ainsi
que d'ajouter facilement des mots au dictionnaire. Une version simple de
dictionnaire s'obtient par une représentation
arborescente. L'arbre comporte des noeuds d'arité
variable. Chaque noeud représente une lettre (de type
char
) d'un mot du dictionnaire et a pour
fils les lettres pouvant arriver immédiatement derrière
(dans l'ordre alphabétique).
Le dictionnaire lui-même est (un pointeur sur) la
liste des initiales de mots. Le caractère '\0'
indique la fin d'un mot.
Cet arbre aux noeuds d'arité variable est
représenté par un arbre binaire. Le fils droit est un
pointeur vers la lettre suivante, le fils gauche est un pointeur vers
la liste des fils.
Exemple
Si le dictionnaire
se compose des mots ``cas'', ``ce'', ``ces'', ``ci'' et ``do'',
l'arbre sera le suivant (le caractère '\0'
est
représenté ici par une étoile) :
Descendre vers la gauche correspond à passer à la lettre
suivante dans le corps d'un mot ; descendre vers la droite
correspond à passer à une autre lettre en même position.
Dans cet exemple, le caractère '\0'
permet de
dire que ``ce'' est un mot
en même temps qu'une partie de ``ces'', alors que ``ca'' n'est pas
un mot, mais seulement une partie de ``cas''.
Types
Un dictionnaire sera donc représenté par un arbre
étiqueté par des char
. On pourra donc utiliser les
types de données définies au
TP 3 :
arbre
et ses constructeurs empty
et node
.
Manipulation du dictionnaire
- 1.
- Écrire une fonction
qui prend en arguments un mot et un dictionnaire et détermine
si oui ou non le mot est dans le dictionnaire ;
- 2.
- Écrire une fonction qui
crée un dictionnaire réduit à un mot ;
- 3.
- Écrire une fonction qui prend en arguments un mot et
un dictionnaire, et renvoie le dictionnaire enrichi de ce mot. Cette
fonction pourra utiliser la fonction précédente ;
Création du dictionnaire
Le dictionnaire sera créé à partir d'un fichier contenant
les mots du dictionnaire, un par ligne. On utilisera les fonctions
d'entrée sortie de haut niveau de la librairie stdio.h
.
Pour ouvrir un fichier en lecture, utiliser fopen(fichier,"r")
et fclose(fichier)
pour ouvrir et fermer les fichiers, et
fgets(buffer, size, file)
pour lire le fichier décrit
par file
(donné par fopen
) ligne par ligne.
La ligne courante est stockée dans la chaîne buffer
de
taille size
. Lire les man fopen
et
man fgets
pour en savoir plus.
- 4.
- Écrire une fonction qui lit les mots dans un fichier
et retourne le dictionnaire correspondant. Tester sur un petit
fichier (et imprimer le résultat
si vous avez écrit la procédure
affiche
la semaine
dernière).
- 5.
- Écrire une fonction qui demande des mots à
l'utilisateur et vérifie leur présence dans le dictionnaire.
On pourra tester le programme sur des dictionnaires plus conséquents,
par exemple le dictionnaire d'anglais de /usr/dict/words
, ou le
dictionnaire de francais de /usr/local/util/lib/words.french
.
Compaction du dictionnaire
Il est possible de réduire l'espace mémoire
occupé par un arbre binaire en partageant les
sous-arbres communs. Chaque fois que deux sous-arbres sont identiques,
l'un d'entre eux est détruit et remplacé par l'autre.
Exemple
Si le dictionnaire
se compose des mots ``mite'', ``rase'' et ``rate'', le dictionnaire et sa
version compactée seront représentés par :
Algorithme de compaction
La nouvelle structure de données s'appelle un DAG pour Directed
Acyclic Graph. Ce n'est pas exactement un arbre, mais on peut utiliser
exactement le même type de données, arbre
, et
les mêmes algorithmes de recherches de mots sans aucune modification.
La seule chose à faire est donc de compacter le dictionnaire grâce
à une fonction de compaction qui prend un arbre en argument et retourne
un ``arbre''. Cette fonction compacte le fils droit et le fils gauche, puis
cherche dans une liste si un sous-arbre avec le même label et les
mêmes fils a déjà été rencontré. Si
c'est la cas, elle retourne le sous-arbre déjà rencontré,
sinon, elle en crée un nouveau qu'elle rajoute à la liste
avant de le retourner.
- 6.
- L'algorithme de compaction utilise une liste de sous-arbres.
Écrire le type correspondant, ainsi que ses fonctions de construction.
- 7.
- Écrire la fonction de compaction récursive.
- 8.
- Écrire la fonction de compaction du dictionnaire qui
initialise la liste de sous-arbres, appelle la fonction récursive et
vide la liste des sous-arbres après usage. Tester sur un
dictionnaire (pas trop gros...) et imprimer le nombre de noeuds gagnés
par la compaction.
Étant donné la structure de données
utilisée pour stocker les sous-arbres déjà
rencontrés, le temps de compaction grandit très vite avec la
taille du dictionnaire. Il est possible d'améliorer substantiellement
le temps de recherche dans la liste des sous-arbres en la divisant en plusieurs
listes disjointes. L'idée est qu'on peut facilement, étant
donné un sous-arbre, trouver dans quelle sous-liste il doit se trouver.
Un facon de procéder consiste à séparer la liste selon
la hauteur des sous-arbres. On rappelle que la hauteur d'un arbre est 0 pour
un arbre vide, et 1 + la plus grande des hauteurs de ses fils sinon.
- 9.
- Modifier les fonctions de compaction pour qu'elles utilisent un
tableau de listes de sous-arbres au lieu d'une simple liste. La liste
numéro i ne sera remplie qu'avec des arbres de hauteur
i. Tester, cette fois sur un gros dictionnaire.
Pour améliorer encore la vitesse de compaction, on peut
remplacer la recherche dans la liste des sous-arbres par une structure
permettant une recherche plus rapide. On pourra essayer un arbre binaire de
recherche ou une table de hachage (voir les fonctions de
search.h
). Dans les deux cas, il faudra encore
associer un entier à chaque sous-arbre.