Arbre de complétion

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un arbre de complétion est un mécanisme logique permettant d'anticiper la saisie et de proposer des mots automatiquement pour faciliter les recherches dans un formulaire sur une page web par exemple.

Description[modifier | modifier le code]

Un moyen efficace de réaliser une autocomplétion (un « complètement ») est d'utiliser une structure de données arborescente, où chaque nœud de l'arbre est une lettre, ses nœuds enfants les lettres suivantes possibles du mot, avec un indicateur par lettre pour savoir si celle-ci est finale ou non.

Construire le dictionnaire[modifier | modifier le code]

Exemple d'arbre à complétion.

Sur le dessin il est représenté un arbre contenant 4 mots : "art", "arbre", "des", "dessin". On peut remarquer que :

  • la racine de l'arbre ne porte aucune lettre ;
  • chaque niveau de l'arbre correspond à une position dans le mot ;
  • un nœud contient une information de nature binaire pour indiquer si la lettre est finale ou non ;
  • chaque nœud peut avoir autant de fils que nécessaire (on parle d'arbre n-aire).

Algorithme d'ajout d'un mot dans le dictionnaire :

i est un entier
mot est une chaîne
lettre est un caractère

i <- 1
Tant que i < longueur(mot) Faire
    lettre <- mot[i]
    Si nœud courant est vide Alors
        nœud courant <- nouveau nœud(lettre)
    Sinon Si nœud courant ne contient pas la même lettre Alors
        nœud courant <- frere de nœud courant contenant la lettre
    Fin Si
    nœud courant <- fils de nœud courant
Fin tant que

L'implémentation d'un tel algorithme est simplifié par l'utilisation d'une fonction récursive.

Compléter un début de mot[modifier | modifier le code]

On propose un début de mot, c'est-à-dire un certain nombre de lettres (par exemple 3). Il suffit de "plonger" dans l'arbre lettre à lettre, puis, une fois la fin du mot proposé trouvé, continuer le parcours jusqu'à une lettre finale.

Uml arbre complétion

Exemple d'implémentation en C++[modifier | modifier le code]

Le langage C++, à la fois par la manipulation de pointeurs et au paradigme objet, est un langage tout à fait approprié à l'implémentation d'un tel algorithme. L'exemple est aisément transposable en C (en remplaçant les classes par des structures, et en ajoutant un paramètre aux fonctions), en Java, en Delphi, en C#, ou dans tout autre langage du même type.

Déclarations des classes[modifier | modifier le code]

Deux classes vont être nécessaires : une représentant le nœud de l'arbre, une représentant l'arbre lui-même.

Comme attributs, une lettre (type char en C++) et un booléen suffisent. Les compositions sont représentées en C++ par des pointeurs (type nœud*) : un pour le fils, un pour le frère. Par convention, un pointeur valant 0 (NULL) représente un lien vide. Comme opérations, nous trouverons, outre le constructeur et le destructeur (obligatoire à cause de la composition, pour libérer la mémoire), une fonction pour ajouter un mot (type std::string en C++) et une fonction pour compléter.

Les deux attributs (tailleMini et tailleMaxi) sont facultatifs et ne servent qu'à restreindre la complétion. La composition sur la racine de l'arbre utilise ici aussi un pointeur de nœud.

Code des constructeurs[modifier | modifier le code]

Le constructeur de nœud initialise ses attributs :

nœud::nœud(char let, bool fin)
	: lettre(let), final(fin), fils(0), frere(0)
{
 
}

De même pour celui de l'arbre :

Lexique::Lexique(int mini, int maxi) 
   : racine(0), tailleMini(mini), tailleMaxi(maxi)
{
}

Code de l'ajout de mot[modifier | modifier le code]

Pour l'arbre, la fonction d'ajout se contente de transmettre à la racine :

void Lexique::Ajoute(const std::string& mot)
{
	assert(mot.length()>0);
	if(!racine)
		racine = new nœud(mot[0],mot.length()==1);
 
	racine->Ajoute(mot,mot.length(),0);
}

Pour le nœud, la fonction est récursive :

Code des fonctions de complétion[modifier | modifier le code]

La fonction suivante va transmettre à la racine de l'arbre (si elle existe) les informations nécessaires à la complétion.

bool Lexique::Complete(const std::string& mot, std::list<std::string>& mots) const
{
	std::string temp=mot;
	if(racine && mot.length()>=tailleMini)
		racine->Complete(mot,mots,0,temp,tailleMaxi);
	return !mots.empty();
}

Pour la classe de nœud, la fonction est elle aussi récursive

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]