Data Mining : les principes d’interrogation d’une base de données

Le Big Data est résolument tourné vers la valorisation et l’exploitation de la donnée. Le contexte actuel et la majorité des approches de gestion de projet  (les méthodes agiles, SCRUM, KANBAN, Lean, Six Sigma, SAFe, …) exigent que les salariés et l’ensemble des professionnels de l’entreprise aient un accès opportun à l’information. Comme décrit dans Managing for results, l’ouvrage du père du management moderne Peter Drucker, les professionnels et les salariés dans une entreprise doivent être dirigés par l’autorité de la connaissance au lieu de l’autorité hiérarchique. Cela signifie que ceux-ci doivent être autonomes et pouvoir décider eux-mêmes dans leur sphère de responsabilité, au lieu d’attendre qu’un chef de la hiérarchie vient leur dire quoi faire. C’est d’ailleurs une des valeurs promues par les méthodes agiles. Cette autonomie n’est possible que s’ils peuvent interroger les données générés par les systèmes opérationnels de l’entreprise pour en extraire de l’information. Dans la plupart des cas, ces données sont centralisées dans des bases de données exploitées encore dans une grande majorité de cas par des systèmes de gestion de bases de données relationnelles (SGBDR). Les SGBDR, en s’appuyant sur le SQL, offrent des fonctionnalités de recherche de contenu qui sont très limitées à la fois en termes de type, de varieté de contenu et de volume. La récupération des données est malheureusement synonyme des requêtes ayant une forme similaire à celle-ci :

CopySELECT 
 co.*, cl.* 
FROM 
 Commandes as co, Clients as cl
WHERE 
cl.client_ID = co.cmd_ID AND
co.date_cmd > to_date('2016-09-09', 'yyyy-mm-dd') AND 
UPPERCASE(cl.client_Name) = “CHOKOGOUE” AND
LOWERCASE(cl.client_FirstName) = “Juvénal” AND
Co.produit LIKE '%big data%';

Hélas, comme vous pouvez le constater vous-même, le SQL n’est pas efficace lorsqu’il s’agit d’exprimer des requêtes d’une certaine complexité et dégrade même la performance du système avec l’augmentation du volume de données dans la base.  Combinez maintenant ceci avec le volume, la variété et la vélocité des données en Big Data et vous comprenez rapidement pourquoi beaucoup d’entreprises souffrent de l’incapacité qu’ont leurs employés à retrouver du contenu dans leurs fichiers et pourquoi rendre l’information « découvrable » est l’une des plus grandes problématiques du Big Data.

Dans ce tutoriel, nous allons vous montrer comment résoudre les difficultés liées à la recherche de contenu, les approches de data mining efficaces pour interroger ou retrouver de l’information dans un vaste ensemble de contenu comme une base de données, ou des pages Web. D’une manière générale, comment aborder les problématiques relatives à la recherche d’information.

Dans le tutoriel précédent relatif à ElasticSearch, nous avons expliqué qu’il existe deux approches pour résoudre les challenges liés à la recherche de contenu : la classification hiérarchique,  et l’indexation de contenu.

Les premières approches de recherche de contenu se faisaient par classification des documents. Mais avec l’explosion des données qui caractérise le Big Data, cette approche de recherche de contenu n’est plus valide. Dans les années 95, Altavista a été le première entreprise à permettre la recherche de questions en langage naturel et à intégrer les techniques de recherche avancées (techniques dérivées d’une branche de data mining appelée Knowledge Management, comprenant elle-même des algorithmes de NLP – Natural Langage Processing). Pour éviter le balayage linéaire de chaque page web au moment de la soumission de la requête, un « index » de tous les termes de requête possible est préparé à l’avance.  Cette technique, appelée indexation de contenu est aujourd’hui la méthode de recherche utilisée.

L’indexation de contenu permet de réaliser les recherches en se basant d’une part sur un index et d’autre part sur un score de similarité qui attribue un niveau d’importance à chaque résultat de recherche.

1. Les challenges associés à la recherche de contenu

