Discussion :

[ryosnake]

Bonjour,

Je souhaiterai implémenter un algo de recherche qui me renverrai true si il a trouvé la chaine de caractère que je lui ai passé en paramètre dans ma base de donnée de mots.(une sorte de dictionnaire).

Il faut que ça soit le plus optimiser possible, donc très rapide tout en requierant le minimum d'espace mémoire. (je sais, c'est beau de rèver )

Et également, comment organiser la base de donnée pour qu'elle soit optimiser pour l'algorithme. Par exemple, ranger les mots par leur longueur et en plus dans l'ordre alphabétique?

Merci par avance.

PS:Attention, je parle bien de chaine et pas de sous-chaine, il faut, si il existe qu'il me trouve le mot recherché pil poil tel que je lui ai donné

[ToTo13]

Bonjour,

ce que tu demandes est implémenté dans les dictionnaires electroniques : une table de hashage !!!

- Recherche en O(1).

[ryosnake]

ok, merci, mais je pensais plutôt utiliser un vecteur dynamique car une table de hachage c'est pour faire un vrai dictionnaire, genre mot / définition. Quand j'ai parlé d'une sorte de dictionnaire, je voulais dire, juste des mots.

[jobherzt]

de memoire, pour avoir un resultat optimal il faut transformer la chaine a rechercher en un automate fini. par exemple, si tu recherche dans un texte une chaine sans repetiton, tu peux passer en O(n) facilement. exemple : chercher abc dans ababc.



tu compares a et a, c'est bon, tu compare b et b c'est bon. tu compares c et a, la ca coince. dans l'approche naive, tu te decalerais jste d'un cran, et tu comparerais a et b, or comme tu sais qu'il n'y a pas 2 lettres identiques dans la chaine recherhée, tu pex directement passer a la comparaison de a et a... c'est pas clair ?? j'essaie de detailler.

1
a b a b c
a b c -> pas bon

2
a b a b c
a b c -> pas bon, mais tu le savais deja vu que a!=b donc tu pouvais passer direct a

2 bis
a b a b c
a b c -> c'est bon, soit 2 etapes au lieu de 3.

en gros, tu n'a jamais a revenir en arriere.

l'idee est donc d'etendre ca en transformant ta chaine en automate pour sauter des etapes.

[ryosnake]

oui, ok, mais moi, c'est plus simple que ça puisque je ne cherche pas une sous-chaine dans une chaine, je veux juste savoir si le mot que je passe en paramètre est dans ma base de mots.

si j'envois le mot abc, et que je rencontre le mot abca ou dabc, c'est pas bon, c'est bon que quand je rencontre abc et rien d'autre.

Là où je me pause des questions, c'est sur la manière de ranger ma base et comment faire mes recherches, sachant que j'aurai des milliers de mots et il faut donc que ça soit le plus optimisé possible.

On pourrai juste les ranger par ordre alphabétique, puis chercher dedans, mais je pensais à ranger mes mots par leur longueurs, et chaque groupe de mots de même longueurs serait rangés dans l'ordre alphabétique, déjà, cela pourrait certainement améliorer la recherche, puisqu'on récupere la longueur du mot passer en parametre et on cherhche dans le bon groupe.

Maintenant, je me demande dans quoi stocker ma base (vecteur dynamique?) et quel algo serait le plus approprié pour la recherche.

[startout]

Les meilleurs moteurs de recherche sont basés sur les expressions régulière il me semble...