Un algorithme 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.
Un algorithme 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.
Ligne 5:
Ligne 5:
On utilise pour cela une structure de données arborescente, où chaque nœud de l'arbre est une étape de lecture et chaque arête correspond à la lecture d'une lettre. Les nœuds sont indexés par les lettres suivantes possibles du mot, avec un compteur par nœud pour savoir si celui-ci est final ou non (le nœud est final si le compteur est >0).
On utilise pour cela une structure de données arborescente, où chaque nœud de l'arbre est une étape de lecture et chaque arête correspond à la lecture d'une lettre. Les nœuds sont indexés par les lettres suivantes possibles du mot, avec un compteur par nœud pour savoir si celui-ci est final ou non (le nœud est final si le compteur est >0).
-
Le but de cet exercice est de construire un arbre de complétion à partir de mots de vocabulaire, puis de l'utiliser pour compléter un début de mot proposé par l'utilisateur.
+
Le but de cet exercice est de construire un arbre lexicographique à partir de mots de vocabulaire, puis de l'utiliser pour compléter un début de mot proposé par l'utilisateur.
-
Vous devez implémenter un arbre de complétion en Java pour gérer une base de mots et répondre à différentes requêtes, telles que l'insertion de mots, l'affichage de l'arbre, la suggestion de mots complets à partir d'un préfixe donné, etc.
+
Vous devez implémenter un arbre lexicographique en Java pour gérer une base de mots et répondre à différentes requêtes, telles que l'insertion de mots, l'affichage de l'arbre, la suggestion de mots complets à partir d'un préfixe donné, etc.
<note tip>
<note tip>
Ligne 26:
Ligne 26:
- ''noeud'' : un objet de type ''Noeud'' représentant le nœud suivant.
- ''noeud'' : un objet de type ''Noeud'' représentant le nœud suivant.
-
c. Pour initialiser un arbre de complétion, créer un nœud vide dont le ''compteur'' vaut 0 et dont la liste des arêtes est une liste (''ArrayList'') vide.
+
c. Pour initialiser un arbre lexicographique, créer un nœud vide dont le ''compteur'' vaut 0 et dont la liste des arêtes est une liste (''ArrayList'') vide.
=== 2. Fonction d'Insertion ===
=== 2. Fonction d'Insertion ===
-
Écrivez une méthode ''insererMot'' dans la classe ''Noeud'' pour insérer un mot dans l'arbre de complétion.
+
Écrivez une méthode ''insererMot'' dans la classe ''Noeud'' pour insérer un mot dans l'arbre.
* La fonction est récursive
* La fonction est récursive
* Elle prend comme argument une chaîne de caractères
* Elle prend comme argument une chaîne de caractères
Ligne 79:
Ligne 79:
c. Affichez l'arbre pour vérifier que les mots sont correctement insérés.
c. Affichez l'arbre pour vérifier que les mots sont correctement insérés.
+
+
<note tip> **Concaténation**
+
+
Vous pouvez créer une nouvelle chaîne qui combine le contenu de l'ancienne chaîne avec un nouveau caractère que vous souhaitez ajouter à la fin.
+
<code java>
+
String maChaine = "Hello";
+
char nouveauCaractere = '!';
+
maChaine = maChaine + nouveauCaractere; // Crée une nouvelle chaîne
ce qui peut être utile lorsque l'on veut examiner les caractères d'ue chaîne de caractrères un à un.
+
ce qui peut être utile lorsque l'on veut examiner les caractères d'une chaîne de caractères un à un.
exemple:
exemple:
Ligne 109:
Ligne 120:
=== 5. Fonction de Suggestion ===
=== 5. Fonction de Suggestion ===
-
Écrivez une méthode ''suivant'' dans la classe ''Noeud'' pour retourner une liste de mots complets à partir d'un préfixe donné. La fonction doit respecter les conditions suivantes :
+
a. Écrivez une méthode ''suivant'' dans la classe ''Noeud'' pour retourner une liste de mots complets à partir d'un préfixe donné. La fonction doit respecter les conditions suivantes :
* Elle doit utiliser une approche itérative de parcours de l'arbre jusqu'au nœud correspondant au préfixe.
* Elle doit utiliser une approche itérative de parcours de l'arbre jusqu'au nœud correspondant au préfixe.
* Elle doit faire appel à la fonction d'affichage du noeud atteint pour afficher l'ensemble des noeuds suivants
* Elle doit faire appel à la fonction d'affichage du noeud atteint pour afficher l'ensemble des noeuds suivants
-
d. Testez la fonction ''suivant'' avec les préfixe ''"bon"'', ''"ch"'', ''"pre"'', et affichez les résultats.
+
b. Testez la fonction ''suivant'' avec les préfixe ''"bon"'', ''"ch"'', ''"pre"'', et affichez les résultats.