Les approches de recherche et d’indexation de contenu tirent leur essence de la croissance explosive d’Internet.  La croissance explosive d’Internet elle-même peut être attribuée majoritairement à la décentralisation de la création de contenu qui se fait désormais sans aucun contrôle sur la  paternité de l’auteur du contenu. Cette décentralisation a eu pour inconvénient majeur la perte de fiabilité du contenu web. En effet, la publication de contenu web mélange des faits, des rumeurs, des suppositions et même des contradictions. En plus, les contenus web qui sont considérés comme fiables pour certains ne le sont pas nécessairement pour les autres.  Avec les moteurs de recherche qui deviennent le moyen principal de découverte de contenu web, les approches d’indexation de contenu n’ont plus juste pour but de retrouver le contenu, mais de fournir des métriques de mesure de fiabilité de chaque page web indépendante de l’appréciation des utilisateurs qui permet au moteur de recherche de classer les résultats de requête par ordre d’importance.  

L’approche traditionnelle de recherche d’information sur les pages web et  autres types de fichiers (documents structurés, tables des bases de données relationnelles, documents semi-structurés ou non-structurés) s’appuie sur les mots-clés : l’utilisateur saisit sa requête, le moteur de recherche  vérifie l’existence de ces mots dans tous les documents qu’il stocke. Par exemple : supposons que nous faisons la recherche suivante,  « Bob Smith », le moteur de recherche va regarder tous les documents et renvoyer celles qui contiennent soit le mot Bob, soit le mot Smith, soit alors le mot Bob Smith. Exprimée en SQL, qui jusqu’aujourd’hui le langage principal d’interrogation des bases de données, notre requête serait formulée ainsi :

CopySELECT * FROM table_Clients WHERE name LIKE « Bob Smith » ;

Bien que le moteur renvoie les documents/résultats, l’approche par mots-clés comporte beaucoup de limites :

•  Premièrement, si les mots-clés que vous saisissez sont différents des mots utilisés dans le document, certains documents ne seront pas renvoyés.  En effet, en fonction du format du document, certains éléments peuvent ne pas être encodés dans la partie visible par les utilisateurs. Par exemple, les noms d’auteur, les dates, bref les éléments qui sont qualifiés de métadonnées. Le moteur n’est pas nécessairement capable de distinguer les mots-clés des  métadonnées. Ceci est un problème de précision ;
• Deuxièmement, les utilisateurs cherchent en réalité les documents dont l’auteur est « Bob Smith », mais certains documents renvoyés par le moteur de recherche ont pour auteur « Robert Smith ». Ceci est un problème d’intention véritable de l’utilisateur ;
• Troisièmement, l’utilisateur recherche « Bob Smith », mais le moteur de recherche renvoie des documents qui ne le satisfont pas parce que « Bob Smith » a changé son nom il y’a trois mois et l’a remplacé par « Météor de l’été ». Ceci est un problème de mise à jour des documents ;
• Dernièrement, l’utilisateur recherche les documents contenant « Bob Smith », mais le moteur de recherche lui renvoie les documents contenant  « bob Smith » à cause de la non-prise en compte de la casse (caractères en majuscules/minuscules). Ceci est un problème de sémantique ;

Ainsi, de façon inhérente, la recherche basée littéralement sur les mots-clés ne tient pas compte du contexte de chaque mot-clé et des informations qui peuvent être inférées de ces mots. Les systèmes de recherche qui sont basés sur les mots-clés littéraux ne fournissent aucun outil linguistique et sémantique pour trouver des éléments précis dans les documents. La précision, l’intention, la mise à jour et la sémantique sont autant de besoins qui ont orienté la recherche de l’information vers les techniques d’indexation de contenu.

2. Les bases de la recherche et l’indexation de contenu

Altavista en 1995 a été le premier moteur de recherche à permettre la recherche des questions en langage naturel et à intégrer les techniques de recherche avancées (algorithmes automatisés de data mining sspécialisés sur la recherche de contenu à large échelle) basées sur l’indexation. Pour éviter le balayage linéaire de chaque page web au moment de la soumission de la requête, un « index » de tous les termes de requête possible est préparé à l’avance.

