Application au 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.

Exemple d'un dictionnaire qui se compose des mots "cas", "ce", "ces", "ci", "de", "des" et "do":

$$\epsfig{file=arbor}$$

Chaque noeud est valué par une lettre (de type char) d'un mot du dictionnaire et a pour fils les lettres qui peuvent suivre. Pour une recherche plus efficace, ces fils sont classés par ordre alphabétique. Comme pour les chaînes de caractères en C, le caractère '\0' indique la fin d'un mot (en CAML, ce caractère se note '\000').

Pour représenter des arbres dont le nombre de fils est variable, nous allons utiliser des arbres binaires interprétés de façon un peu particulière.

L'idée est la suivante:

chaque noeud $N$ de l'arbre binaire 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 valué par une autre lettre possible en même position et le fils gauche est valué par la lettre suivante du mot.

Exemple:

Pour traduire en arbre binaire l'arbre précédent, il suffit de bouger certaines flèches :

$$\epsfig{file=arbor-bin1}$$

Puis, de tourner un peu l'arbre pour avoir une vision d'arbre binaire classique :

$$\epsfig{file=arbor-bin2}$$

Descendre vers la gauche correspond à passer à la lettre suivante 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".

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