[PHP + MySQL] Rechercher des mot ressemblants

comment ça ?

Dans mon exemple, ça ne fait qur 4 requêtes.
Je suis d'accord que ça fait en général n+1 requêtes pour un mot de n lettres, mais ce n'est pas infini. non ?
(ou au pire 26*n+1 si tu recherche chaque caractèredans l'étoile).

Salut,

Je ne suis pas d'accord avec ekra...
Cela représente tres vite enormement de calculs de cehrecher toutes les combinaisons de lettres:

Si on reprend ton exemple de CCM cela fait 26 lettres possibles pour chacune des 3 lettres soit 26^3=17576 combinaisons, c'est un algorithme exponentiel (par ex pour 5 lettres on est deja a presque 12 millions de combinaisons) sans compter que tu n'as pas resolu le probleme puisqu il faut que tu tries celles que tu vas garder!

Il n'y a malheureusement pas de solution simple a ton probleme (de classe NP) si tu veux tous les mots possibles a partir d une racine.

La seule maniere d'obtenir un résultat satisfaisant (en dehors de techniques d intelligence artificielle) est de commencer par indexer (sans doublon) les mots de ton site dans un arbre de recherche (pour limiter l espace des solutions) puis de suivre cet arbre au fur et a mesure de la saisie de l utilisateur.

NB: un arbre de recherche dans ton cas sera forme :
- une racine unique (point de depart) qui aura comme fils toutes les 1eres lettres des mots de ton index.
-chacune des lettres aura comme fils toutes les lettres trouvees à la position suivante dans ton index
- etc...
- il faudra avoir un marqueur pour indiquer qu'un mot se termine (par ex un booleen).

Ce qui donne pour "abc", "avec" et "avoir":

        *
        |
        a
      /  \
     b    v
   /     /  \
  c     e    o
        |    |
        c    i
             |
             r

Tu peux ainsi presenter pour chaque nouvelle lettre saisie tous les mots qui correspondent:
en tapant "a" on aura: "abc", "avec" et "avoir"
en tapant "av" on aura : "avec" et "avoir"
en tapant "avo" on aura: "avoir".

Good luck

Si on reprend ton exemple de CCM cela fait 26 lettres possibles pour chacune des 3 lettres soit 26^3=17576 combinaisons, c'est un algorithme exponentiel (par ex pour 5 lettres on est deja a presque 12 millions de combinaisons) sans compter que tu n'as pas resolu le probleme puisqu il faut que tu tries celles que tu vas garder!

Je ne suis pas d'accord, mon algorithme est linéaire en fonction du nombre de lettres et non exponentiel.
Je ne cherche pas les requêtes de AAA à ZZZ (qui là feraient 26^3), mais de :

-ACM à ZCM (26 cas car seule la première lettre est un paramètre)
-CAM à CZM (26 cas car seule la deuxième lettre est un paramètre)
-CCA à CCZ (26 cas car seule la troisième lettre est un paramètre)
Donc 26*n
Et en enregistrant le nombre de réponse à chaque requête, il suffit de proposer la 'frappe' qui a renvoyé le plus de réponse

Celà dit, je n'ai pas dit que j'avais le bon algorithme

Tu peux ainsi presenter pour chaque nouvelle lettre saisie tous les mots qui correspondent:
en tapant "a" on aura: "abc", "avec" et "avoir"
en tapant "av" on aura : "avec" et "avoir"
en tapant "avo" on aura: "avoir".

Si tu tape avoc pour avec, c'est mort ...

Salut,

Malheureusement, je suis tout a fait sûr de ce que j avance...

Le fonctionnement de ta proposition presuppose que tu sais d'avance que l'utilisateur fera une seule faute par mot:
- si l'on reprend l'exemple de "avoc" pour "avec", tu n'auras ta réponse que pour la requete "av*c", en revanche si l'utilisateur cherche en effet "avoir"... pas de réponse correcte
-dans la methode que je propose, rien se s'opose à ce que le resultat "avec" soit retourné dans la liste des réponses possibles, il suffit de parcourir l'arbre en evaluant la possibilité d'avoir une erreur à chaque emplacement, dans ce parcours ton espace de test sera de toute façon limité par celui des lettres présentes à cette position dans un des mots de l'index, ce qui sera de tout façon moins coûteux que de le faire pour chaque lettre de l'alphabet (dans ce cas on cherchera les mots commençant par "av" avec un "c" en 4eme position parmi "avoir" et "avec" soit deux comparaisons au lieu de 26 sans compter les accents et éventuellement les majuscules ou les chiffres...).
-la methode de l'arbre te permet d'avoir en plus les autres mots possibles quels que soit leur longueur sans presager de l'emplacement de la ou des erreurs (par exemple "avocat" pour "avoc"). C'est plutôt pratique notamment si ton site contient des mots seulement au pluriel (respectivement au singulier): ex. un "avoir" pour des "avoirs" (et inversement).

D'autre part, comme le laisse penser le pseudo "Ajax" de notre interlocuteur, il cible cette technologie qui permet de renvoyer "en live" le résultat à l'utilisateur (voir par exemple Google Suggest: https://www.google.com/webhp?complete=1&hl=en&gws_rd=ssl). Autrement dit, l'utilisateur aura pour chaque lettre saisie, la liste des mots "encore possibles".

En résumé:
1/ ton algo n'est linéaire que parce que tu augmente les hypothèses en restreignant les réponses à un espace de une erreur par mot: dans ce cas autant en passer directement par l'établissement d'un index des mots pour rechercher les solutions par des expressions régulières dans les mots de la longueur de celui saisi...
2/ l'evaluation des retours par le nombre de réponses risque de te jouer des tours: si tu tapes "se*" pour "sel" tu as bien plus de chances de te retrouver avec "sex" comme réponse plutôt que celle que tu veux...

Good luck