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...
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 :
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.
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...
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);
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 !
imprime_arbre
du
précédent TP, un peu modifiée).
FILE *
de l'entrée standard est
stdin
(voir stdio.h
)..
/usr/dict/words
, ou le
dictionnaire de francais de /usr/local/util/lib/words.french
.