De façon formelle, un index est une liste ordonnée de mots clés. Pour que vous compreniez le principe de l’indexation de contenu, supposons la collection des livres de français d’une bibliothèque. Pour réaliser une recherche de contenu dans ces livres, l’approche la plus simple consiste à tracer tous les mots de chaque livre de la bibliothèque. En répétant cette opération à travers tous les livres, on obtient ce qui s’appelle dans le jargon une matrice d’incidence de termes dans laquelle chaque cellule indique si un mot spécifique survient dans un livre ou pas.

La figure ci-après illustre l’échantillon de la matrice d’incidence de termes des livres de français de notre exemple. L’ensemble des documents sur lesquels le moteur de recherche effectue les recherches de contenu est appelé le « corpus« . Ainsi, pour un corpus d’un million de documents possédant chacun 100 000 mots distincts, à peu près 10 Go  (1 million * 100 000) seront nécessaires pour contenir l’index sous sa forme matricielle. Le corpus lui-même requerra à peu près  4 octets pour encoder chaque mot distinct et par conséquent un total de 4 Go (1 million * 1000 * 4) d’espace de stockage sous l’hypothèse que chaque document contient 1000 mots en moyenne. Vous voyez que beaucoup d’espace est gaspillé dans l’enregistrement de l’absence des termes dans le document. Une meilleure approche serait d’enregistrer uniquement les occurrences qui apparaissent.

La structure d’index la plus efficace est l’index inversé, une collection de listes, une par terme, indiquant l’ensemble des documents contenant ce terme. Chaque élément dans la liste pour un terme t, encore appelé « posting » (nous allons l’appeler « valeur » pour simplifier la lecture) indique l’identifiant du document  d, et la fréquence d’apparition du terme t dans le document (on parle de Term Frequency – TF) : <d, tf>. Notez que si 4 octets sont utilisés pour encoder chaque valeur, un terme apparaissant dans 100 000 documents résulterait à une liste de valeur d’une taille comprise entre 100 Ko et 1 Mo. La figure suivante illustre l’index inversé correspondant au tableau  précédent.

Dans notre exemple précédent, la langue de tous les termes des livres était connue d’avance (le français). Cela n’est en général pas le cas dans les fichiers non-structurés comme les pages web, où les auteurs créent des contenus dans une multitude de langages, avec une large variation de grammaires et de style. Les pages Internet sont très souvent criblées de texte de couleurs et de font variés, ainsi que d’images qui entraînent un contenu textuel qui s’enrichit lorsqu’on clique dessus, ne fournissant ainsi aucune structure sémantique claire. En plus, les caractères sont encodés en utilisant des formats d’encodage différents tels que l’UTF-8 ou des formats d’encodage propriétaires. Etant donné que le composant visible d’une page web pourrait éventuellement être utilisé comme terme de requête, l’index inversé doit aussi inclure tous les mots prononcés, les nombres, les constructions telles que AF-420 ou X-86, et les jetons d’authentification apparaissant dans les URL. Cette collection de termes dans un index est conventionnellement appelé un « dictionnaire » ou un « lexique« . Les dictionnaires et les listes de valeurs (qui forment l’index inversé) sont les structures de données centrales utilisées dans l’indexation de contenu en général et les moteurs de recherche ou d’interrogation de bases de données en particulier. Dans la suite, nous allons voir comment avec les problématiques liées à la décentralisation de création de contenu, le dictionnaire de l’index inversé peut être formé.

3. Techniques data mining de construction de l’index

L’efficacité de l’index inversé est étroitement liée à la capacité de bien construire son dictionnaire. Celui-ci est construit à partir des mots contenus dans les fichiers.  A l’introduction de cette partie, nous avons mentionné  que la création de contenu sur Internet est sujet à plusieurs problèmes tels que la sémantique des mots, les différents langages utilisés, pour ne citer que ces deux là. Il existe des techniques que vous pouvez utiliser pour construire le dictionnaire de l’index tout en évitant ces problèmes. Ce sont ces techniques que nous voulons vous fournir ici.

