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 (cette représentation s'appelle un trie de retrieval). L'arbre représentant le dictionnaire comporte des noeuds dont le nombre de fils est 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. Pour une recherche plus efficace, ces fils sont classés par ordre alphabétique. Le dictionnaire lui-même est (un pointeur sur) la liste des initiales de mots. Comme pour les chaînes de caractères en C, le caractère '\0' indique la fin d'un mot. Cela est nécessaire pour savoir quels préfixes d'un mot forment des mots du dictionnaire.

Pour représenter des arbres dont le nombre de fils peut varier, nous allons utiliser des arbres binaires interprétés de façon un peu particulière. L'idée est la suivante : chaque noeud de l'arbre binaire N est le fils d'un autre noeud P(sauf pour la racine). Le fils droit de N dans l'arbre binaire correspond au fils suivant de P dans l'arbre de départ, et le fils gauche de N dans l'arbre binaire correspond au premier de ses fils dans l'arbre de départ. Dans le cas du dictionnaire, donc, le fils droit est un pointeur vers une autre lettre possible en même position et le fils gauche est un pointeur vers la suite possible du mot.

Les choses seront plus claires sur un exemple...

1  Exemple

Si le dictionnaire se compose des mots ``cas'', ``ce'', ``ces'', ``ci'', ``de'' ``des'' et ``do'', l'arborescence sera la suivante :

Pour traduire en arbre binaire, il suffit de bouger certaines flèches :

Puis, de tourner un peu l'arbre pour avoir une vision d'arbre binaire classique :
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''.

Notez bien que pour une plus grande efficacité, les lettres qui se suivent de fils droit en fils droit sont ordonnés.

2  Types

Un dictionnaire sera donc représenté par un arbre étiqueté par des char. On pourrait donc utiliser les types de données définis au TP 3 : arbre et son constructeur noeud. Toutefois, je conseillerais de modifier légèrement ce type de la façon suivante : changez le nom du champ gauche en fils et du champ droite en frere. Cela pourra vous simplifier un peu la programmation...

3  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 ;
Solution
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 .

4  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 pour le fermer, fclose(file). La fonction fopen renvoie un FILE * qui est utilisé pour les fonctions de lecture. Pour lire les caractères, on peut utiliser fgetc(file). Par exemple, une boucle pour lire tous les caractères d'un fichier :
int c;
FILE *file;
file = fopen("fichier","r"); //ou a la place de "fichier" une variable char *
while( (c=fgetc(file))!=EOF ){
/* faites de c ce que vous voulez
*/
}
fclose(file);
4.
Écrire une fonction int lire_ligne(FILE *f, char *buffer) qui lit une ligne entière et met le mot correspondant dans buffer (sans oublier le \0 final). Attention à la mémoire !
Solution
5.
É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 en utilisant la procédure imprime_arbre du précédent TP, un peu modifiée).
6.
Écrire une fonction qui demande des mots à l'utilisateur et vérifie leur présence dans le dictionnaire. On rappelle que le FILE * de l'entrée standard est stdin (voir stdio.h)..
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.