Dictionnaire optimise

Soyez le premier à donner votre avis sur cette source.

Vue 11 122 fois - Téléchargée 725 fois

Description

/// <summary>
/// Edité par Diallo Apha
/// aokdiallo@hotmail.com
/// Version du 13 Mars 2008
///
/// Cette Classe est L'implementation economique en memoire et en performace d'un dictionnaire.
/// En effet dans plusieurs applications telque les jeux de mots ou les editeurs de texte on a besoin d'un dictionnaire.
///
/// A -> Une premiere approche facile :
///
/// est de stocker dans un fichier tous les mots du dictionnaire.
/// Les problemes de cette approche sont :
/// 1 ->
/// la taille du fichier sera enorme
/// 2 ->
/// la recherche d'un mot est tres couteuse car à chaque fois il faut ouvrir le fichier et le parcourir en comparant à chaque fois le mot lut
/// avec le mot cherché.
///
/// B ->
/// Approche utiliséé dans ce projet :
///
/// le dictionnaire est une liste de noeuds.
/// chaque noeud represente une lettre et possede un lien ver d'autres noeuds
/// je m'explique :
/// par exemple le mot "AN" correspond au noeud('A') qui pointe vers le noeud ('N')qui à son tour pointe vers le noeud('\0')
/// '\0' representant le caractere de fin de mot.
/// là ou ça devient interessant c'est quand par exemple on veut ajouter les mots "ANE" et "ANES" dans le dico :
///
/// dans le cas de la premiere approche on aurait simplement ajouté ANE et ANES dans le fichier ce qui fait pour "AN" et "ANE" et "ANES" 9 caracteres.
///
/// dans la deuxieme approche on a deja le mot "AN" dans le dico donc il suffit de faire pointer le noeud (N) vers un nouveau noeud(E) puis
/// faire pointer le noeud (E) vers un nouveau noeud(\0) pour ANE.
/// ensuite
/// faire pointer le noeud (E) vers un nouveau noeud(S)
/// puis
/// faire pointer le noeud (S) vers un nouveau noeud(\0) pour ANES.
/// au final on a que 7 noeuds.
/// Voire la figure ci dessous :
/// A
/// |
/// \0<-N->E->\0
/// |
/// S->\0
/// mais le plus interessant à remarquer est que :
/// pour passer de An à ANE puis ANES on a rajouté 7 caracteres avec la premiere approche alors
/// qu'avec la deuxieme on n'en n'a rajouté que 4
/// on voit donc que le fait de reutiliser les lettres deja presentes nous fait enormement gagner en place memoire.
///
/// Ensuite pour verifier l'existance d'un mot avec la deuxieme approche c'est tres rapide
/// car on sais facilement trouver le noeud de la premiere lettre
/// du mot cherché.
/// à partir de là il suffit de tester les noeuds suivants en comparant les lettres avec celles du mot.
///
/// </summary>

Source / Exemple :


//dans le zip

Conclusion :


s'il il existe d'autres façons plus efficaces d'implementer un dictionnaire
Je suis preneur.

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
1
Date d'inscription
dimanche 24 novembre 2013
Statut
Membre
Dernière intervention
24 novembre 2013

Bonjour,

je cherche pour un jeu de type scrabble/anagrammes, comment trouver toutes les combinaisons possibles avec un nombre donné de lettres.

Pour l'instant, j'ai implementé une fonction qui ouvre un fichier texte contenant 311513 mots, chaque mot est lue l'un après l'autre et la fonction vérifie si ce mot peut être formé avec les lettres tirées précédement.
Cela fonctionne bien mais c'est lent (30 secondes sur un core I5 avec un SSD).

Je souhaiterais adapter cette fonction en utilisant le dictionnaire optimise : comment parcourir/lister tous les mots avec le dico optimisé ?

Cordialement.
Messages postés
10
Date d'inscription
lundi 24 novembre 2008
Statut
Membre
Dernière intervention
26 octobre 2010

oui:! merci...
Mais estt-ce je me déroute? je préfère que si l'utilisateur insère un mot, dès qu'il l'indique verbe, qu'il puisse directement insérer les mots relatifs aux conjuguaisons à tous les temps possibles, de à ce verbe. Exemple, si l'user insère le verbe 'manger', au moment où il est verbe, mon programme insère automatiquement les mots mangeais, mangerai etc grace aux méthodes appropriées. mais je me demande si en utilisant des classes adjectifs, adverbes, cela ralentirai l'application.
Messages postés
13
Date d'inscription
mardi 18 avril 2006
Statut
Membre
Dernière intervention
27 mars 2008

je pense qu'il faudrait déja créer une enum : public enum eWordType { Adjective, Verb, ... }
ensuite créer une propriété dans la classe Noeud : public eWordTpe? NodeType;
nullable pour que les noeud intermédiaires nepossedent pas de valeur mais que les noeuds finaux la possedent.
de plus il faudrait modifier les methodes d'insertion de mots pour qu'ils prennent en compte cette nouvelle valeur.
et pourquoi pas accélérer la recherche avec cette valeur...
d'ailleurs, les noeuds intermediaires devraient peutetre avoir une valeur combinée de l'enum contenant l'enssemble des sous-valeurs pour accélérer la recherche. mais à ce moment la, ca ralentirait l'insertion et modification. donc au choix ;)
Messages postés
10
Date d'inscription
lundi 24 novembre 2008
Statut
Membre
Dernière intervention
26 octobre 2010

heu bien bon,merci à vs. je trouve ce que je fais ici...
Voilà je voudrais un peu savoir comment pouvez vous faire en sorte que les mots soient classés, genre adjectif ou verbe ou nom. C'est à dire que je suis en train de réaliser un dictionnaire pareille mais je permets à l'utilisateur de préciser si le nouveau mot qu'il insère est un adjectif ou un verbe, un nom ect... comment aborderiez-vous ceci? un peu tard mais je vous crois connecté à ce sujet!
Messages postés
2
Date d'inscription
mercredi 19 mars 2003
Statut
Membre
Dernière intervention
31 juillet 2009

j'oubliais de preciser que si le mot existait deja alors on reiterais simplement sans rien faire, j'arrive avec cette methode a ajouter 250.000 mots en 2,6sec ce qui est puissant avec le language de flash qui n'est pas optimize!!
Afficher les 18 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.