Journal De la "Recherche" approximative en php

Posté par  .
Étiquettes : aucune
0
12
juin
2004
Bonjour;

Suis-je le seul à trouver la plupart des moteurs de recherche présent sur les sites vraiment pourris ? (a commencer par les miens). N'y a t'il pas des scripts qui permettent par exemple de trouver le mot "fraise" lorsqu'on tape "fraiiise" ? J'ai passé la journée à chercher des scripts de ce genre mais rien. Et vous ? comment faites vous ?
Même sur les sites de commerces électronique je trouve que c'est pourris. Suffit d'introduire une lettre de trop dans un mot, ou de mettre la conjugaison qui va pas bien et on trouve plus rien.
Personne s'es penché sur le problème dans le monde du libre ?

  • # J'ai encore oublié de cocher la case

    Posté par  . Évalué à -4.

    Arf je voulais pas mettre en première page... méa culpa

  • # Une idée

    Posté par  (site web personnel) . Évalué à 2.

    Je suis en train d'améliorer les moteurs de recherche des mes sites, car ce n'était pas la joie non plus :-).

    Pour ta question, je pense qu'il y a moyen de s'en sortir avec des expressions régulières, en faisant un preg_match avec un patern qui introduise des caractères parasites type fautes de frappe.

    • [^] # Re: Une idée

      Posté par  (Mastodon) . Évalué à 6.

      Les expressions rationnelles c'est trop simpliste pour marcher (efficacement). Il faut regarder du côté des algorithmes utilisés en bioinfo pour les analyses de séquence, en gros c'est un calcul de distance d'édition entre deux mots (nombre de modifications élémentaires à faire pour passer de l'un à l'autre).

      Il y a des bouquins assez abordables sur la question dont un qui doit s'appeler "algorithmique du texte".

      • [^] # Re: Une idée

        Posté par  . Évalué à 3.

        > Il y a des bouquins assez abordables sur la question dont un qui doit s'appeler "algorithmique du texte".

        Nooooooooon pas celui la (vuibert ?).

        J'etais jeune et fou a l'epoque moi aussi je voulais coder ca. Effectivement il y a ce bouquin. Je l'ai trouvé, je l'ai ouvert, je l'ai lu, j'ai essaye de le comprendre et je l'ai vite refermé il fait vraiment trop mal au crane :-)

        Mais il me semble que ce genre de choses soient abordées dedans si ma mémoire est bonne.

        • [^] # Re: Une idée

          Posté par  . Évalué à 2.

          A vrai dire le sujet m'interesse bien aussi mais je ne pense pas pouvoir comprendre les ouvrages sur la questions.

          • [^] # Re: Une idée

            Posté par  (Mastodon) . Évalué à 3.

            L'idée de base est relativement simple, mais les algorithmes sont assez compliqués. En gros, on définit la notion d'édition entre deux mots (comme j'ai dit plus haut, le nombre d'opérations élémentaires entre ces mots). Avec cette distance, on pourrait théoriquement comparer le mot requête avec tous les mots du texte cible, mais ce serait trop long. Donc on construit un automate à partir du texte cible, qui servira d'index pour faire une recherche rapide.

            Note que ça ne demande aucune notion compliquée. C'est plein de notions simples, mises ensembles pour faire un truc assez subtil. Mais c'est abordable par n'importe qui d'assez motivé. Par contre pour le livre dont je parlais, je ne sais pas s'il est suffisant si on n'a pas un cours avec des exemples derrière :-/

            Une idée: c'est pas possible d'utiliser un logiciel comme BLAST pour faire ça sans trop s'embêter ?

  • # mysql

    Posté par  . Évalué à 2.

    Avec mySQL c'est très simple: WHERE texte LIKE "%f%r%a%i%s%e%"

    Bon ça va te trouver aussi des trucs genre "françoise"...

    • [^] # Re: mysql

      Posté par  . Évalué à 2.

      lol le pire c'est que ca marcherait meme pas avec "%f%r%a%i%i%s%s%e%"

  • # soundex peut-etre...

    Posté par  . Évalué à 3.

    Peut être en se renseignant sur SOUNDEX...

  • # distance de levenshtein

    Posté par  . Évalué à 6.

    Un truc utilisé par les dictionnaires orthographiques.

    En php il existe : http://www.nexen.net/docs/php/annotee/function.levenshtein.php(...)

    • [^] # Re: distance de levenshtein

      Posté par  . Évalué à 2.

      Oui.
      C'est efficace, j'ai utilisé ca il y a quelques temps.

      Et c'est assez facile à utiliser.

      En gros ça calcule la "distance" entre 2 chaines de caractéres selon la définition de Levenshtein, soit le nombre de caractéres qu'il faut ajouter/modifier/supprimer pour passer d'une chaine à l'autre.

      Pour les fautes de frappe c'est idéal, mais ca marche assez bien aussi pour les fautes d'ortographe.

      • [^] # Re: distance de levenshtein

        Posté par  . Évalué à 3.

        La complexité de l'algorithme est en O(m*n), où n et m sont les tailles respectives de str1 et str2

        Ca force quand meme a comparer avec tous les mots du dico, y'a pas un truc qui permettrait de tirer parti d'un index a tout hasard ?

        • [^] # Re: distance de levenshtein

          Posté par  . Évalué à 2.

          Pour des bases trés importantes, ca peut éventuellement poser probléme.

          L'utilisation d'un index ne me parait pas être une bonne solution. Un index est basé sur un tri, et c'est justement quand ce tri n'est plus suffisant que des fonctions de recherche avancés sont utile. Genre quand je cherche conqueror je veux aussi Konqueror: distance de Levenshtein faible (1), mais distance alphabétique trés grande.

          Une des solution courament utilisée pour diminuer la charge, c'est de faire une premiére recherche en ortographe exacte, puis de demander à l'utilisateur s'il veut corriger l'ortographe ou faire une recherche en ortographe approchée.

          Pspell est surement à étudier mais pas forcément une bonne idée. Ce n'est pas non plus ultra léger en ressource, ca demande un bon controle sur le serveur de production, c'est beaucoup moins universel, etc...

          En fait, il faudrait faire une étude assez précise pour dire quelle est la meilleure solution :
          - Fréquence des changements du site
          - Fréquence des recherches
          - fréquence des fautes dans les recherches
          - ressource la plus limitée : espace disque, puissance proc, BP...
          - etc...

          Tout ca pour expliquer pourquoi il n'y a pas de solution "toute faite".

  • # Pspell

    Posté par  . Évalué à 2.

    Utilise pspell pour faire cela. J'ai deja réalisé ce genre de chose avec ce programme.

    Levenshtein est trop couteux en ressource.

    tu as des fonctions pspell dans php. Seul hic, il faut que php soit compilé pour l'utiliser avec, et il te faut donc probablement un serveur dedié.

    • [^] # Re: Pspell

      Posté par  . Évalué à 2.

      Hum ça semble pas mal. Je pensais constituer un dictionnaire à partir des mots de ma base. Ensuite je corrige la recherche de l'utilisateur via mon dictionnaire et normallement je devrais avoir un mot prêt à etre recherché. Ca semble correct ?

      • [^] # Re: Pspell

        Posté par  . Évalué à 2.

        oui, il faut que tu realises un traitement sur tes mots via des regexp pour donner à pspell une liste de mots valables.

        En tous cas t'as l'idée. (le dico se fait en ligne de commande avec les fichiers de phonetiques francaises qui se trouve dans /usr/share/pspell si je me rappelle bien)

  • # Commentaire supprimé

    Posté par  . Évalué à 2.

    Ce commentaire a été supprimé par l’équipe de modération.

  • # Indexation de texte intégral

    Posté par  (site web personnel) . Évalué à 2.

    Personne s'es penché sur le problème dans le monde du libre ?

    Si, mais la solution n'est pas à chercher du côté script mais côté base de données en mettant en oeuvre des indexations de texte intégral (full text indexing).

    Pour Postgresql : extension tsearch :
    http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/(...)

    Pour MySQL l'indexation est possible en standard depuis la v3.23.23 http://dev.mysql.com/doc/mysql/en/Fulltext_Search.html(...)

  • # Côté moteur de recherche

    Posté par  (site web personnel) . Évalué à 3.

    http://www.htdig.org/(...)

    Fuzzy searching
    Searches can be performed using various configurable algorithms. Currently the following algorithms are supported (in any combination):

    * exact
    * soundex
    * metaphone
    * common word endings (stemming)
    * synonyms
    * accent stripping
    * substring and prefix

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.