Création d’un index de recherche – moteur de recherche Part1

0
Création d'un index de recherche  - moteur de recherche Part1

Ok, let’s go. nous allons commencer la création de notre moteur de recherche home made :). La première partie (disons deuxième après le crawl), va etre d’exploiter l’ensemble des documents collectés. La partie 2 consiste à rechercher dans notre index, et la troisième partie consiste à créer un score de ranking pour classer les résultats.

Il s’agit ici de créer un index basé sur un corpus de documents. Normalement, les moteurs de recherche ont des robots qui parcourent le web en permanence à la recherche de nouveaux documents et mettent à jours leurs bases de données. Nous n’allons pas créer de crawler à proporement parler. Pour faire simple, nous allons travailler sur un corpus de documents déja existants. Pour ma part, j’ai pris quelques milliers d’articles issus de wikipedia. Ca me servira de base pour le processus d’indexation.

Le format de mon fichier d’input est le suivant:

<pages>
<page>
<title>le titre de mon article.</title>
<text>le contenu de mon article.</text>
</page>
</pages>

Comme vous pouvez le voir, j’ai opté pour un format xml classique. Notre programme va pouvoir lire les données de manière très simple.

Pour notre exemple, j’ai pris un corpus de 5000 pages toutes issues de wikipedia.

Récupération des informations:

La première chose que nous allons faire est de récupérer les informations texte contenues dans le corpus. En gros, nous allons récupérer les informations entre les balises <text></text> et <title></title> que nous allons agréger.

Une fois que cela est fait, nous allons transformer cette chaine de caractères en liste de mots.

Qu’entendons nous par “mot” ?

Nous allons devoir procéder à une normalisation des mots afin d’éviter de prendre des mots inutiles ou qui n’en sont pas vraiment. Nous allons exclure certains stopwords, et également remettre à la même échelle différentes déclinaisons d’un même mot. Voici la liste des normalisation à opérer:

1- transformer l’ensemble des mots en minuscule. APPLE sera égal à Apple qui sera égal à apple.
2-Nous n’allons garder que les caractères alpha-numériques les caractères spéciaux seront éliminés (!, #, &,…). Nous allons utiliser une regex pour cela. Mettons que notre contenu est dans une variable appellée text, alors:

text = Regex.Replace(text, “[^a-z0-9]”,””);

2-utilisation du stemming:

le stemming est la technique permettant de ramener tous les mots à leur radical. De cette manière, une recherche sur “déménager”, “déménagement”, “déménageur” aura comme stem le meme radical qui est “déménag”. Nous allons alors pouvoir matcher un grand nombre de documents avec un haut niveau de pertinence. Le stemming permet également de parer à certaines fautes d’orthographe.
Les techniques de stemming sont très complexes surtout lorsque nous voulons créer un moteur de recherche dans plusieurs langues différentes. Pour ma part, je vais utiliser un algorithme connu sous le nom de porter stemmer. L’avantage c’est que cet algorithme existe dans plusieurs langues et langages. Il est facilement utilisable. Néanmoins, les résultats obtenus pour le français sont bons mais quelques fois, ils me sort de belles surprises :). Mais bon il fera largement l’affaire pour notre besoin.

4- supprimer les stopwords

Les stopwords sont tous les mots comme “de”, “des”, “le”,”quelle”… qui sont indispensables pour la syntaxe de toute langue, mais qui n’ont pas une très grande valeur ajoutée pour un moteur de recherche. Nous serons tous d’accord pour dire qu’une recherche sur “chaussure de sport” devrait renvoyer les même résultats que “chaussure sport”, non? c’est pour ca que cette étape est utile.

Vous pouvez trouver ici une liste de départ pour constituer vos stopwords en francais ou autre langue cible.

Attention:
cette liste n’est pas complète. Je la trouve même un peu limite, mais constitue une bonne base de départ.

A ce stade, nous avons une liste de “mots utiles” issue de chaque document mappé avec le corpus de documents. C’est ce qu’on appelle un index !

Création de l’index inversé:

Nous allons à présent créer un index inversé basé sur le mot. L’idée est de mettre en face de chaque mot le numéro de tous les documents qui le contiennent. Nous allons également définir la position de chaque mot dans le document en question.

what

Attends, attends ! tu peux la refaire celle là ?

Ok, un exemple vaut mieux que mille discours !

mettons que j’ai 3 documents dont voici les contenus:

doc 1- création d’un moteur de recherche cours pratique et information: créer
doc 2- créer un moteur de recherche et indexation
doc 3- crawler et indexer le web grace à un moteur

dans un premier temps, nous allons tout d’abord procéder à notre normalisation, nous obtiendrons ainsi:

1- cré moteur recherche cour pratique inform cré
2- cré moteur recherche index
3- crawl index web moteur

Nous pouvons maintenant créer notre index inversé comme ceci:

cré:[1,2];moteur:[1,2,3];recherche:[1,2];cour:[1]; ainsi de suite

cela veut dire que le mot “cré” est contenu dans les document 1,2,et3. le mot cour n’est contenu que dans le doc 1.

l’étape d’après c’est de rajouter la position de chaque mot au sein du document.

Euh, la po… quoi?

La position d’un mot est la distance qui le sépare du début du document. Ainsi dans le document 1, cré est en position 0, moteur est en position 1, inform est en position 5

Notre index inversé deviendra donc un vecteur contenant l’ensemble du mapping de chaque mot avec le corpus de documents.

cré:[1:[0,6],2[0]];moteur:[1:[1],2[1]]…etc

en d’autres termes, le mot “cré” est présent dans le doc 1. C’est le premier mot du document (position 0) et aussi le 5ième.

Vous voyez le genre? OK !

question

Attend, j’ai une question: Pourquoi on s’emmerde à stoker la position du mot dans le document?

Ah, en voici une bonne question :)

En fait, cette information est très utile. Elle nous permet de savoir:

1- l’occurrence du mot dans le document. Nous avons vu que dans le cadre de notre calcul de score de ranking TF IDF TF veut dire Term Frequency. Il nous permet de savoir si un terme est fréquent au sein d’un document. Avec ce vecteur, il est très facile pour nous de savoir la densité d’un mot au sein d’un document. Il suffit de calculer la taille du tableau contenant les positions.
2- il nous permet de savoir si une expression (groupe de mots) est présente exactement dans le meme ordre que celui entré par l’utilisateur.
3- il nous permet de booster le score d’un mot en fonction de sa présence dans le haut ou le bas de l’article.

Bon ok, continuons.

Il faut faire ca pour tous les mots issus de l’ensemble des documents de notre corpus. Pour schématiser, voir à quoi ressemble le processus d’indexation dans le cadre d’un moteur de recherche.

index

 

Comme vous pouvez le voir, ça re-prend exactement le vecteur que nous avons commencé à constituer un peu plus haut. Je pense que le schéma est très clair. Inutile de commenter plus ;)

La loi de Zipf

Pour finir sur cette partie, j’aimerais vous parler de cette règle mathématique. La zipf”s law explique que la distribution de termes dans une collection suit une logique assez particulière: la fréquence d’un terme au sein d’un document est inversement proportionnelle à son ranking. Du coup, le mot le plus fréquent dans un document apparait 2 fois plus que le second mot le plus important. il est 5 fois plus fréquent que le cinquième mot le plus important, etc.

zipf

 

Voila, nous avons réussi à construire notre index inversé. Prochain rendez vous à l’étape 2 qui est celle de l’utilisation de cet index pour trouver les documents les plus pertinent pour une expression donnée.

A plus !

Leave a Reply

Name
Name*
Email
Email *
Website
Website