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...

[Jean-Marc.Bourguet]

Est-ce que tu as regardé les tries.

[borisd]

J'ai déjà vu utiliser une structure en arbre (chaque noeud représente une lettre, on a un indicateur sur chacun pour savoir si un mot se termine en ce noeud, la profondeur correspond à la position de la lettre dans le mot).
Bref, je ne me souviens plus du nom en français ("écorché" ? pas retrouvé sur google), mais ça ressemble beaucoup au lien que propose Jean Marc Bourguet.
Pour ce qui est de la table de hashage, arriver à une complexité en O(1) me paraît très suspect??

[lyxthe]

Juste pour confirmer que dans une table de hachage la recherche de l'existance d'un élément est bel et bien en O(1) vu qu'il recherche l'élément en codant la clef et qu'il peut retrouver de façon immédiate si cette clef se trouve dans la table. C'est bien du O(1)
De plus moi je te dirai pour ton problème si tu ne veux pas utiliser de table de hachage (qui me parait être pourtant une bonne idée) de trier ta table tout d'abord en fonction de la taille des mots, puis dans l'ordre alphabétique pour les mots de même longueure, et comme ça quand tu recherche un mot, tu fais une dichotomie rapide sur la partie de la table dont les mots ont la même longueure que celui que tu recherches. Complexité de la recherche O(log(n)) et encore vu que tu ferais une recherche uniquement le nombre de mots de même longueure que le tien.
Enfin je pense qu'il y a mieux, vu que le tri serait pas mal conséquent à mettre en oeuvre, mais pour la recherche c pas trop mal.

[jobherzt]

il peut retrouver de façon immédiate si cette clef se trouve dans la table.

je ne vois pas trop comment retrouver ca de facon "immediate".... si j'ai 50 000 clé et que je recherche un element, va bien falloir que je fasse quelque comparaison par ci par la... bref c'est bien beau de coder l'element a chercher et de passer par la cle, il y a bien des cas ou ca accelere, mais ca ne change rien au fait que tu doives faire une rechercher, le bon element ne sort pas par magie

[lyxthe]

de mémoire dans une table de hashage, c'est comme si t'avais un tableau derriere dont seule les cases correspondant au numéro de la clef sont remplies. Dans un tableau normal tu peux accéder directement à la case numéro 10. genre y = T[10] se fait en O(1). Et bien dans une table de hachage, y=T['toto'] se fait en O(1) aussi. Donc savoir si 'Toto' est une clef de la table se fait aussi en O(1). donc si tu places tes mots en tant que clefs de la table, tu sais directement si un mot est présent.
Enfin je crois, je suis pas super sur de moi mais il me semble que c'est comme ça que ça se passe dans les tableaux associatifs et dans les tables de hachage

[borisd]

Un petit exemple pour expliquer la raison de mon doute : si ton algo de hashage code associe un nombre de 128 bits à ton mot et que tu veux avoir une case par valeur, alors il te faudra 2^128 cases à ton tableau pour une complexité en O(1).
Sans compter par ailleurs le coût de ta fonction de hashage...

[jobherzt]

en fait, pour qu'on ai du O(1), il faudrait avoir plus ou moins une correspondance exacte entre une clé et une adresse memoire.. ce qui est surment possible dans certaine cas particulier, mais pas du tout en général.

[Jedai]

On a du O(1) en amorti avec une bonne fonction de hachage et un ensemble de clé qui n'est pas spécifiquement conçu pour tirer parti de cette fonction de hachage... Si on connait d'avance l'ensemble des clés, il est même possible de calculer une fonction de hachage parfaite, où toute les clés ont des hachages distincts. Bien sûr, il s'agit de O(1) en nombre d'accès à la table, le calcul de la fonction de hachage en lui-même est en O(n) par rapport à la longueur de la clé.

Néanmoins dans le cas particulier d'un ensemble de mots, un trie me paraît une très bonne solution également.

(les tables de hachages ont différentes stratégies pour gérer les cas de collision, par exemple chaque emplacement contient une liste chaînée de paires (clé,valeur), les collisions ralentissent la structure, mais avec une bonne fonction de hachage et une taille du tableau sous-jacent raisonnable, les collisions sont très rares)

