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 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...
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.
Types
Un dictionnaire sera donc représenté par un arbre
étiqueté par des char
. On pourra donc utiliser les
types de données définis au
TP 3 :
arbre
et son constructeur noeud
.
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 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 ){
/* faite 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 !
- 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
si vous avez écrit la procédure
imprime_arbre
au
précédent TP).
- 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
.
Corrigé
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.
Dans le cas du dictionnaire, la représentation arborescente permet de
partager les préfixe, et la compaction permet de partager les suffixes.
Exemple
Le dictionnaire précédent compacté :
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.
- 7.
- L'algorithme de compaction utilise une liste de sous-arbres.
Écrire le type correspondant, ainsi que ses fonctions de construction.
- 8.
- Écrire la fonction de compaction récursive.
- 9.
- É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.
- 10.
- 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.
Compaction à la volée
- 11.
- Plutôt que de construire le dictionnaire puis de le compacter, il
est mieux de le construire déjà compacté. Indication : il suffit de
modifier légèrement le constructeur pour ne construire que des noeuds
unique, les autres algorithmes restant inchangés...