| 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/05 09:42] – 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 |
| char[] tableauDeCaracteres = maChaine.toCharArray(); | char[] tableauDeCaracteres = maChaine.toCharArray(); |
| </code> | </code> |
| ce qui peut être utile lorsque l'on veut examiner les caractères d'une 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: |