Représentation d'un dictionnaire
Discutez d'informatique ici !
-
informix
- Membre Naturel
- Messages: 79
- Enregistré le: 04 Nov 2007, 17:49
-
par informix » 04 Nov 2007, 17:59
Bonjour à tous,
je veux savoir quelle est la structure de donnée la plus adéquate pour representer un dictionnaire de mot dans la mémoire de l'ordinateur (arbre, liste etc...)
Merci
-
Joker62
- Membre Transcendant
- Messages: 5028
- Enregistré le: 24 Déc 2006, 20:29
-
par Joker62 » 04 Nov 2007, 18:36
Une liste de structure de données je dirais :)
-
olivthill
- Membre Relatif
- Messages: 349
- Enregistré le: 21 Avr 2006, 18:17
-
par olivthill » 04 Nov 2007, 19:24
On peut représenter un dictionnaire avec presque n'importe quelle structure de données.
Cela peut-être une simple liste, mais c'est un peu long à balayer, sauf si la liste est triée et qu'il est possible de faire une recherche dicotomique , donc avec des tailles fixes pour les mots.
Un arbre équilibré est une structure qui est très employée pour les index de toutes sortes, et la liste des entrées d'un dictionnaire peut être considérée comme étant un index.
La structure la plus performante est une table de hachage, quand elle est bien optimisée, c'est-à-dire avec un algorithme qui minimise les collisions, et que l'on peut élaborer à partir de statistiques dans le cas où le dictionnaire est statique.
Pour les besoins d'une saisie semi-automatique, j'avais été amené à utiliser une autre structure, qui était une arborescence de listes chaînées, où chaque noeud représentait une lettre. Cela permettait de retrouver très vite tous les mots débutants par quelques lettres.
Bref, tout dépend du type de dictionnaire et de l'usage que l'on souhaite en faire.
-
informix
- Membre Naturel
- Messages: 79
- Enregistré le: 04 Nov 2007, 17:49
-
par informix » 04 Nov 2007, 19:24
Joker62 a écrit:Une liste de structure de données je dirais
:--: drôle
-
informix
- Membre Naturel
- Messages: 79
- Enregistré le: 04 Nov 2007, 17:49
-
par informix » 04 Nov 2007, 19:30
olivthill a écrit:On peut représenter un dictionnaire avec presque n'importe quelle structure de données.
Cela peut-être une simple liste, mais c'est un peu long à balayer, sauf si la liste est triée et qu'il est possible de faire une recherche dicotomique , donc avec des tailles fixes pour les mots.
Un arbre équilibré est une structure qui est très employée pour les index de toutes sortes, et la liste des entrées d'un dictionnaire peut être considérée comme étant un index.
La structure la plus performante est une table de hachage, quand elle est bien optimisée, c'est-à-dire avec un algorithme qui minimise les collisions, et que l'on peut élaborer à partir de statistiques dans le cas où le dictionnaire est statique.
Pour les besoins d'une saisie semi-automatique, j'avais été amené à utiliser une autre structure, qui était une arborescence de listes chaînées, où chaque noeud représentait une lettre. Cela permettait de retrouver très vite tous les mots débutants par quelques lettres.
Bref, tout dépend du type de dictionnaire et de l'usage que l'on souhaite en faire.
Merci bcp pour l'explication.
Pour un éditeur de texte à complétion automatique de suffixes, je pense que la structure de données la plus adéqute est l'arbre binaire / transformation d'un arbre N-aire en arbre binaire. LEs noeuds devraient etre des lettres. Dans ce cas, un mot du dictionnaire n'est pas forcément une séquence de noeud liés entre eux (branche)...
Pour la table de hachage, je dois me documenter dessus. Je ne l'ai jamais utilisée. C'est une occasion pour la découvrir.
a+
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 5 invités