Dictionnaires : comment les implémenter ?

Bonjour tout le monde je suis nouveau sur le forum et j'espère que je suis tombé sur le bon. J'ai toujours été fasciné par les dictionnaires. ça fait longtemps que je cherche les méthodes dont les ils sont programmés: certains proposent des structures sous forme d'arbre arbre naire mais je pense que ces dernières consomment trop de mémoire dès que le contenu devient important par ailleurs je ne sais pas si on utilise une boucle de recherche qui a aussi le problème du temps de recherche.
ma question est-ce que vous pouvez m'aider à comprendre comment sont programmés le dictionnaire pratiquement.
Je vous remercie d'avance.

Bonjour,
une structure particulièrement compacte pour stocker un lexique est le graphe dirigé acyclique, DAG pour les intimes. On préfère le terme de lexique (liste de mots) à dictionnaire (liste d'entrée avec des informations attachées).
Un DAG est une structure compacte car il profite d'une sorte de factorisation des préfixes et des suffixes. Pour obtenir un DAG ce n'est pas trop trop compliqué, tout va dépendre de ton niveau en algo. On part d'un arbre n-aire qu'on implémente sous forme binaire (classiquement fils gauche-frère droit). Une fois cet arbre construit on peut le réduire en cherchant les sous-arbres identiques avec une recherche bottom top et en les fusionnant. On arrive à une structure nommée DAWG (direced acyclic word graph) utilisé dans de nombreux jeux de mots.
Pour les jeux de mots où on peut «construire» un mot à partir du milieu (comme au scrabble) et en s'attachant à d'autres mots il y a ce qu'on appelle un GADDAG, le DAG va non seulement contenir les mots «normaux» mais aussi les mots décalés.
Je pense que tu as déjà pas mal de sources d'infos à creuser :) N'hésite pas si tu as d'autres questions.

:salut:

Si tu parles de la structure de données, tu pourrais trouver des éléments de réponse dans http://tcuvelier.developpez.com/tuto...es-donnees/#LV.

Bonjour je trouve que finalement la définition de dictionnaire dans la programmation inclus tout type de donnee, moi je m'intéresse précisément au dictionnaire de définition linguistique où on a pas besoin d'insérer souvent des informations on a plutôt besoin de consulter juste la définition. Avec les arbres naire de 26 liaison chaqune pour une dixaine de niveu (mot le plus long ) alors la j'aurai besoin de la memoir du silicon valey. j' ai ponsé a supprimer les pointeurs non utilisés cequi reviens a creer une classe neud qui a just le nombre d'attributs necessaire (je ne sais pas si ca existe??? )
Ou comment on fait pour reduir ces blancs car pour les supprimer il faut d'abord creer la totalite du dictionnaire qui est enorme.
Merci

Non, le vocabulaire est trompeur. Ce qu'en jargon informatique français on appelle dictionnaire est une structure de donnée particulière qui à une clé associe une ou plusieurs valeurs, en anglais on parlera de map en général et parfois de dictionary.

Relis mon message qui fait la distinction entre un lexique et un dictionnaire. J'ai bien compris que tu parlais de lexique et que ta question portait sur une implémentation informatique d'un lexique. Tu surestimes énormément la taille d'un lexique en tant que tel et sa taille implémentée.

Prenons le lexique ODS7 (officiel du scrabble 7ème édition). Il contient 393670 mots de 2 à 15 lettres. Le fichier fait 4.2Mo, autant dire que de nos jours c'est peanuts. Même si tu ne fais pas attention à ton implémentation et en étant très large, la structure en mémoire ne devrait pas dépasser la bonne centaine de Mo, ce qui est toujours de nos jours sur les plateformes classiques peanuts.
Une implémentation avec un DAWG permet de tout faire tenir dans quelques Mo, car on tire profit de la redondance naturelle des langues (en français beaucoup de pluriels se forment en s, les verbes du 1er groupe on souvent les même terminaisons, …).