IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme d'un moteur de recherche


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 37
    Points : 15
    Points
    15
    Par défaut Algorithme d'un moteur de recherche
    Bonjour,

    je cherche à optimiser la recherche sur mon site car ma base de donnée contient de plus en plus de données.

    Imaginons que je dois trouver l'information parmi 200.000 enregistrements et même plus par la suite.

    Pour le moment, l'algorithme est simple :

    > l'utilisateur tape une chaine de caractère "je cherche l'information"

    > découpage des mots clés considérés utiles [0]->"cherche", [1]->"information"

    > Ensuite recherche de tous les enregistrements avec ces deux mots clés. Création d'un premier tableau de résultat

    > Ensuite on attribue à chaque résultat un nombre de points suivant une formule simple :

    points = nombre mots clefs présent dans l'enregistrement * ponderance (fonction de l'importance du mot clef)

    > Tri décroissant en fonction du nombre de points

    > Affichage des résultats page par page.

    Cependant rechercher parmi tant d'information cela risque de prendre de plus en plus de temps. Je voulais savoir si vous connaissiez des informations concernant les algo de recherche ? J'ai cherché sur le net j'ai trouvé que des infos sur l'algo par dichotomie.

    A bientôt
    Adrien.

  2. #2
    Membre expérimenté
    Avatar de Rakken
    Homme Profil pro
    Inscrit en
    Août 2006
    Messages
    1 257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 1 257
    Points : 1 341
    Points
    1 341
    Par défaut
    Dans ce que tu présentes, ce qui prend du temps, c'est la phase :

    > Ensuite recherche de tous les enregistrements avec ces deux mots clés. Création d'un premier tableau de résultat
    Une des idées que tu peux utiliser, c'est d'indexer le contenu de tes enregistrement. En gros, tu crée une table avec 4 champ (le 4eme est optionnel) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    mot_clef / id_enregistrement / nb_apparition / phrase de contexte
    Avec mot_clef + id_enregistrement en clef primaire.
    Phrase de contexte : un extrait de ton enregistrement, genre 30 caractères avant et 50 après, à régler à l'usage et suivant le contenu.
    Ensuite, tu vas parser tous tes enregistrements, et pour chaque mot, creer un enregistrement dans ta base qui indique où tu as trouvé ce mot, et combien de fois il apparait dans l'enregistrement en question.
    Cette étape là peut prendre pas mal de temps machine si ta base est grande, mais elle n'est faite que de temps en temps quand tu le décides.
    Après, quand quelqu'un rentre un mot, au lieu d'aller voir tes enregistrements, tu vas directement faire un select sur ta table d'indexation where 'mot_clef' like "tonmotderecherche" pour récuperer l'id des enregistrements qui t'interessent.
    Puis tu reprend à ton étape d'attribution de points et de pondération.

    L'intéret est que la partie chronophage du traitement est faite "avant", pour augmenter la rapidité à la lecture.

    La table d'indexation risque d'être franchement volumineuse (pour chaque enregistrement de ta table source tu as une ligne par mot unique) et longue à générer mais avec un index sur "mot_clef", tu as la garanties que les informations sont triées, donc recherche dichotomique. En 20 itérations max la base de donnée aura trouvé tes infos, autant dire, rien du tout par rapport au fait de parser à chaque fois tes 200 000 enregistrements.
    Rakken

    Oneira, un monde imaginaire d'Heroic Fantasy.

    Parce que la présomption d'innocence est un des fondements de notre pays et qu'elle doit le rester, dans tous les domaines : http://www.laquadrature.net/

  3. #3
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 37
    Points : 15
    Points
    15
    Par défaut
    Effectivement ce serait pratique de créer une table parallèle qui reprend la table principale.

    Je testerai ton idée, mais d'avance c'est évidant qu'il y a un gros intérêt : la base principale se retrouve déchargé de toutes les requêtes...

    Le risque c'est de devoir mettre à jour les 100.000 infos chaque jour héhé

  4. #4
    Alp
    Alp est déconnecté
    Expert éminent sénior

    Avatar de Alp
    Homme Profil pro
    Inscrit en
    Juin 2005
    Messages
    8 575
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : Juin 2005
    Messages : 8 575
    Points : 11 860
    Points
    11 860
    Par défaut
    Je ne sais plus quel moteur de recherche utilisait une technique de ce genre. Ce qui est certain c'est que ça améliore nettement la rapidité de recherche... Pour la soumission d'infos tu t'en fous, pour peu que tu lances des crons/robots qui s'occupent de le faire, à leur rythme mais presque en permanence, par exemple.

  5. #5
    Expert éminent Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Points : 7 903
    Points
    7 903
    Par défaut
    Bonjour,

    Dans le cadre d'un serveur, la technique la plus performante est de créer l'index en mémoire au (re)démarrage du serveur et de le maintenir lors des mises à jour.

    Suivant la taille de l'index (nombre de mots différents et nombre d'enregistrements moyen par mot) , il pourra être totalement ou partiellement en mémoire.
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  6. #6
    Expert éminent Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Points : 7 903
    Points
    7 903
    Par défaut
    La table d'indexation risque d'être franchement volumineuse (pour chaque enregistrement de ta table source tu as une ligne par mot unique)
    il sera plus performant de mettre un enregistrement par mot et de gérer des Blob contenant la liste des Id des enregistrements reférencés.
    Prévoir une allocation par blocs (Blobs partiellement remplis) pour ne pas agrandir les blobs à chaque ajout d'une reférence.
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  7. #7
    Membre expérimenté
    Avatar de Rakken
    Homme Profil pro
    Inscrit en
    Août 2006
    Messages
    1 257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 1 257
    Points : 1 341
    Points
    1 341
    Par défaut
    Effectivement, stocker les mots avec un blob/text associé qui a les id, peut être plus performant... Je ferais comme ca si je recode le mien ^^

    Par contre, le défaut de ma méthode, c'est si on cherche quelque chose comme "hello world". On sait quels id ont du "hello", lesquels ont du "world", lequels contiennent l'un et l'autre, mais comment déterminer ceux qui ont "hello world" cote à cote ?
    Rakken

    Oneira, un monde imaginaire d'Heroic Fantasy.

    Parce que la présomption d'innocence est un des fondements de notre pays et qu'elle doit le rester, dans tous les domaines : http://www.laquadrature.net/

  8. #8
    Expert éminent Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Points : 7 903
    Points
    7 903
    Par défaut
    mais comment déterminer ceux qui ont "hello world" cote à cote
    On stocke l'id avec la position dans l'enregistrement.
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  9. #9
    Membre expérimenté
    Avatar de Rakken
    Homme Profil pro
    Inscrit en
    Août 2006
    Messages
    1 257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 1 257
    Points : 1 341
    Points
    1 341
    Par défaut
    Mais que n'y ai-je pensé moi même !
    Rakken

    Oneira, un monde imaginaire d'Heroic Fantasy.

    Parce que la présomption d'innocence est un des fondements de notre pays et qu'elle doit le rester, dans tous les domaines : http://www.laquadrature.net/

  10. #10
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 37
    Points : 15
    Points
    15
    Par défaut
    En gros ce serait avantageux de faire une table du style

    mot_clef => "voyage" id => "132322|332323|220323202|id_video..."
    ?

    J'ai pensé à faire une pré recherche dans un xml contenant les recherches les plus courantes.


    En revanche niveau SQL ce qui bouffe du temps c'est les ORDER BY appariement. J'ai testé avec et sans sur mon algo actuel je suis passé de 10 secondes de chargement à une seconde environ !!


    J'avais une autre idée mais d'après certain site elle est démenti : je pensai qu'il serait plus rapide d'utiliser php pour appeler une commande externe programmée en C/C++ puis récupérer un résultat en sortie ou générer un fichier xml rapide à lire sous php. Un petit programme exécuté par shell_execute devrait faire l'affaire avec la requête passé en paramètre. Je pense que google n'a pas son algo codé en Php ou Asp ? il doive utiliser d'autres langages non ? (enfin même si personne ne sait ce qu'il se passe réellement on peut toujours supposer )

  11. #11
    Membre expérimenté
    Avatar de Rakken
    Homme Profil pro
    Inscrit en
    Août 2006
    Messages
    1 257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 1 257
    Points : 1 341
    Points
    1 341
    Par défaut
    En revanche niveau SQL ce qui bouffe du temps c'est les ORDER BY appariement.
    Si tu crées des index au niveau des champs qui sont dans ton order by, alors ces champs seront déjà trié en base, cela devrait te faire gagner pas mal de temps.
    Par contre, qui dit index dit une lecture plus rapide, mais également une écriture un peu plus lente (genre il doit inserer ses données au bon endroit et pas juste à la suite du reste). Mais dans ton cas, je pense que c'est approprié.
    Rakken

    Oneira, un monde imaginaire d'Heroic Fantasy.

    Parce que la présomption d'innocence est un des fondements de notre pays et qu'elle doit le rester, dans tous les domaines : http://www.laquadrature.net/

  12. #12
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 37
    Points : 15
    Points
    15
    Par défaut
    Je me demande si la puissance du serveur influe beaucoup sur la capacité à exécuter rapidement une requête Sql ?

    C'est vraiment dur de trouver des infos sérieuses sur le net parlant d'algo de moteur de recherche. Et je suis étonné par Exalead ou Google qui donne des résultats en moins d'une seconde pour des milliards de possibilités.

  13. #13
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par didi78 Voir le message
    C'est vraiment dur de trouver des infos sérieuses sur le net parlant d'algo de moteur de recherche.
    Tu as lu la présentation sur la première architecture de Google ?

    http://infolab.stanford.edu/~backrub/google.html

    (Depuis l'architecture a évoluée mais c'est tout de même une bonne base de départ )
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  14. #14
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 37
    Points : 15
    Points
    15
    Par défaut
    Merci énormément, d'autant plus que je viens de remarquer une erreur dans mon algorithme. Il devient de plus en plus lent avec la croissance des enregistrements et il risque de devenir obselète lorsque le nouveau robot d'indexation sera en place (je suis entrain de recoder le tout en C++, ce qui est bien plus performant héhé)

    Je file lire cet article qui semble est une mine d'or d'info sur le sujet
    Tu es un évangéliste des produits google ?

    Merci encore et a bientôt

  15. #15
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par didi78 Voir le message
    Je file lire cet article qui semble est une mine d'or d'info sur le sujet
    Tu es un évangéliste des produits google ?
    Non, pas particulièrement de Google. C'est juste que je pense qu'ils savent de quoi ils parlent en matière de moteur de recherche.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  16. #16
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 37
    Points : 15
    Points
    15
    Par défaut
    héhé et pas qu'en moteur de recherche, ils réussissent partout où ils marchent !

    Sinon je suis entrain de créer les "WordID" en suivant vos conseils.
    On a une table avec wordID en clé primaire qui représente un mot clef, et un TEXT blob contenant la liste des id concerné.

    Mais je ne sais pas s'il serait préférable de faire une autre structure du genre :

    table des mots clefs
    {
    wordID "mot_clef" clé primaire
    id - identifiant unique
    }

    table des liens
    {
    id unique du mot clef
    gid du contenu en relation avec le mot clef
    }

    J'hésite car dans ce cas cela fait deux tables, donc deux query au lieu d'un. Mais cela réduit la taille de la table mots clefs. Je vais surement faire des tests je vous tiens au courant mais si vous avez des conseils n'hésitez pas

    Sinon pour la création des mots clefs mon script tourne assez vite, mais j'ai déjà 150.000 vidéos dont il faut indexer chaque mot clef dans le titre et les tags, ca en fait du travail. En gros mon script tourne pour 500 vidéos puis fait une mini pause, puis reprend etc. Quel dommage que mon serveur ne soit pas très puissant pour pouvoir se manger des requêtes à plein régime

  17. #17
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 37
    Points : 15
    Points
    15
    Par défaut
    Oh my god !

    merci beaucoup, je viens de faire quelques tests avec cette méthode :


    - D'après estimation je pourrais remplir toute la table word_id en 6 heures
    - J'ai testé sur 10.000 enregistrements de word_id une requete longue à rechercher du style : "bush obama victoire chaussure foot etc"

    résultat : Execution du script en 0.042224 secondes

    Ca a du bon Alors merci beaucoup

  18. #18
    Membre à l'essai
    Inscrit en
    Avril 2004
    Messages
    21
    Détails du profil
    Informations forums :
    Inscription : Avril 2004
    Messages : 21
    Points : 18
    Points
    18
    Par défaut
    Salut,

    Nous sommes dans ma boite sur un projet similaire. Nous avons regardé les algos et les BDD d'outils comme Spip ou Wordpress et planchons depuis quelques jours sur une solution proche.
    Les deux tables sont à mon avis préférable à une seule table avec un blob (lourd).
    Qu'en pensez-vous ?

    La table des mots clefs :
    id_mot BIGINT
    mot VARCHAR(30)

    La table des liens
    id-mot, id_page
    poids

    le poids pourrait etre donné en fonction du nombre de fois qu'apparait le mot par rapport au nombre de mots total.

    Au niveau de la recherche :
    La page doit etre notée non seulement en fonction du poids du mots clefs pour la page mais aussi en fonction du nombre de mots qu'elle référence. (sur une requete "élection obama", la page qui contient "élection d'obama" doit être plus importante que celle qui contient 10 fois élection )

    Un GROUP BY avec un count pourrait etre interressant.

    Concernant les expressions (ton "hello world") l'idée de noter la position des mots est très interrssante (nous étions partis sur autre chose).

    Nous sommes en train de développer le programme (php) qui se charge de construire les mots clefs. Peut-être pourrions-nous échanger quelques idées?

  19. #19
    Membre expérimenté
    Avatar de Rakken
    Homme Profil pro
    Inscrit en
    Août 2006
    Messages
    1 257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 1 257
    Points : 1 341
    Points
    1 341
    Par défaut
    Pour ma part, pour la recherche sur plusieurs mots (l'un "ou" l'autre) je considérais (mais c'est un choix personnel), qu'il était plus interessant quand on cherche "election obama" d'avoir une page avec 3 fois election et 50 fois obama qu'une page avec 4 fois election et 4 fois obama.
    Donc en gros, j'attribue 1 point a chaque fois qu'un mot apparait dans une page, et 10 pour un 'couple' (voire un peu plus, je ne sais plus quelle valeur j'avais mis. J'avais fait plusieurs tests pour avoir les réponses qui me semblaient les plus pertinentes en moyenne sur le contenu de mes pages).
    C'est d'autant plus vrai quand ce qui est recherché comporte beaucoup de mot. Du genre "Election américaine obama mccain palin biden usa"
    Avec un simple group by, une page qui possède tous les mots sauf un 10 fois sera placée après une page qui possède tous les mots 1 seule fois.
    Enfin, ca se sont des choix stratégiques à définir en fonction du contenu plus que du code.

    A noter aussi que je n'indexe pas les mots ayant une seule lettre, que je supprime les l', d' (l'election => election) dans l'indexer, et que je vire certains mots récurents classiques du genre "un, une, le, la, les..."
    Rakken

    Oneira, un monde imaginaire d'Heroic Fantasy.

    Parce que la présomption d'innocence est un des fondements de notre pays et qu'elle doit le rester, dans tous les domaines : http://www.laquadrature.net/

  20. #20
    Membre à l'essai
    Profil pro
    Inscrit en
    Novembre 2008
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2008
    Messages : 37
    Points : 15
    Points
    15
    Par défaut
    Bonjour,

    cela fait quelques temps que j'ai pas posté ici,
    j'ai du améliorer d'autres aspects sur le projet mooveOn notamment au niveau communautaire.

    Mais après m'être inspiré des idées de Rakken et après avoir développé mes propres idées, je vais bientôt mettre en place un nouveau système fondé sur celui actuel.

    J'aimerai donc avoir votre avis sur la pertinence des recherches sur le moteur actuel du projet mooveOn.net Ce qui se passe, c'est que comme le site grossit à la vitesse du robot indexateur (on a presque 2 millions de vidéos indexées), je vais devoir mieux hiérarchiser les résultats et proposer quelque chose de nouveau dans la manière de présenter les résultats. Mais avant ca, j'aimerai des avis sur :
    - la rapidité ou non du moteur
    - la pertinence
    - des problèmes ?

    Merci d'avance pour votre aide,
    cordialement, Adrien.

Discussions similaires

  1. Google doit-il publier l'algorithme de son moteur de recherche ?
    Par Gordon Fowler dans le forum Actualités
    Réponses: 94
    Dernier message: 31/07/2010, 11h44
  2. Algorithme d'indexation pour moteur de recherche
    Par caspertn dans le forum Algorithmes et structures de données
    Réponses: 7
    Dernier message: 24/04/2006, 17h57

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo