Jump to content
Sign in to follow this  
Spidetra

Inside an inverted index

Rate this topic

Recommended Posts

Les moteurs de recherches n'utilisent pas un SGBD pour stocker et indexer les informations.

Ils utilisent une structure connu sous le nom de : Inverted Index.

Ce post essaye de décrire ce que je comprend de la structure d'un inverted index.

J'espère que les zones d'ombres pourront être complété par les experts du Hub

1. Les fichiers qui composent un inverted index

iiindex.jpg

Un inverted index est composé de segments. Dans notre exemple nous avons un seul segment _0.

Un segment est composé de différents fichiers.

En particulier certains fichiers ont des extensions du type : .fnm, .tis, .frq, .prx

Nous verrons un peu plus bas à quoi correspondent ces fichiers.

Un des fichiers important de ce répertoire est le fichier segment.

Ce fichier liste tout les segments présents dans notre inverted index.

Dans notre exemple nous n'avons qu'un seul segment : _0

Le moteur de recherche va se baser sur ce fichier pour savoir quels sont les noms des fichiers d'index qu'il devrat manipuler.

Dans notre exemple, ce sont les fichiers _0.fnm, _O.tis, _O.frq, _0.prx qui vont nous intéresser.

Le fichier deletable contient des informations sur les documents qui ont été marqués pour suppression.

Les fichiers ayant des extensions .fN ( N étant un nombre entre 0 et 8 dans notre exemple ) contiennent des informations sur

les champs présents dans les documents indéxés.

Dans notre exemple nous verrons que les 9 champs présents sont :

anchor, content, dccreator, dctitle, host, site, tag, title, url

2. Le fichier .fnm : liste les noms des champs

iiifieldname.jpg

Ce fichier contient la liste de tout les champs composant l'inverted index.

Vous pouvez voir que j'ai configuré mon crawler pour prendre en compte

les méta Dublin Core ( dc:title et dc:creator )

Pour chacun de ces champs des flags indiquent les propriétés du champs : I, T, S, V

I : Indexed => Le champ est indéxé

T : Tokenized => Le champ est tokenize ( Découpé en mot )

S : Strored => Le champ est stocké

V : Vector => ???

3. Le fichier .tis : Dictionnaire des termes

iiifieldvalue.jpg

Ce fichier contient tout les termes de l'index.

Un terme est un tuple contenant : Nom du champ et valeur du champ.

Un terme de notre exemple :

dctitle: XMLParser parse XMLData using Namespace and XPath

Ce fichier contient aussi un document frequency.

Cette valeur correspond au nombre de document du segment qui contiennent ce terme.

4. Les fichiers .frq et .prx : fréquences et positions des termes

Ces deux fichiers listent les fréquences et les positions des termes dans

l'ensemble des documents composant le segment.

La structure d'un inverted index est un compromis entre deux chemin :

- maximum de performance

- minimum de ressources utilisées.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...