Créer un moteur de recherche avec des logiciels libres

  • View
    4.911

  • Download
    3

Embed Size (px)

DESCRIPTION

Lorsque lon parle de moteur de recherche, les noms de Google, Bing ou Yahoo! viennent immdiatement lesprit. La taille de ces moteurs (plusieurs milliards de pages indexes), limportance des infrastructures (grands centres de donnes) et la pertinence des rsultats de recherche peuvent donner limpression que les dveloppements spcifiques sont devenus impossibles ou sans intrt. La cration de moteurs de recherche spcialiss reste cependant possible, et utile pour certains usages particuliers (ex.: moteurs de recherche dentreprise, mise en place de systmes de veille, etc.). Pour ce faire, le dveloppeur peut sappuyer sur les interfaces de programmation (API) gnralement mises disposition par les moteurs de recherche commerciaux mais aussi sur les trs nombreux composants et logiciels libres existants. Ces derniers couvrent la collecte des donnes textuelles, leur analyse, leur indexation et leur prsentation. La prsentation dtaille les diffrentes tapes de cration dun moteur de recherche. Les outils libres disponibles, ainsi que leurs limites et cadres dutilisation privilgis, sont ensuite prsents.

Transcript

  • 1. [ Jeudis du Libre, Mons Mercredi 16 mai 2012 ]Crer un moteur de recherche avecdes logiciels libres Auteur: Dr Ir Robert Viseur

2. Qui suis-je? Robert Viseur Ingnieur Civil, Mastre en Management delInnovation, Docteur en Sciences Appliques. Spcialis dans les questions relatives lconomiedes logiciels libres et aux pratiques de co-cration,ainsi que dans les technologies de recherche et detraitement de linformation (outils dindexation,API,...). Assistant la Facult Polytechnique de lUniversitde Mons (www.umons.ac.be). Conseiller technologique au CETIC (www.cetic.be).2 3. Quest-ce que le CETIC? Centre dExcellence en Technologies de lInformation etde la Communication bas Charleroi (Belgique). Trois dpartements (et types de services): Software & System Engineering : qualit logicielle (fiabilit, scurit, respect des normes internationales, processus,...). Software & Services Technologies : architectures orientes services et smantique. Embedded & Communication Systems : prototypage de systmes embarqus communicants et nouvelles technologies lectroniques. 3 4. De quoi allons-nous parler? Sujet: comment crer un moteur de recherche base de logiciels libres? Plan: Quest-ce quun moteur de recherche? Faut-il utiliser une base de donnes fulltext ou un pur indexeur? Jusquo est-il utile de dvelopper soi-mme? Exemples: cration de moteurs de recherche spcialiss.4 5. Quest-ce quun moteur de recherche ? 5 6. DfinitionUn moteur de recherche est une application permettant de retrouver des ressources (pages web, articles de forums Usenet, images, vido,fichiers, etc.) associes des mots quelconques(Wikipedia). 6 7. tapes de fonctionnement Crawler. Collecter automatiquement les documents que lon souhaite chercher sur un rseau local ou sur Internet. Extraire. Extraire le contenu textuel (texte et mtadonnes) des ressources collectes. Enrichir. Trouver et ajouter de nouvelles informations sur base du contenu et de la structure du document. Analyser Analyser le contenu textuel (en vue de son indexation). Indexer. Transformer le contenu textuel en une forme facilitant la recherche par un ordinateur. Rechercher. Proposer une interface de recherche pour des utilisateurs (WUI) ou des logiciels (API). Composer Associer un ensemble de sources de rsultats complmentaires. 7 8. Crawler Rseau Internet: Ouvrir les pages Web issues dun ensemble de pagesWeb de dpart. Extraire des liens prsents dans les pages Web. Suivre ces liens (dcouverte automatique dInternet). Rseau local: Suivre larborescence de rpertoires, faire linventairedes fichiers disponibles. ventuellement, constituer une copie locale desfichiers indexer. Attention aux droits daccs aux documents (scurit)! 8 9. Extraire (1/5) Lindexation se fait sur du texte brut (texte oumtadonnes). Besoin dextraire... le contenu textuel associ au document / la ressource... et/ou associ son contexte (ex.: vido ou photo insre dans un document HTML).9 10. Extraire (2/5) Complexit variable. Trs simple pour du texte. Simple pour du (X)HTML ou du XML (RSS, Atom,FOAF, etc.). En pratique: Texte avec des balises (tags). Plus ou moins bien form. Exemple: HTML.10 11. Extraire (3/5) Complexit variable (suite). Besoin danalyseurs spcialiss pour les formats binaires (ex.: photos, vidos, documents bureautiques, etc.). Extraction des mtadonnes. Exemple: tags ID3 dans les fichiers MP3. 11 12. Extraire (4/5) Complexit variable (suite). Besoin danalyseurs spcialiss pour les formats binaires (suite). Extraction du texte. Exemple: fichier dans le format ouvert ODT (fichiers XML et autresressources zippes. Plus difficile si formats non documents.12 13. Extraire (5/5) Complexit variable (suite). Beaucoup plus difficile pour les documents scanns (OCR).(...)13 14. Enrichir (1/3) Il est possible daller plus loin que la simpleextraction des mtadonnes et du texte. Pour les documents HTML: Comprhension des microformats. Exemple: hCard / vCard.14 15. Enrichir (2/3) Pour les documents HTML (suite): Rtroingnierie (extraction structure -> redonner du sens aux informations formates en HTML).15 16. Enrichir (3/3) Pour les contenus textuels: Extraction dentits nommes. Exemple: reconnatre des noms de personnes,dorganisations, de villes, de pays, des dates, etc. Autre possibilit: exploiter des logiciels, des basesde donnes ou des services externes pour enrichirle document. Exemples: langue du document, catgorisation, etc. 16 17. Analyser (1/2) Gnralement, cette tche est ralise parlindexeur lui-mme. Degr de sophistication variable. Base: segmentation du texte par tokenization. Les phrases sont dcomposes en lments simples. Possibilit (ou non) de configurer des rgles defiltrage. Exemple : suppression des mots trop courts, suppression des stops words, etc. 17 18. Analyser (2/2) Degr de sophistication variable (suite). Lemmatisation. Transformation des mots indexer en lemme (formecanonique). Exemple: avoir = ai, as, a, avons, eussions eu, aurions, etc. But: amlioration du rappel du moteur de recherche(parfois au dtriment de la prcision). Ncessite un dictionnaire dans la langue du document indexer. Procd voisin (plus basique) sur base de rgles de troncature (stemming). Exemple: algorithme de Porter.18 19. Indexer (1/3) Cration dun index invers. Typiquement: structure mettant en correspondance des mots avec un ensemble de documents. La recherche dun ou plusieurs mots permet de facilement retrouver les documents le ou les contenant.19 20. Indexer (2/3) Vue (trs) simplifie: = = Index: pos=1 pos=2 pos=3 pos=1 pos=2Requtes:q = -> q = OR -> , 20 21. Indexer (3/3) Modle de pertinence intgr. Un classique: modle TFxIDF. La frquence dapparition de chaque terme dans un document est pondre par la frquence du terme dans le jeu de documents. volutions possibles: classement fonction de lalocalisation, de la structure des liens (cf. GooglePagerank), etc. 21 22. Rechercher (1/2) Proposer une interface dinterrogation du moteur. Pour humains (Web User Interface, WUI). Pour logiciel (Application Programming Interface, API). Raffinements possibles: catgorisation, clustering,factisation, etc. 22 23. Rechercher (2/2) Remarque: Les moteurs de recherchecommerciaux proposent une API (Google, Bing,etc.). Passage progressif au modle payant. Conditions dutilisation parfois restrictives. Problmes de fiabilit (cf. webomtrie). Mais utilit: pour initier des crawls, pour disposer de listes dURLs cibles (analyse en profondeur), pour complter des rsultats de recherche (composition).23 24. Composer Plusieurs sources de donnes peuvent trecombines. Exemples: principe du mtamoteur, lien avec des bases de donnes smantiques.24 25. Faut-il utiliser une base de donnesfulltext ou un pur indexeur ? 25 26. Bases de donnes simples (1/2) Base de donnes = tables de donnes (lignes /colonnes) lies (via des clefs / identifiants). Typage des donnes, contraintes dintgrit. Language dinterrogation standardis proche dulanguage humain (SQL). Large disponibilit doutils de cration. Par dfaut, pas de fonctionnalit fulltext.26 27. Bases de donnes simples (2/2) Recherche de texte possible par: Recherche de sous-chanes de caractres via "LIKE". Sous-chanes != mots. Filtrage ncessaire avant affichage. Recherche possible via des expressions rgulires.-> pas adapt de gros volumes de donnes (>100.000 lignes par table).27 28. Base de donnes fulltext Mmes caractristiques que pour la base de donnessimple, mais... Cration automatique dun index invers. Performances variables: volume de donnes support (nombre denregistrements, longueur du texte), finesse danalyse du texte (lemmatisation ou non, personnalisation de lanalyse ou non, etc.), richesse variable du langage dinterrogation, support variable des langues (si lemmatisation). Le langage dinterrogation de lindex fulltext variedun SGBG un autre. 28 29. Pur indexeur Outil ddi uniquement la recherche fulltext. Plus de structure tabulaire, de contraintesdintgrit, ni de language dinterrogationuniversel. En gnral: conu pour grer de gros volumes de texte, facilement embarquable dans un logiciel, possibilits de personnalisation du comportement, syntaxe dinterrogation riche, notion de champs (sans contrainte). 29 30. Technologies libres Bases de donnes fulltext: MySQL (mode fulltext), PostgreSQL (Tsearch2), Sphynx Search (extension pour MySQL et PostgreSQL). Pur indexeur: Lucene, ports Lucene, Xapian, Whoosh, etc. Rapide comparatif: Remarque: couvertures fonctionnelles variables.30 31. Jusquo est-il utile de dvelopper soi-mme?31 32. Approches possibles Trois approches possibles: Utilisation doutils intgrs. A utiliser sils sont adapts. Dveloppement ex nihilo (DIY). A dmarrer si un avantage fonctionnel peut tre trouv. Dveloppement sur base de composants libres. A privilgier si pas doutil intgr disponible. Suite: prsentation non exhaustive de logicielslibres disponibles.32 33. Existence doutils intgrs (1/2) Serveur dindexation: SolR (lucene.apache.org/solr/). Comprend: extracteurs (Apache Tika), indexeur (Lucene), API (JSON ou REST). Mtamoteurs: Carrot (mtamoteur, clustering; carrot2.org). Seeks (mtamoteur, P2P; seeks-project.info).33 34. Existence doutils intgrs (2/2) Moteur de recherche intgr: Nutch (nutch.apache.org). Comprend: crawleur, extracteurs, indexeur, WUI et API. Bas sur SolR. Fonctionnel avec Internet ou Intranet. Moteur de recherche complet dcentralis (P2P): YaCy (yacy.net). Comprend: crawleur, extracteurs, indexeur, WUI et API (OpenSearch).34 35. Plusieurs de langages deprogrammation adapts au Web Plusieurs languages de programmation libresadapts au Web. Exemples: Python, Perl, Java, Ruby, PHP, etc. Possibilit de dveloppements sur mesure... Bas sur des bibliothques rutilisables Exemple: gestion des threads, ouverture dURLs, analyse detextes, analyse HTML, etc. Attention au syndrome NIH...35 36. Existence de composants spcialiss (1/3) Craw