Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

10/11/2021 1 Bases de données multimédias II - Bases de données documentaires 1

10/11/2021 1 Bases de données multimédias II - Bases de données documentaires 1. Recherche documentaire 2. Moteurs de recherche 3. Recherche plein texte: index inversé 4. Technique d’indexation 5. Modèles de recherche d’information 6. Approches par navigation A,U 2021-22 Faculté des Sciences de Monastir Proposé par: Mr Samir Belaid 1. Recherche documentaire • Problème de la recherche des entités et des documents (également appelés collection ou corpus) en réponse aux requêtes des utilisateurs. • Le corpus est composé de documents d'une ou plusieurs bases de données, qui sont décrits par un contenu ou par les métadonnées associés. • Les entités recherchées pouvant être connues ou inconnues aux utilisateurs. • Il existe différents choix pour poser une requête : – Recherche par une seule entité (R1E), – Recherche par plusieurs entités (RPE), – Recherche par mots clés (RMC), • Un Système de Recherche d’Informations (SRI) exploite à la fois l’ensemble des informations et la requête, et infère par un mécanisme les informations les plus pertinentes à la requête. 10/11/2021 2 • Plusieurs concepts clés peuvent être définis : – Besoin d'information : Trois types de besoin assimilé à l’utilisateur : Besoin vérificatif (dit stable): l'utilisateur cherche à vérifier le texte avec les données connues qu'il possède déjà. Il recherche une donnée particulière, et sait souvent comment y accéder. Exemple: Rechercher un article sur Internet à partir d'une adresse connue ou la date de publication d'un ouvrage dont la référence est connue. Besoin thématique connu : l'utilisateur cherche à clarifier, à revoir ou à trouver de nouvelles informations dans un sujet et un domaine connus. Peut être stable ou variable : il est possible que le besoin de l'utilisateur s'affine au cours de la recherche. S'exprimer de façon incomplète, l'utilisateur n'énonce pas tout ce qu'il sait dans sa requête mais seulement un sous-ensemble (appelé label). 1. Recherche documentaire Besoin thématique inconnu : L'utilisateur cherche de nouveaux concepts ou relations. Le besoin est variable et exprimé de façon incomplète. – Modèle de représentation : Processus pour extraire d’un document (ou requête) une représentation paramétrée qui couvre au mieux son contenu sémantique. Ce processus de conversion est appelé indexation. o Le résultat de l’indexation constitue le descripteur du document/requête, (liste de termes), pour différencier le contenu sémantique d’une unité. o L’ensemble des termes reconnus sont rangés dans une structure appelée dictionnaire constituant le langage d’indexation. – Modèle de recherche (noyau d’un SRI): o Fonction de décision qui permet d’associer à une requête, l’ensemble des documents pertinents à restituer. o Etroitement lié au modèle de représentation des documents. 1. Recherche documentaire 10/11/2021 3 • Couplage entre Base documentaire et Base d’index documentaire • Les données du SRI sont gérées classiquement par une base documentaire (MySQL, Postgres, MongoDB) • On extrait de la base tous les documents à indexer et on en fait des indexes. • Pourquoi ne pas utiliser directement le moteur de recherche comme un gestionnaire de documents ? – N’est pas adapté aux fonctionnalités d’une base de données. o Facilite la recherche et l’accès aux documents. – S’appuie sur des structures compactes, compressées et optimisées (index inversés ou fichier inversés). Serveur de documents (eg MongoDB) Base documentaire Index documentaire Indexation Recherche structurée Moteur de recherche (El. Search, Solr) Recherche structurée et plein-texte Application Synchronisation Requête/Résultat Put/Post/Get Architecture d’un système d’information avec un moteur de recherche 2. Moteurs de recherche 2. Moteurs de recherche • On peut améliorer les performances des moteurs de recherche à l’aide de plusieurs techniques : – Requêtes plus structurées o requêtes booléennes, o expressions rationnelles, o proximité, o recherche d’expression – Résultats classés o modèle vectoriel o PageRank o analyse sémantique latente • Moteurs libres: Apache Solr (Lucene), ElasticSearch (Lucene), Sphinx, Xapian • Moteurs commerciaux: Google Search Appliance, Exalead, Qwant, Amazon CloudSearch, Microsoft Azure Search, Bing,… Exemple de moteurs de recherche 10/11/2021 4 3. Recherche avec index inversé Exemple 1 de base Soit l’ensemble suivant de documents qui nous servira de guide. d1 Lucene est une bibliothèque de recherche moderne. d2 Lucene a subi d'importants changements d'applications. d3 Apache est utilisé dans une vaste bibliothèque. d4 Applications mobiles, ordinateurs de bureau, à l'échelle Internet. d5 Apache Lucene Fournit des interfaces pour effectuer de bibliothèque. d6 Apache Lucene Indexer, interroger, analyse Twitter. d7 Les applications de Apache nécessitent 4 Go de RAM et 8 Go de DDR. d8 Lucene Alimente deux applications: Netflix et Instagram. Ici, on fait abstraction aux étapes de pré-traitement et on examine uniquement la construction d'un index inversé de base par indexation basée sur le tri. 3. Recherche avec index inversé Parcourir tous les documents ? (appelé Grepping relatif à la commande Grep de l’Unix) • Potentiellement long; • Critère ”pas de Bibliothèque” n’est pas facile à traiter; • Autres types de recherche plus difficile (”le mot ’ Lucene’ doit être près du mot ’Apache’”); • Comment classer par pertinence les documents trouvés ? Structure spécialisée : la matrice d’incidence et son inversion. Besoin (Requête) On veut chercher tous les documents parlant de: Lucene, Apache mais pas Bibliothèque. Solution 10/11/2021 5 3. Recherche avec index inversé • Après pré-traitement des documents, on sélectionne un ensemble de mots (ou plutôt termes), constituant notre vocabulaire (ou dictionnaire / lexique). • Documents en ligne, termes en colonnes. Dans chaque cellule : 1 si le terme est dans le document, 0 sinon. Modèle Booléen lucene apache appliquer bibliotheque indexer twitter d1 1 0 0 1 0 0 d2 1 0 1 0 0 0 d3 0 1 0 1 0 0 d4 0 0 1 0 0 0 d5 1 1 0 1 0 0 d6 1 1 0 0 1 1 d7 0 1 1 0 0 0 d8 1 0 1 0 0 0 Matrice d’incidence Pour effectuer la recherche 3. Recherche avec index inversé On prend les vecteurs d’incidence de chaque terme contenu dans la requête, soit les colonnes dans notre représentation : • lucene : 11001101 • apache : 00101110 • bibliotheque : 10101000 Puis, on en déduit les documents en réponse à la requête : • ET logique sur les vecteurs de lucene et apache, on obtient 00001100. • ET logique avec le complément du vecteur de bibliotheque (01010111) On obtient donc 00000100, d’où la réponse qui est limitée au document d6 (le “1” de la 6ième position). Opération binaires très efficace, mais... 10/11/2021 6 • Avec des données à grande échelle, cette approche soulève quelques problèmes. • Exemple, posant les hypothèses suivantes : – Un million de documents, mille mots chacun en moyenne. – Disons 6 octets par mot (espaces et ponctuation compris), soit 6 Go!!! – Disons 500 000 termes distincts – la matrice d’incidence a : o 106 lignes et 500 000 colonnes soit 500×109 bits o soit 62 Go approximativement Ceci ne tient pas en mémoire… ce qui complique les choses. Recherche à grande échelle 3. Recherche avec index inversé Comment faire mieux ? • Mettre les termes en lignes associées (on parle de listes inversées ou vecteurs d’incidences); ceci est important en terme de structure de données. – Facilite les opérations logiques, – Permet un stockage dans une zone mémoire contigue et donc un accès simple et rapide. • On obtient donc la structure suivante: lucene apache appliquer bibliotheque indexer twitter 1 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 • Les mises à jour sont plus difficiles car elles impliquent la réorganisation des listes compactes. 3. Recherche avec index inversé Solution Inconvénient Chaque "1" de la liste (par terme) correspond à un document contenant le terme L'étape de base de l'indexation consiste à trier les termes, par ordre alphabétique. 10/11/2021 7 3. Recherche avec index inversé • Etant la matrice est creuse (Sur chaque ligne, il y a plus de "0" que des "1" ≈1/500), Il devient plus interessant de garder les "1" et non pas les "0". • Aussi, on remplace les "1" par les identifiants des documents correspondants (). • Chaque liste est ensuite triée suivant le . • Pour obtenir une nouvelle structure appelée index inversé lucene apache appliquer bibliotheque indexation twitter 1 2 5 6 8 3 5 6 7 2 4 7 8 1 3 5 6 6 À chaque terme est associé une liste inversée Solution On suppose que chaque document a un numéro de série unique, appelé identificateur de document (). • La structure utilisée dans tous les moteurs de recherche est: – Un répertoire contient tous les termes. – Une liste (inversée) est associée à chaque terme, triée par . – Chaque élément de la liste est appelé une entrée. – Concept : la notion de terme (token en anglais) est différente de celle de “mot”. • Vocabulaire : – le répertoire est appelé dictionnaire (ou sac de mots), – les entrées des postings, – les uploads/Science et Technologie/ mp-bases-de-donnees-multimedia-2.pdf