| Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente |
| tc_info:2023-tp-texte [2023/12/04 22:28] – edauce | tc_info:2023-tp-texte [2024/12/03 23:53] (Version actuelle) – edauce |
|---|
| ==== Arbre de complétion ==== | ==== Arbre lexicographique ==== |
| |
| 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. |
| 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> |
| - ''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 |
| <note tip> | <note tip> |
| * **Cas terminal** : | * **Cas terminal** : |
| Si le mot est vide, cela signifie que tous les caractères du mot ont été insérés. Dans ce cas, on met à jour l'attribut estTerminal du nœud actuel à true (pour indiquer que c'est la fin d'un mot) et on incrémente le compteur associé. | Si le mot est vide, cela signifie que tous les caractères du mot ont été insérés. Dans ce cas, on met à jour l'attribut ''terminal'' du nœud actuel à ''true'' (pour indiquer que c'est la fin d'un mot) et on incrémente le compteur associé. |
| |
| * **Cas Récursif** : | * **Cas Récursif** : |
| * Elle doit afficher chaque mot complet trouvé ainsi que son compteur. | * Elle doit afficher chaque mot complet trouvé ainsi que son compteur. |
| |
| 3.2 **Tests** | 3.2 Tests |
| |
| a. Créez un arbre de complétion vide. | a. Créez un arbre de complétion vide. |
| | |
| 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 |
| | </code> |
| | </note> |
| | |
| |
| === 4. Fonction d'Appartenance === | === 4. Fonction d'Appartenance === |
| |
| b. Testez la fonction ''appartient'' avec les mots ''"chat"'', ''"maison"'', ''"soirée"'' et ''"bon"'', et affichez le résultat pour chaque test. | b. Testez la fonction ''appartient'' avec les mots ''"chat"'', ''"maison"'', ''"soirée"'' et ''"bon"'', et affichez le résultat pour chaque test. |
| | |
| | <note> **la méthode ''toCharArray''** |
| | |
| | La méthode ''toCharArray()'' de la classe ''String'' en Java retourne un tableau de caractères qui représente la séquence de caractères de la chaîne. |
| | <code java> |
| | String maChaine = "Java"; |
| | char[] tableauDeCaracteres = maChaine.toCharArray(); |
| | </code> |
| | ce qui peut être utile lorsque l'on veut examiner les caractères d'une chaîne de caractères un à un. |
| | |
| | exemple: |
| | <code java> |
| | for (char c : maChaine.toCharArray()) { |
| | ... |
| | } |
| | </code> |
| | est une boucle permettant de parcourir un à un tous les caractères d'une chaîne. |
| | </note> |
| |
| |
| === 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. |
| |
| |