Pour des raisons d’efficacité, un identifiant est utilisé pour représenter chaque terme dans le dictionnaire. Ce mapping est fait soit à la volée lors du traitement du corpus entier, soit en deux phases. La première phase compile le dictionnaire tandis que la deuxième phase construit l’index. Dans les deux cas de figure, la première phase consiste à transformer chaque document en liste de jetons et à utiliser des algorithmes de Data Mining appelés algorithmes de linguistique naturelle (NLP – Natural Langage Processing) pour les normaliser en termes d’index. Ceci implique des simples traitements comme le découpage des phrases selon les espaces vides, l’élimination des caractères de ponctuation, l’analyse de l’utilisation de l’apostrophe, la normalisation en minuscule de tous les mots. Les documents ont également tendance à contenir différentes formes grammaticale pour le même mot, par exemple « marche« , « marches« , « marchons« , « marchant« .  

Le Stemming est une technique NLP qui dérive les mots pour en récupérer le sens. Certains termes appelés formellement « Stop words » comme « le« , « la« , « je« , etc., forment la structure de base des phrases et sont par conséquent extrêmement nombreux dans les documents. Cependant, malgré leur volume, ils apportent une faible valeur dans la recherche et l’indexation de contenu. De plus, à cause de leur fréquence élevée, ils posent des problèmes de performance. Ces mots peuvent donc être supprimés du dictionnaire de l’index sans aucune crainte.  Voici les techniques courantes provenant du Data mining de traitement naturel de texte utilisées pour raffiner le dictionnaire des indexes inversés, ainsi que des recherches de contenu : le stemming, l’Entity extraction, l’expansion de synonymes, la recherche de caractère générique, la recherche de proximité, les mots mal prononcés et les N-Gram.

• le Stemming : c’est une technique de data mining spécialisé dans le traitement de langage naturel  qui permet aux utilisateurs d’inclure les variations de la racine d’un mot dans une recherche tout en faisant toujours référence à la racine du mot. Par exemple, si une personne cherche et saisit l’un des mots suivants « marche« , « marches« , « marchons« , ou « marchant« , le moteur renverra les mêmes résultats ;
• l’Entity extraction ou extraction d’entité : c’est une technique de NLP qui permet de trouver et d’étiqueter les entités du texte. Les objets tels que les dates, les noms de personnes, les noms d’entreprise, les noms de produits, les noms de zones géographiques sont des exemples d’entités qui peuvent être étiquetés par un programme d’extraction d’entité. Le moyen le plus courant d’étiquetage de texte est l’utilisation d’un moteur NoSQL natif XML, par exemple MarkLogic fournit des fonctions qui trouvent et étiquettent automatiquement des entités de votre texte. Nous y reviendrons plus bas ;
• l’expansion de synonyme : c’est une technique de data mining textuel qui consiste à inclure  les synonymes de mots clés spécifiques dans les résultats de recherche. Par exemple, si un utilisateur cherche le mot « PC« , alors en utilisant l’expansion de synonyme, les résultats vont également inclure les mots « laptop« , « tablette« , « ordinateur« , parce que ce sont des synonymes de la même réalité. La base de données WordNet[1] est un bon exemple de base incluant les synonymes à inclure dans une recherche ;
• la recherche de caractère générique : c’est une technique qui consiste à ajouter des caractères spéciaux pour indiquer au moteur que plusieurs termes correspondent à la requête. La majorité des SGBD possèdent des modules de recherche de caractère générique. Par exemple, un utilisateur peut spécifier une requête telle que « téléphon* »  ou « téléphon?« pour indiquer que les mots téléphoner, téléphone, téléphones, téléphonons sont valides comme résultats de recherche. l’astérisque (*) indique plusieurs caractères et le point d’interrogation (?) indique un seul caractère après le mot racine. Apache Lucene par exemple permet de faire la recherche basée sur les caractères génériques au milieu du mot. Nous y reviendrons dans le chapitre suivant. D’autres moteurs permettent de ‘ajouter le caractère spécial dès le début du mot. Par exemple « *cadre » pour renvoyer les mêmes résultats que encadre ou recadre ;
• la recherche de proximité : c’est une technique de data mining textuel qui permet de rechercher les mots qui sont proches des autres mots dans le document. Ici, vous indiquez que vous êtes intéressés par exemple par tous les documents qui ont le terme « femme » et le terme « ordinateur » séparés de 20 mots les uns des autres. Les documents dans lesquels ces deux termes sont les plus proches recevront un score de classement plus élevé dans les résultats ;
• les mots mal-prononcés : Si l’utilisateur a mal saisi un mot-clé dans le formulaire de recherche et que le mot en question n’est pas dans le dictionnaire de la langue, le moteur de recherche retournera une phrase du style « est ce que vous vouliez dire ceci ? » et lui proposer des alternatives de mots pour la recherche. Cette fonctionnalité exige que le moteur de recherche soit capable de trouver les mots similaires au mot mal-saisi ;
• les N-Gram : c’est une technique bien classique du data mining textuel (NLP) qui consiste à sectionner les longues chaînes de caractère en N chaînes courtes de taille fixe. Ces chaines sont ensuite ajoutées au dictionnaire de l’index pour effectuer les recherches. Par exemple un 4-Gram consiste à découper tous les mots d’un texte dont en 4 caractères chacun. supposons le mot  « anticonstitution« . Le 4-Gram de ce texte donne les mots indexés suivants : « anti », « cons », « titu » et « tion ». L’intérêt du N-gram est de retrouver des similarités dans le corpus ;