--
Jedaï

[borisd]

Si on connait d'avance l'ensemble des clés, il est même possible de calculer une fonction de hachage parfaite, où toute les clés ont des hachages distincts.

Si j'ai bien compris, une fonction de recherche de la position selon un critère de tri d'une clé parmi toutes les possibles est alors considérée comme un fonction de hashage parfaite (association clé<->No ordre)!
Par curiosité, est-il possible de faire mieux dans le cas général ? (et cette question a-t-elle un sens ??)

[lyxthe]

T'auras beau chercher, dans l'informatique et l'algorithmie normale (tant que les physiciens n'interviennent pas avec leur ordinateur quantique ou autre :p ), tu n'auras jamais mieux qu'un accés immédiat (donc en O(1)) à une donnée. Après c'est au niveau matériel que ça joue. Mais au niveau compléxité O(1) c'est le mieux vu que c'est immédiat....Enfin si j'ai bien compris ta question

[borisd]

En fait, c'est au niveau de la correspondance fonction de hashage<->fonction de recherche que je pensais.
Une fonction de hashage "idéale" (accès en O(1)) semble limitée dans le cas général dans sa complexité à la complexité de recherche d'un élément dans un ensemble sous une relation d'ordre total (log(n)?) au minimum.
Mais je me comprends...

[lyxthe]

Si je dis pas de bêtise, je crois que tu confonds, sinon c'est moi qui confond :p , toujours est-il que la fonction de hashage ne trouve pas un resultat en O(1), la fonction de hashage code ta clef. Une fonction de hashage idéale codera tes clefs de tels façon qu'il n'y aura pas besoin de gérer les éventuels doublons de clef. Mais c'est bien ta fonction de recherche qui se fait en O(1) pour une fonction de hashage parfaite justement parce qu'il n'y a pas de doublons de clefs. (Enfin je sais qu'il ne peut pas y avoir de doublon de clefs de toute façon, ce que je veux dire c'est qu'il n'y a pas possibilité pour la fonction de hashage de renvoyer deux fois le même résultats pour deux mots différents si elle est parfaite). J'espere m'être fait comprendre.
Quoiqu'il en soit, que la fonction de hashage soit parfaite ou non, une recherche dans une Hash table se fera en quasi O(1) plus une broutille pour les cas où la fonction de hashage renvoit deux valeurs identiques pour deux mots différents.
Alors effectivement la recherche dans une hash table pourrie avec une fonction de hashage la pire qu'on puisse imaginer et qui donnerait toujours le même résultat quelque soit le mot à coder, peut bel et bien prendre n opérations, mais ça n'arrive pas. L'accés à une donnée dans une table de hashage est considéré comme étant un accés en O(1) quelque soit la fonction.

A moins que je ne m'embrouille .... ?

[borisd]

J'ai très bien compris, mais ma remarque n'est pas très clairement exprimée (pourtant il paraît que qui se conçoit bien s'énonce clairement, donc le doute subsiste ). J'ai bien fait la distinction entre complexité de l'accès et complexité de calcul du hashage, ce que tu sembles ne pas faire.
Quoiqu'il en soit, ça n'a pas grand rapport avec la question initiale, qui a reçu une réponse appropriée.

[Jedai]

En fait, c'est au niveau de la correspondance fonction de hashage<->fonction de recherche que je pensais.
Une fonction de hashage "idéale" (accès en O(1)) semble limitée dans le cas général dans sa complexité à la complexité de recherche d'un élément dans un ensemble sous une relation d'ordre total (log(n)?) au minimum.
Mais je me comprends...

Tu es bien le seul, exprime toi clairement !!

Je cite les morceaux de ta phrase dépourvus de sens :
"limitée dans sa complexité à la complexité de..." ??
"la complexité de recherche d'un élément dans un ensemble sous une relation d'ordre total" ?? Elle dépend de la structure de donnée (un "ensemble" peut-être représenté de diverses façons), et peut aller de O(1) à O(n) (n étant le nombre d'éléments de l'ensemble).
"Relation d'ordre total (log(n))" ?? Qu'est que ce log(n) fout là ? Si c'est une complexité, met au moins un o() ou un O().

--
Jedaï