Brevet FR2798206A1 — publié le 20010309

La présente invention se rapporte à un moteur de recherche ainsi qu'à un procédé d'indexation et de recherche de documents. Elle s'applique en particulier à l'indexation et à la recherche de documents, par exemple des pages Web, stockés dans des centres serveurs répartis sur un réseau informatique. Un moteur de recherche est un outil informatique permettant d'extraire d'une information, principalement textuelle, les mots ou termes qui la représentent le mieux et de les stocker dans des bases d'index. En réponse à une requête formulée par un utilisateur, ce même outil parcourt ces bases d'index afin d'identifier les termes les plus pertinents par rapport à ceux de la requête, puis de trier les informations à fournir en retour. Classiquement, un moteur de recherche comprend - un module de recherche de documents sur un réseau informatique, - un module d'indexation des documents récupérés sur le réseau informatique pour la création et la mise à jour de bases d'index, - un module d'interrogation des bases d'index, qui à partir d'une requête utilisateur, fourni en réponse les références des documents correspondant le mieux à la requête. Pour réaliser l'indexation, le moteur de recherche scrute en permanence le réseau informatique et récupère des documents, par exemple les documents nouvellement créés ou modifiés, extrait de chaque document la liste des éléments le constituant, et associe à chaque élément des informations caractéristiques de cet élément vis à vis du document, par exemple son score, c'est-à-dire l'importance de cet élément pour le document, et sa position dans le document. On obtient ainsi, dans les bases d'index, des informations représentant de façon aussi fidèle que possible l'ensemble du contenu des serveurs du réseau informatique. Pour pouvoir être efficace, c'est à dire pour pouvoir répondre efficacement à des requêtes, il est nécessaire que l'indexation s'effectue de façon plus rapide que la création de sites ou de nouvelles pages. En raison du nombre très élevé de sites et de pages accessibles sur le réseau, on conçoit que la mémoire dans laquelle sont stockées les bases d'index doit avoir une capacité particulièrement importante. Classiquement, cette mémoire est constituée par une mémoire de masse persistante, par exemple le disque dur d'un centre serveur dans lequel est implanté le moteur de recherche. Ce type de support de stockage a généralement une capacité suffisante, mais présente un inconvénient majeur dans la mesure où les accès mémoire s'effectuent à des vitesses qui dégradent considérablement la vitesse de mise à jour des bases d'index. Le but de l'invention est de pallier cet inconvénient. Elle a donc pour objet un moteur de recherche du type précité, caractérisé en ce que le module d'indexation comporte des premiers moyens de mémorisation à accès rapide pour le stockage incrémental et temporaire des éléments et des informations correspondantes d'un nombre restreint de documents et des deuxièmes moyens de mémorisation dans lesquels sont stockées les bases d'index et dans lesquels est transféré le contenu desdits premiers moyens de mémorisation dès que leur capacité maximale est atteinte. Ainsi, le remplissage des bases d'index s'effectue par l'intermédiaire d'une mémoire tampon, ce qui permet de réduire considérablement la durée de création et de mise à jour des bases d'index. Le moteur de recherche selon l'invention peut en outre comporter une ou plusieurs des caractéristiques suivantes, prises isolément ou selon toutes les combinaisons techniquement possibles - le module d'indexation comporte, stocké en mémoire, un algorithme d'adressage calculé, pour la formation de tables de hachage à partir des documents récupérés sur le réseau informatique, lesdites tables étant stockées dans lesdits premiers moyens de mémorisation. - le module d'indexation comporte des moyens de calcul de caractéristiques représentatives de la pertinence de chaque élément extrait de chaque document vis à vis de ce document, - ces moyens de calcul sont constitués par algorithme d'adressage calculé, - les deuxièmes moyens de mémorisation comportent deux espaces mémoire destinés l'un au stockage des bases d'index et l'autre au stockage du contenu des premiers moyens de mémorisation et des moyens de fusion du contenu des deux espaces mémoire, - le module de recherche comprend des moyens de filtrage des requêtes pour identifier les éléments pertinents de chaque requête. - le module de recherche comporte en outre des moyens de traitement des résultats fournis après interrogation des bases d'index, ces moyens de traitement comprenant des opérateurs de calcul ensembliste. L'invention a également pour objet un procédé d'indexation et de recherche de documents sur un réseau informatique, comprenant les étapes suivantes - indexation des documents récupérés sur le réseau pour former et mettre à jour des bases d'index contenant, pour chaque élément de l'ensemble des documents, une liste des documents dans lesquels il apparaît ainsi que des informations caractéristiques de l'élément vis à vis des documents. - en réponse à une requête formulée par un utilisateur, interrogation des bases d'index pour fournir, en réponse, l'indication des documents correspondant à la requête, caractérisé en ce que l'indexation comprend les étapes suivantes - on indexe les documents de façon incrémentale de manière à mémoriser dans des premiers moyens de mémorisation à accès rapide les éléments et les informations correspondantes d'un nombre restreint de documents, et - dès que la capacité maximale des premiers moyens de mémorisation est atteinte, on transfère leur contenu vers des deuxièmes moyens de mémorisation. De préférence, l'indexation consiste à créer une table de hachage regroupant la liste des éléments de chaque document récupéré associés à des informations de localisation de ces éléments dans le document. Selon une autre caractéristique de ce procédé, lors de l'étape d'interrogation des bases d'index, on filtre la requête formulée par l'utilisateur de manière à en extraire les éléments pertinents et on présente les éléments pertinents en entrée des bases d'index pour récupérer une liste de documents correspondant à la requête. De préférence, postérieurement à la présentation des éléments pertinents en entrée des bases d'index, on effectue des calculs d'opération ensembliste sur les résultats fournis. Selon encore une autre caractéristique de ce procédé, le contenu des premiers moyens de mémorisation est transféré dans un premier espace mémoire des deuxièmes moyens de mémorisation pour constituer des bases d'index différentielles, ces bases d'index différentielles étant fusionnées avec des bases d'index principales stockées dans un deuxième espace mémoire des deuxièmes moyens de mémorisation. D'autres caractéristiques et avantages ressortiront de la description suivante , données uniquement à titre d'exemple, et faite en référence aux dessins annexés sur lesquels - la figure 1 est un schéma synoptique illustrant la structure générale d'un moteur de recherche ; et - la figure 2 illustre la structure d'une table de hachage d'une page d'un document. Sur la figure 1, on a représenté la structure générale d'un moteur de recherche conforme à l'invention, désigné par la référence numérique générale 10. Dans l'exemple de réalisation représenté, le moteur de recherche est un moteur francophone. II est destiné, d'une part, à la création et à la mise à jour de bases d'index 12, 14 et 16, dites principales, contenant, comme cela est classique, pour chaque document récupéré sur un réseau informatique 18, par exemple le réseau internet, une liste d'éléments extraits de ce document associés chacun à des informations caractéristiques de cet élément vis à vis de ce document ainsi qu'une liste de documents dans lesquels ces éléments apparaissent et, d'autre part, à évaluer des requêtes formulées par un utilisateur au moyen d'un poste 20 en interrogeant les bases d'index 12, 14 et 16. En réponse, le moteur de recherche fournit à l'utilisateur une ou plusieurs références des documents contenant un ou plusieurs éléments de la requête. Pour assurer ces fonctions, le moteur 10 comporte un module 22 d'indexation recevant, en entrée des pages web récupérées sur le réseau 18 par des robots, tels que 24, en vue de leur indexation, et un module 26 de recherche recevant, en entrée, les requêtes formulées par l'utilisateur et interrogeant les bases d'index 12, 14 et 16 pour fournir à l'utilisateur la liste des références des documents ou pages web correspondant à la requête. Pour la mise à jour des bases d'index, les robots scrutent périodiquement le réseau informatique, par exemple une fois par semaine, à un instant où la bande passante sur le réseau est accrue, et transmet ,par exemple, les pages nouvelles ou modifiées au module d'indexation. Ce module d'indexation 22 comporte un module 28 d'analyse des pages fournies par les robots 24 contenant un algorithme d'adressage calculé ou " hash-code . Cet algorithme est un algorithme de calcul de type classique approprié. II ne sera donc pas décrit par la suite. On notera cependant qu'il permet la formation de tables de hachage, à partir des documents récupérés sur le réseau informatique, listant les éléments des documents, associés par exemple à des informations de localisation. II comporte également un indexeur 30 auquel sont fournis les tables de hachage formées par le module d'analyse 28 en vue de leur stockage dans les bases d'index 12, 14 et 16. Plus particulièrement, dans le but de diminuer la durée de l'indexation, le module 22 d'indexation comporte des premiers moyens de mémorisation à accès rapide, constitués par des zones d'adresses mémoire formées dans la mémoire vive du centre serveur dans lequel est implanté le moteur de recherche, pour le stockage des tables de hachage formées par le module 28 d'analyse, et des deuxièmes moyens de mémorisation, constitués par des zones d'adresse mémoire formées dans le disque dur du centre serveur et dans lesquels sont stockées les bases d'index 12, 14 et 16 et dans lesquels sont sauvegardées les tables de hachage sous la forme de bases d'index différentielles 32, 34 et 36 destinées à être fusionnées avec les bases d'index principales 12, 14, 16. Le fonctionnement du module 28 d'analyse et de l'indexeur 30 va maintenant être détaillé en référence à la figure 2. Le module 28 d'analyse comporte, stocké en mémoire, et comme mentionné précédemment, un algorithme d'adressage calculé, pour former, à partir de chaque page fournie par les robots 24, une table de hachage, visible sur la figure 2, dans laquelle sont listés les éléments, en particulier les mots, extraits de cette page associés chacun à des informations caractéristiques de cet élément vis à vis de cette page. Comme on le voit sur la figure 2, pour une page récupérée sur le réseau, le module 28 d'analyse crée une table de hachage 38 indexant tous les mots de la page. Ainsi, dans l'exemple représenté, la table de hachage 38 comporte les mots " voiture " et " avion ", chacun de ces mots étant associé à des informations caractéristiques de ce mot pour le document indexé. Ces informations sont, par exemple, le score, indiquant l'importance du mot dans le document, de préférence normalisé selon la taille de la page , une liste de positions du mot dans la page, le nombre d'occurrences de ce mot, ainsi que le type d'éléments auquel il appartient. On notera que, de préférence, seules les deux premières positions du mot sont mémorisées afin de ne pas obtenir des bases trop volumineuses. On notera également que, pour le calcul du score d'un mot, on prend en compte le nombre total de mots dans le document et des marqueurs caractérisant le mot, par exemple les balises HTML, permettant de mettre en valeur des mots lors de la visualisation de pages web par un navigateur web. On notera enfin que la table de hachage prend également en compte le type d'éléments auquel il appartient, c'est à dire s'il s'agit d'un mot " normal " ou d'un élément dit "alias ". Dans le cas d'un élément de type " alias " l'élément peut être une image, un son, un lien ou un code d'instruction. Dans ce cas, le libellé exact de l'élément est remplacé par un mot clé, par exemple " #EXJPG " pour une image au format JPG. Comme mentionné précédemment, les tables de hachage délivrées par le module 28 d'analyse, stockées temporairement dans les premiers moyens de mémorisation, sont fournis à l'indexeur 30 en vue de leur stockage ultérieur dans les seconds moyens de mémorisation pour constituer les bases d'index différentielles 32, 34 et 36, et ce lorsque la capacité maximale des premiers moyens de mémorisation (mémoire vive) est atteinte. Ces premiers moyens de mémorisation ont une capacité limitée et ne sont donc adaptés que pour le stockage des tables de hachage correspondant à un nombre limité de pages, par exemple 7500 pages. Le stockage dans les premiers moyens de mémorisation s'effectue donc de façon incrémentale et temporaire sous la forme d'un nombre limité de pages, le contenu de ces premiers moyens de mémorisation étant transféré vers les deuxièmes moyens de mémorisation dès que la capacité maximale des premiers moyens de mémorisation est atteinte pour y être sauvegardé pour constituer les bases différentielles 32, 34, 36. Pour ce faire, le module 22 d'indexation est doté d'un module 40 de fusion réalisant l'intégration des bases d'index différentielles 32, 34 et 36 dans les bases d'index 12, 14 et 16. Cette fusion s'effectue donc en utilisant deux ensembles d'espaces mémoires formés dans le disque dur du centre serveur, destinés les uns au stockage des bases d'index principales 12, 14 et 16 et, les autres, au stockage des contenus des premiers moyens de mémorisation, c'est à dire de la mémoire vive, sous forme de bases différentielles 32, 34 et 36 dans les seconds moyens de mémorisation, c'est à dire dans le disque dur, le module de fusion 40 comportant des moyens logiciels de fusion du contenu respectif des bases d'index principales 12, 14 et 16 d'une part, et des bases d'index différentielles 32, 34 et 36 d'autre part. Le module de recherche 26 comporte, quant à lui, un module 42 de traitement des requêtes formulées par l'utilisateur, ce module 42 comportant un algorithme de filtrage de ces requêtes pour identifier les éléments pertinents constitutifs de chacune d'elle. Par exemple il peut éliminer des requêtes les éléments trop fréquents dans les bases d'index pour représenter une quantité d'information suffisante, tels que les mots très fréquents du langage : " le ", " la ", " les ".... Cet algorithme de filtrage est constitué par un algorithme de type classique et ne sera donc pas décrit par la suite. On notera toutefois que, par exemple, il traduit les requêtes sous la forme d'un arbre d'évaluation, en utilisant, par exemple, des script " LEX " et " YACC " de type classique, en conservant un maximum de cinq mots par requête. L'arbre d'évaluation ainsi réalisé est ensuite transmis à des modules 44, 46 et 48 de recherche proprement dite adaptés pour interroger les bases d'index 12, 14 et 16 en présentant les éléments pertinents de chaque requête en entrée de ces bases d'index. En réponse, les modules de recherche 44, 46 et 48 extraient des bases 12, 14 et 16 une liste de références sur des documents, en particulier de numéros de pages dans lesquelles les éléments de la requête apparaissent, références associées notamment à l'indication du score des mots dans chacune de ces pages et, éventuellement, à une indication de la position de ces mots dans les pages. Après récupération de ces références, les modules de recherche 44, 46 et 48 procèdent à un calcul du résultat de l'arbre d'évaluation en utilisant des opérateurs de calcul ensembliste. Ainsi, par exemple, si l'utilisateur a formulé la requête de la façon suivante " train " ET " couchette ", le résultat délivré par les modules de recherche 44, 46 et 48 sera constitué par l'intersection des deux ensembles de pages fournies respectivement pour les mots " train " et " couchette ", les scores étant, dans ce cas, sommés. Au contraire, si l'utilisateur a formulé sa requête de la façon suivante " train " OU " couchette ", le résultat fourni par les modules de recherche 44, 46 et 48 sera constitué par l'union des deux ensembles de pages correspondant respectivement au mot " train " et au mot " couchette ". La détermination de la pertinence d'une page fournie en réponse à une telle requête, c'est à dire le score de la page, s'effectue de la façon suivante. Si un mot est le seul à se trouver dans une page, on décide que le score de la page correspond au score du mot dans cette page. Par contre, si les deux mots se trouvent dans la même page, le score de la page est alors égale à la somme des scores de ces mots. Ainsi, lors d'une évaluation d'un ET ou d'un OU le score est calculé en utilisant la formule suivante Score = somme (rareté x score-dans- page x facteur- syntaxe) dans laquelle rareté désigne l'inverse de la fréquence du mot dans l'index ; score dans_page désigne le score généré lors de l'indexation, et facteur syntaxe désigne un coefficient illustrant le fait que les mots déclinés (formes plurielles, féminines...) ont moins de poids que les mots saisis directement par l'utilisateur dans la requête. Lorsque la liste des numéros de pages fournies en tant que résultat ainsi que leurs scores ont été déterminés, le meilleur score est normalisé à la valeur arbitraire de 100%, cette référence étant utilisée pour normaliser les scores suivants. On conçoit que l'invention qui vient d'être décrite, qui utilise des moyens de mémorisation à accès rapide pour le stockage incrémental et temporaire des mots et des informations correspondantes d'un nombre restreint de documents, ainsi que des deuxièmes moyens de mémorisation dans lesquels sont stockées les bases d'index et vers lesquels sont transférés les contenus des premiers moyens de mémorisation permet d'accroître la rapidité de constitution de bases d'index de tailles importantes. En effet, lorsque l'on utilise une mémoire RAM pour le stockage temporaire des tables de hachage et un disque dur pour le stockage des bases d'index, l'écriture des tables de hachage dans les premiers moyens de mémorisation est classiquement extrêmement plus rapide que l'écriture directe des données dans les deuxièmes moyens de mémorisation. REVENDICATIONS 1. Moteur de recherche comprenant un module (22) d'indexation de documents récupérés sur un réseau informatique pour la création et la mise à jour de bases d'index (12, 14, 16) contenant, pour chaque document, une liste d'éléments extraits de ce document associés chacun à des informations caractéristiques de cet élément vis à vis de ce document et un module (26) de recherche de documents sur le réseau informatique adapté pour interroger les bases d'index à partir d'une requête formulée par l'utilisateur pour fournir, en réponse, l'indication des documents correspondant à la requête, caractérisé en ce que le module d'indexation comporte des premiers moyens de mémorisation à accès rapide pour le stockage incrémental et temporaire des éléments et des informations correspondantes d'un nombre restreint de documents et des deuxièmes moyens (12, 14, 16 et 32, 34, 36) de mémorisation dans lesquels sont stockées les bases d'index et dans lesquels est transféré le contenu des premiers moyens de mémorisation dès que leur capacité maximale est atteinte. 2. Moteur de recherche selon la revendication 1, caractérisé en ce que le module (22) d'indexation comporte, stocké en mémoire, un algorithme d'adressage calculé, pour la formation de tables de hachage (38) à partir des documents récupérés sur le réseau informatique, lesdites tables étant stockées dans lesdits premiers moyens de mémorisation. 3. Moteur de recherche selon l'une des revendications 1 et 2, caractérisé en ce que le module (22) d'indexation comporte des moyens de calcul de caractéristiques représentatives de la pertinence de chaque élément extrait de chaque document vis à vis de ce document. 4. Moteur de recherche selon la revendication 3, caractérisé en ce que lesdits moyens de calcul sont constitués par l'algorithme d'adressage calculé. 5. Moteur de recherche selon l'une quelconque des revendications 1 à 4, caractérisé en ce que les deuxièmes moyens de mémorisation comportent deux espaces mémoire destinés l'un au stockage de bases d'index principales et l'autre au stockage du contenu des premiers moyens de mémorisation sous forme de bases différentielles, et des moyens de fusion du contenu des bases principales et différentielles. 6. Moteur de recherche selon l'une quelconque des revendications 1 à 5, caractérisé en ce que le module (26) de recherche comprend des moyens de filtrage des requêtes pour identifier les éléments pertinents de chaque requête. 7. Moteur de recherche selon la revendication 6, caractérisé en ce que le module (26) de recherche comporte en outre des moyens de traitement des résultats fournis après interrogation des bases d'index, ces moyens de traitement comprenant des opérateurs de calcul ensembliste. 8. Procédé d'indexation et de recherche de documents sur un réseau informatique, comprenant les étapes suivantes - indexation des documents récupérés sur le réseau pour former et mettre à jour des bases d'index (12, 14, 16) contenant, pour chaque élément de l'ensemble des documents, une liste des documents dans lesquels il apparaît ainsi que des informations caractéristiques de cet élément vis à vis de ce document, et - en réponse à une requête formulée par l'utilisateur, interrogation des bases d'index (12, 14, 16) pour fournir, en réponse, l'indication des documents correspondants à la requête, caractérisé en ce que l'indexation comprend les étapes suivantes - on indexe les documents de façon incrémentale de manière à mémoriser dans des premiers moyens de mémorisation à accès rapide les éléments et les informations correspondantes d'un nombre restreint de documents, et - dès que la capacité maximale des premiers moyens de mémorisation est atteinte, on transfère leur contenu vers des deuxièmes moyens (32, 34, 36) de mémorisation. 9. Procédé selon la revendication 8, caractérisé en ce que l'indexation consiste à créer une table de hachage (38) regroupant la liste des éléments de chaque document récupéré associés à des informations de localisation de ces éléments dans les documents. 10. Procédé selon l'une des revendications 8 et 9, caractérisé en ce que lors de l'étape d'interrogation des bases d'index (12, 14, 16), - on filtre la requête formulée par l'utilisateur de manière à en extraire les éléments pertinents, et - on présente les éléments pertinents en entrée des bases d'index pour récupérer une liste de documents correspondant à la requête. 11. Procédé selon la revendication 10, caractérisé en ce que postérieurement à la présentation des éléments pertinents en entrée des bases d'index (12, 14, 16), on effectue des calculs d'opération ensembliste sur les résultats fournis. 12. Procédé selon l'une quelconque des revendications 8 à 11, caractérisé en ce que le contenu des premiers moyens de mémorisation est transféré dans un premier espace mémoire des deuxièmes moyens de mémorisation pour constituer des bases d'index différentielles et en ce que ces bases d'index différentielles sont fusionnées avec des bases d'index principales stockées dans un deuxième espace mémoire des deuxièmes moyens de mémorisation.