4. Modèles d’intelligence artificielle de recherche de contenu

Vous avez maintenant compris que les problématiques de recherche de contenu se résolvent en deux phases : l’indexation de contenu et la recherche de contenu. La construction de l’index va en général se faire à travers le paradigme MapReduce ou suivant les algorithmes de data mining textuel que nous avons fournis plus haut. Grâce à ces algorithmes, 6 types (ou modèle) de recherches de contenu sont possibles : la recherche textuelle intégrale (full text Search), la recherche géographique, la recherche réseau, la recherche facetté, la recherche vectorielle et la recherche N-Gram.

• La recherche textuelle intégrale : communément référencé par l’expression anglaise full text search, les requêtes de recherche  textuelle intégrale effectuent des recherches linguistiques sur des données textuelles dans des documents structurés ou non, en traitant les mots et les expressions à partir des règles spécifiques d’une langue telle que le français, l’anglais ou le japonais. A cause de la multiplicité des langues, les moteurs d’indexation de contenu qui offrent les fonctionnalités de recherche textuelle intégrale sont obligés de choisir les langues qu’ils vont supporter. La prise en charge d’une langue demande obligatoirement la prise en charge d’un ensemble de ses composants linguistiques spécifique à cette langue, à savoir un analyseur lexical et générateur de formes dérivées (un analyseur lexical détecte les limites de mots en fonction des règles lexicales définies pour la langue. Chaque analyseur lexical est associé à un générateur de formes dérivées qui conjugue des verbes pour la même langue), une liste de mots vides ou stop words, et un dictionnaire de synonyme ;
• La recherche géographique ou géolocalisation : ce type de recherche consiste à géolocaliser un ou plusieurs points par rapport à un point de référence. les résultats sont retournés sur la base du calcul des distances géographiques, du plus proche du point de référence au moins proche. Par exemple, vous voulez obtenir les hôtels qui sont situés à 5 minutes de véhicule de votre localisation actuelle. Techniquement, la géolocalisation est un procédé permettant de positionner un objet sur un plan ou une carte à l’aide de ses coordonnées géographiques latitude/longitude. Cette opération est réalisée à l’aide d’un terminal capable d’être localisé en temps réel ou différé grâce à un système de positionnement par satellites et un récepteur GPS par exemple. Les comparateurs de site d’hôtels par exemple fournissent une interface qui s’appuie sur des fonctionnalités de recherche géographique et qui renvoie une carte contenant la liste des hôtels qui répondent aux critères d’utilisateur et qui sont les plus proches de sa position. Dans ce cas, le moteur de recherche ne stocke pas nécessairement les informations concernant la disponibilité des hôtels, mais il accède à leurs données en se connectant directement à leur site web. Les résultats sont renvoyés en fonction d’un score qui mesure la différence entre les critères de requête de l’utilisateur et les informations renvoyés par les différents sites web. La figure suivante illustre un exemple de recherche géographique faite sur le comparateur d’hôtel Trivago ;

