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 :
arbre1 arbre2

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.