Discussion :

[floopi51]

Bonjour,

Je recherche une méthode qui me permette de trouver rapidement une sous chaine ou une chaine dans un set de 40000 noms.

Si je fais une recherche du mot "tu", je veux que mon programme trouve "turquoise", "tortue", "tu" dans un "dictionnaire" figé c'est à dire que les données dans lesquelles la recherche est faite reste inchangées d'une exécution à une autre.

J'ai trouvé des informations sur l'algorithme de Boyer-Moore pour la recherche de sous-chaine.
j'ai aussi trouvé les arbres binaires mais étant donné que ma recherche doit porter sur une sous-chaine qui n'est pas forcément en début de mot, je ne pense pas que cela puisse me servir.
J'ai aussi pensé à une table de hash avec des listes chainées mais je ne vois pas sur quoi calculer ma clé de hash.

Quelqu'un peut-il m'orienter pour choisir une structure de données adaptée pour la recherche ?
Merci

[I_believe_in_code]

Après avoir lu cet article :

http://fr.wikipedia.org/wiki/Algorithme_de_Boyer-Moore

Ainsi que les autres cités dans "articles connexes"

Je crois pouvoir affirmer que tout ceci est très intéressant et répond sans doute à tes questions.

L'Algorithme de Boyer-Moore est basé sur une idée que je trouve géniale. Ne convient-il pas à ce que tu dois faire ?

[kwariz]

Bonsoir,

Une autre approche serait de construire un dictionnaire qui optimise les recherches partielles de lettres consécutives qui renvoient un ensemble de mots correspondants.
Il y a évidemment l'approche naïve (et peu efficace) qui consiste à construire un arbre n-aire qui factorise les préfixes (en anglais un trie). L'étape suivante est de passer en une représentation binaire (fils gauche, frère droit) et de factoriser au possible les suffixes (en anglais un DAWG). Puis tu peux essayer un GADDAG qui prend plus de place mais facilite les «accès en milieu de mots».
Il y a pas mal de doc et d'articles sur ce genre d'approche (citeseer et google scholar par exemple).

[sologne]

Bonjour,

comme tu a dis que tu recherche une "méthode", si tu peux placer tes mots dans une BDD alors ton problème peut se résoudre facilement avec une requête SQL :
Select * FROM les_mots WHERE mot like "*tu*"

C'est juste une proposition car je ne sais pas si tu as la possibilité d'utiliser une BDD.

[souviron34]

Bonjour,

comme tu a dis que tu recherche une "méthode", si tu peux placer tes mots dans une BDD alors ton problème peut se résoudre facilement avec une requête SQL :
Select * FROM les_mots WHERE mot like "*tu*"

C'est juste une proposition car je ne sais pas si tu as la possibilité d'utiliser une BDD.

juste pas très efficace, je pense, en termes d'optimisation...

[Trap D]

Bonjour

J'ai eu à faire ce genre de choses il y a une vingtaine d'années, avec une base de plusieurs dizaines de milliers de mots, qui ne changerait pas fréquemment.
J'ai indexé tous les mots de la base sur la premiere lettre, la seconde etc
Ce qui fait que j'ai 24 index et je recherche les chaînes comme je veux à partir de la premiere, la seconde... C'est très rapide.
Evidemment, et j'insiste, il ne faut pas que la base change tous les jours (quoique maintenant, l'indexation totale doit prendre moins d'une heure).

[souviron34]

je n'ai pas lu les aticles pointés, mais une idée comme ça, avec ta condition :

dans un "dictionnaire" figé c'est à dire que les données dans lesquelles la recherche est faite reste inchangées d'une exécution à une autre.

et si tu disposes d'un tant soit peu de mémoire

Un tableau 2D de 26 cases

• On passe une fois dans l'ensemble du dico
• Pour chaque lettre rencontrée, on stocke dans le tableau à l'indice correspondant la position en 2ième dimension

Ensuite, pour chercher une sous-chaine, on va directement à la première lettre. Puis pour chaque possiiblité, on regarde avec la deuxième (par exemple avec une recherche dichotomique dans son tableau de position). etc...

Non ??

Enfin je sais que c'est un sujet de recherche et de travail courant, donc peut-être mon idée est-elle trop nettement simpliste...