• La recherche réseau : Ce type de recherche consiste à retourner les résultats de recherche en fonction des informations que vous trouvez dans les graphes, par exemple des graphes de réseaux sociaux (interrogation d’un graphe). Par exemple, vous pourriez vouloir inclure dans votre recherche uniquement les restaurants auxquels vos amis ont noté par 5 étoiles. C’est ce type de recherche qui est utilisé pour interroger les graphes des réseaux sociaux comme Facebook, LinkedIn ou Twitter ;
• la recherche facetté : c’est tune technique algorithmique de recherche qui consiste à accéder aux informations sur la base d’un ensemble de facettes. C’est la recherche facettée qui permet d’effectuer le type de requête similaire à celle-ci – « renvoyer tous les documents d’une catégorie précise et à une date précise« . Vous pouvez voir les facettes comme des catégories de sujet qui réduisent l’espace de recherche. Elle donne aux utilisateurs les moyens  de filtrer les documents en choisissant un ou plusieurs critères (les facettes).  Une classification à facettes associe à chaque donnée de l’espace de recherche un certain nombre d’axes explicites de filtrage, par exemple des mots clés issus d’une analyse texte, des métadonnées stockées dans une base de données, etc. On trouve par exemple des recherches à facettes basées sur des catégories sur de nombreux sites de e-commerce ;
• la recherche vectorielle : la recherche vectorielle est un processus algorithmique de data mining qui consiste à classer les résultats d’une recherche sur la base de leur proximité par rapport aux mots-clés en utilisant un modèle de distance multidimensionnel. L’ensemble des documents dans ce cas est un vocabulaire comprenant des termes d’indexation. Ceux-ci sont typiquement les mots les plus significatifs du corpus considéré : noms communs, noms propres, adjectifs… Ils peuvent éventuellement être des constructions plus élaborées comme des expressions ou des entités sémantiques. À chaque élément du vocabulaire est associé un index unique arbitraire. Chaque contenu est ainsi représenté par un vecteur v, dont la dimension correspond à la taille du vocabulaire. Chaque élément vi du vecteur v consiste en un poids associé au terme d’indice i et à l’échantillon de texte. Un exemple simple est d’identifier vi au nombre d’occurrences du terme i dans l’échantillon de texte. La composante du vecteur représente donc le poids du mot i dans le document. L’un des schémas de pondération les plus usités est le TF-IDF ;
• la recherche N-Gram : la recherche N-gram est une technique de NLP (data mining textuel) qui consiste à sectionner les chaînes de caractère en N chaînes de taille fixe. Ces N chaines sont ensuite indexées pour et utilisées pour faire des recherches par mot-clé ;

Un moteur qui implémente ces modèles de recherche, ainsi que les algorithmes d’intelligence artificielle ou de data mining nécessaires à la construction de l’index vous aidera à résoudre vos problématiques de recherche de contenu.

5. Utilisation de l’index lors d’une requête

