Indexation automatique

Pour les articles homonymes, voir Indexation.

L’'indexation automatique est un domaine de l'informatique et des Sciences de l'information et des bibliothèques qui utilise des méthodes logicielles pour établir un index pour un ensemble de documents et faciliter l'accès ultérieur aux documents et à leur contenu.

Processus d'indexation automatique

La méthode souvent la plus efficace d’indexation automatique pour l'utilisation de fichiers séquentiels est l'indexation (elle est également utilisable pour les autres types de données, stockées en mémoire). Les composantes sont stockées dans le fichier dans l'ordre de leur création. On utilise alors un tableau d'index, donnant en première position le numéro de la première composante, puis de la seconde,... L'avantage de cette méthode est que l'ajout de composantes est optimal : on rajoute la valeur en fin de fichier, on met à jour le tableau d'index. Tout déplacement d'une composante sera donc remplacé par une modification du tableau d'index, sans déplacement réel de la valeur dans le fichier. En général, ce tableau peut tenir en mémoire, ce qui permet une modification rapide, en général on préfère le sauver également sur support magnétique avant de quitter le programme, ce qui évitera de le recréer (par exemple refaire un tri) à la prochaine utilisation. On peut également utiliser une liste d'index si les déplacements sont fréquents (mais alors l'accès devient séquentiel). Le second avantage de cette méthode est que l'on peut utiliser simultanément plusieurs index : par exemple pour une liste de personnes, on peut créer un index pour le classement alphabétique des noms, un autre sur les villes, on accédera donc plus rapidement à tous les champs indexés, alors que les champs non indexés devront se satisfaire d'une recherche séquentielle, et ce sans modification dans le fichier (un tri par nom puis par ville auraient été nécessaires sans indexation). Par contre toute modification nécessitera la mise à jour de tous les tableaux d'index. La suppression, par contre, pose problème. En général, toujours pour éviter les décalages dans les fichiers, on préfère marquer d'un signe distinctif les champs supprimés (par exemple un nom non alphabétique ou vide), puis remettre à jour les index qui ne pointeront plus sur ce champ. Le retassage, assez long, n'est effectuée que sur ordre de l'utilisateur ou lorsqu'il quitte le programme. On peut aussi (comme dans la méthode du super-tableau) créer une liste des champs vides, ce qui permettra d'y accéder, plus rapidement que par une recherche séquentielle, lors de la prochaine insertion.

Sur un fichier indexé, on peut à nouveau se permettre des algorithmes utilisant l'insertion, puisque celle-ci n'affecte que l'index (à accès rapide). Pour un tri par exemple, on pourra utiliser le tri par insertion, à condition d'optimiser la recherche de la position d'insertion (par dichotomie pondérée par exemple), puisque celle-ci nécessite des lectures de champs dans le fichier alors que l'insertion n'entraîne que des décalages dans un tableau, d'une durée généralement négligeable devant le temps pris par la recherche. On peut également utiliser une liste d'index plutôt qu'un tableau si nécessaire. (créée par un programme informatique), ou à divers degrés intermédiaires « assistée » ou semi-automatique (par exemple créée par un humain assisté d'un programme proposant des termes). L'indexation manuelle d'informations est généralement coûteuse : pour indexer correctement un texte scientifique d'un certain niveau, il faut faire intervenir des personnes qui soient elles-mêmes capables de comprendre le contenu du texte, ce qui impose un coût non négligeable.

Indexation de textes

Un index est en toute généralité, une liste de descripteurs à chacun desquels est associée une liste des documents et/ou passages de documents auxquels ce descripteur renvoie. Ce renvoi peut être pondéré. Lors de la recherche d'information d'un usager, le système rapprochera la demande de l'index pour établir une liste de réponses.

Un index très simple à établir automatiquement est la liste ordonnée de tous les mots apparaissant dans les documents avec la localisation exacte de chacune de leurs occurrences ; mais un tel index est volumineux et surtout peu exploitable.

L'indexation automatique tend donc plutôt à rechercher les mots qui correspondent au mieux au contenu informationnel d'un document. On admet généralement qu'un mot qui apparaît souvent dans un texte représente un concept important. Ainsi, la première approche consiste à déterminer les mots représentatifs par leur fréquence. Cependant, on s'aperçoit que les mots les plus fréquents sont des mots fonctionnels (ou mots outils, mots vides). En français, les mots « de », « un », « les », etc. sont les plus fréquents. En anglais, ce sont « of », « the », etc.

Il est évident que l’on ne peut pas garder ces mots à haute fréquence mais peu porteur de sens en terme. C’est pourquoi on introduit dans les moteurs de recherche des opérations de filtrage de ces mots. Ces listes de mots sont appelées anti-lexiques ou plus fréquemment stoplist^[1].

Une autre opération est ensuite couramment appliquée lors de l'indexation. Elle consiste à effacer les terminaisons (flexions de nombre, genre, conjugaison, déclinaison) afin de retrouver les racines des mots. Cette opération est appelée stemming (une autre solution voisine appelée lemmatisation conduit globalement au même résultat). Ce procédé permet de relever les fréquences en cumulant les nombres d'occurrence des variations des mêmes mots.

Chaque unité documentaire (chaque document ou chaque passage de document) peut alors faire l'objet d'une représentation vectorielle : les coordonnées représentent les fréquences des mots non vides. Lorsque l'on effectue cette opération pour un corpus de documents ou de pages web on obtient une matrice dont les colonnes représentent un document et les coordonnées la fréquence des termes.

Les moteurs de recherche de première génération s'appuient sur des formules de pondération, généralement pour affecter un poids élevé aux termes non-distribués uniformément au sein du corpus. Il existe un grand nombre de formules de pondération dont le but et de distribuer le poids pour contribuer à la différentiation informationnelle des documents. Certaines formules de pondération harmonisent les poids en fonction de la longueur des documents où la fréquence des termes est globalement plus élevée, d'autres formules s'appuient sur la fréquence maximale des termes afin de concilier l'aspect multi-thématique d'un document avec des documents mono thématiques. Les formules de pondération les plus connues sont TF-IDF^[2] (term frequency . inverse document frequency).

Les moteurs de seconde génération s'appuient non seulement sur la fréquence des termes pour indexer les pages web mais aussi sur la popularité des sources. En naviguant de lien en lien, les robots indexent les termes utilisés par une page web pour décrire une autre page web. À chaque fois qu'un utilisateur suit ce lien, il « vote » la pertinence des descripteurs utilisés. Le page-ranking est ensuite calculé selon la popularité des descripteurs et un coefficient de similarité issu de la modélisation vectorielle.

Indexation d'images

L'indexation d'images consiste apres analyse de tous les pixels ou d'une partie réduite (masque) de transformer l'information des pixels en un autre type d'information de telle sorte que la recherche d'image (a l'identique, ou de même catégorie) soit facilité (en terme informatique, taille compacte, vitesse, tout en conservant une sémantique proche de l'utilisateur). Les premiers système d'indexation des images ont utilisés la couleur (systeme QBIC IBM), plus tard l'analyse des couleurs par histogramme c'est a la fois amélioré et diversifié. Plusieurs modeles de representations des couleurs ont été utilisés, des raffinement de l'histogramme global primitif ont été introduits. Les améliorations de l'histogramme couleur ont surtout portés sur l'ajout d'information spatiales a l'origine totalement absentes. Les meilleurs algorithmes actuels de reconnaissances utilise une dérivée de l'image. Seule une partie des points plus important que d'autres sont analysés précissement. Im n'existe pas de système connu permetant d'égaler les performances humaines. On peut toutefois affirmer qu'il existe des solutions industrielles (univers restreint) qui sont économiquement viables. La méthode des SIFT de D.Lowe fait souvent référence en matière de description multi echelle invariante par rotation et translation.

Indexation sonore

Indexation vidéo

Notes et références

Voir aussi

• Moteur de recherche
• Recherche d'information
• Robot d'indexation
• Spamdexing

• Portail de l’informatique