Maintenant regardons comment la recherche de contenu proprement dite est faite en utilisant l’index inversé. Pour illustrer cela, considérons une  requête contenant 4 termes ou mots-clés. La première étape d’exécution de cette requête consiste à trouver ces termes dans le dictionnaire. Pour ce faire, les listes de valeur correspondant aux 4 termes est récupérée (et chargée en mémoire si l’index était stocké sur le disque dur), entrecoupant ainsi les documents dans les quels ils sont stockés. A la deuxième étape, le moteur de recherche récupère les documents contenant les termes des listes de valeur, en commençant par le terme dont la fréquence est la plus faible (puisque sa liste de valeurs  est la plus faible, elle pointe sur le moins de documents que toutes les autres listes). A la dernière étape, l’ensemble des documents est présentée à l’utilisateur de façon classée et réordonnée. Etant donné la faible taille du corpus, ces trois étapes peuvent se faire à l’échelle de la seconde.  Les pages sont retournées à l’utilisateur dans un ordre différent de celui dans lequel ils apparaissent dans l’index. Pour classer les pages, une métrique de mesure de similarité est utilisée, celle-ci évalue le niveau de proximité des documents à la requête des utilisateurs. Le principe sous-jacent étant que plus le score de similarité est élevé, plus est  la probabilité que la page corresponde aux besoins et aux intentions véritables de l’utilisateur est élevée. Google a été le premier à appliquer ce principe à large échelle. Il a développé l’algorithme PageRank, un algorithme basé sur l’analyse de similarité qui attribue une note d’importance à chaque page web. Tous les moteurs de recherche de contenu utilisent ce principe actuellement dans le but de fournir des résultats de grande fiabilité rapidement.  Avec le nombre astronomique et continu de pages web actuellement disponible, mettre à l’échelle ce principe demande l’optimisation des ressources informatiques et l’utilisation des clusters. Dans la partie suivante, vous allez comprendre les approches informatiques qui sont mises en œuvre pour ce faire.   

6. Les composants d’un système informatique d’indexation et de recherche de contenu

A ce stade, vous connaissez les choix disponibles pour construire un index qui va s’exécuter à l’échelle. Dans ce point, nous allons entrer dans les détails de l’indexation à large échelle proprement dit. En 2004, le moteur de recherche de Google traitait plus de 200 million de requêtes par jour sur plus de 20 Téra octet de données, en utilisant un cluster de plus de 20 000 nœuds. Pour réussir cet exploit, les moteurs de recherche s’appuient sur deux composants informatiques majeurs : un Système de Fichier Distribué et un algorithme d’indexation de contenu (indexeur de contenu). Le Système de fichier distribué permet de gérer le stockage et la redondance des  documents indexés, tandis que l’algorithme profite du parallélisme et de la scalabilité du cluster pour faire l’indexation et la recherche de contenu dans les documents. Chez Google cet algorithme est le MapReduce. Nous allons voir comment le système de fichier distribué et l’indexeur de contenu sont utilisés  pour l’indexation de contenu à grande échelle.

6.1. Le système de fichiers distribués

Un moteur de recherche est construit à partir d’une copie du web (une copie de tous les sites Internet disponibles sur la toile). Cette copie est stockée localement. Ainsi, indexer le web signifie indexer individuellement toutes les pages de chaque site Internet disponible dans tout le Web. Si on fait l’hypothèse  que chaque site web a une taille moyenne de 30 Mo et sachant qu’il y’a plus de 100 milliards de pages Web disponibles actuellement, alors il faut autour de 3 Po (Péta octets) d’espace disque rien que pour le stockage des pages.  Ainsi, il faut au minimum 6 Po (soit 6144 To) de disque dur au système informatique pour l’indexation et la recherche (documents initiaux + copie). Si nous supposons des configurations de disque dur de 500 Go, alors il faudra un cluster de plus de 12 000 nœuds pour stocker une seule copie du Web et son index (hors mis l’espace nécessaire pour la redondance des données). Comme nous l’expliquons dans l’ouvrage « Maîtrisez l’utilisation des technologies Hadoop », pour gérer de tels volumes de données, il faut utiliser un système de fichier distribué installé sur un cluster de machines. Le rôle du système de fichier distribué est de fournir un accès distant aux fichiers, le transfert de fichier, la tolérance aux pannes et la concurrence d’accès aux fichiers. Malgré la disponibilité de plusieurs systèmes de fichier distribué, Google a décidé de développer son propre système de fichier distribué, principalement pour pouvoir l’optimiser aux besoins propres à son moteur de recherche. Une fois que le moteur de recherche est appuyé sur un système distribué de fichier efficace, on peut développer un indexeur qui va créer un seul index pour toutes les pages à travers les nœuds du cluster et y rechercher du contenu. Cet indexeur est nécessairement un algorithme parallèle.

6.2. L’algorithme d’indexation de contenu

Une fois que le moteur de recherche est adossé sur un système de fichiers distribués efficace, la deuxième composante du système est de développer l’indexeur de contenu. Compte tenu de la nature du traitement ici, cet algorithme se fait nécessairement trois étapes : la lecture des termes du dictionnaire de l’index sur chaque noeud, la récupération des documents de ces termes et l’agrégation des documents en fonction de la liste des valeurs. Google a été le premier a développé un modèle algorithmique distribué et tolérant aux pannes qui réalise ces trois étapes : le Map ->Shuffle ->Reduce ou MapReduce tout simplement. Dans le premier ouvrage du projet Hadoop – Devenez opérationnel dans le monde du Big Data, nous parlons du fonctionnement du MapReduce dans l’indexation des pages Web en profondeur.

• le Map : dans cette étape,  le noeud maître assigne à chaque tâche une partition de document. La fonction Map s’exécute sur chaque noeud de calcul et transforme le contenu de la partition de documents en paires de clés/valeurs  où la clé est le terme de la requête dans le dictionnaire de l’index et la valeur est l’identifiant du document, par exemple son nom, son URL, etc. ;
• le Shuffle : dans cette étape, les paires de clé/valeurs précédemment générées sont triées par ordre de clé, autrement dit par ordre de terme, ce qui permet de regrouper l’ensemble des documents qui contienne chaque terme. Cette étape est optionnelle ;
• le Reduce : ici, le noeud maître récupère les résultats de l’étape Shuffle et les agrège en fonction de la technique définie par le programmeur pour obtenir les résultats finaux qui vont être renvoyés à l’utilisateur ;

Pour plus de détails sur le fonctionnement du MapReduce, rendez vous à l’ouvrage Hadoop – Devenez opérationnel dans le monde du Big Data,. L’avantage du modèle MapReduce dans l’indexation de contenu comme nous l’avons montré précédemment est qu’il masque la complexité de l’exécution parallèle des tâches aux yeux du développeur et passe facilement à l’échelle avec l’accroissement de la complexité du système et des ressources disponibles. De plus, en cas de panne d’un noeud, le noeud maître peut simplement re-planifier les tâches qui s’exécutaient sur ce noeud vers d’autres nœuds. Tout ceci se fait sans l’intervention du développeur. Nous allons maintenant voir le lien entre l’indexation de contenu et les SGBD NoSQL d’indexation de contenu.

---

Ressources complémentaires

Pour approfondir votre apprentissage sur les problématiques de recherche de contenu, les approches automatisées de résolution des problématiques d’interrogation de bases de données, n’hésitez pas à vous appuyer sur les ressources suivantes :

• [1]  WordNet est une base de données dans laquelle les noms, verbes, adjectifs et adverbes sont organisés en jeu de synonymes, chacun représentant un concept lexical sous-jacent.  Site officiel de WordNet https://wordnet.princeton.edu/
• pour en savoir plus sur les fonctions d’interrogation de base de données relationnelles du SQL, reférez-vous à la documentation de la norme ISO/IEC 13249-3:2011 : https://www.iso.org/standard/53698.html
• voici un bon tutoriel sur l’implémentation de la recherche intégrale rédigé par Microsoft : https://docs.microsoft.com/fr-fr/sql/relational-databases/search/full-text-search?view=sql-server-ver15

Lectures recommandées

Pour aller plus vite sur les problématiques de recherche de contenu et d’interrogation des bases de données, nous vous recommandons vivement les ouvrages suivants :

Vous avez aimé cet article ? Cliquez sur les boutons de réseaux sociaux suivants pour le partager et permettre à vos collègues/amis d’en bénéficier.