Créer un moteur de recherche avec des logiciels libres

  • Published on
    24-May-2015

  • View
    4.910

  • 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

<ul><li> 1. [ Jeudis du Libre, Mons Mercredi 16 mai 2012 ]Crer un moteur de recherche avecdes logiciels libres Auteur: Dr Ir Robert Viseur</li></ul><p> 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 &amp; System Engineering : qualit logicielle (fiabilit, scurit, respect des normes internationales, processus,...). Software &amp; Services Technologies : architectures orientes services et smantique. Embedded &amp; 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 -&gt; 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 = -&gt; q = OR -&gt; , 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.-&gt; pas adapt de gros volumes de donnes (&gt;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) Crawler: Wget. Extraire: Lecture de flux RSS ou Atom: Feedparser (Java, Python), Simplepie (PHP), etc. Extraction de texte et de mtadonnes: Apache Tika / POI (Java), utilitaires (xls2csv, catdoc, pdfinfo,etc.), iFilters (propritaire, disponible sous Windows), etc. Extraction darticles (contenu utile) : Boilerpipe (Java). OCR: GOCR, OCRAD, Tesseract, etc. 36 37. Existence de composants spcialiss (2/3) Analyser: Stemming: Snowball (Java). Rtroingnierie de pages Web: DEiXTo, Web Harvest, etc. TAL: OpenNLP (Java), NLTK (Python), etc. Dtection de langue: Language-detection (Java), NLTK (Python),Text_LanguageDetect (PHP), etc. Extraction dentits (nommes ou pas): OpenNLP (Java), UIMA (Java), Stanbol, etc. 37 38. Existence de composants spcialiss (3/3) Indexer: Indexation (SGBD): MySQL, PostgreSQL, etc. Indexation (indexeur): Lucene (Java), Whoosh (Python), Zend Search (PHP), etc. Rechercher: Classification: Mahout (Java), NLTK (Python), Reverend (Python), etc. Composer: Mtamoteur: Carrot. Divers: Bases de donnes: DBPedia (Wikipedia), Geonames (base de donnes gographique), etc. Remarque: existence de trs nombreux petits projets spcialiss et parfoistrs utiles. 38 39. Et pourquoi pas du logiciel propritaire ? Existence de technologies propritaires reconnues pour lindexation. Exemples: Dtsearch, Oracle TEXT, etc. Point fort: trs large couverture fonctionnelle, performances de haut niveau. Point faible: prix, lock-in technique. Le monde Java est aliment par des projets de recherche (publics ouprivs) en traitement de linformation. Exemples(logiciels libres) : UIMA, Stanbol, Nepomuk, etc. Existence dalternatives en Python (parfois) et, dans une moindre mesure, enMicrosoft .Net (C#, ASPX, etc.). Existence doutils gratuits (mais non libres). Exemples: TreeTagger, Sentiwordnet, etc. 39 40. Exemples pratiques: cration demoteurs de recherche spcialiss 40 41. Exemple 1: moteur de recherchede podcasts Objectif: Sur base dune liste de podcasts (fichiers RSS)... Indexer le contenu des flux RSS... En distinguant... Les descriptifs de chaque fichier RSS et... Les descriptions de chaque ressource multimdia rfrence... Et permettre des recherches par mots-clefs.41 42. Outils rutiliss Lecture RSS: Feedparser (Python). Indexation: MySQL (fulltext). Fonctionnement simple (extension du SQL): Cration de la table avec index: CREATE TABLE news ( id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY, title VARCHAR(256), content TEXT, FULLTEXT (title, content) ) Recherche par mot-clef: SELECT id, title, content, MATCH (title,content) AGAINST (linux) AS score FROM news WHERE MATCH (title,title) AGAINST (linux) ORDER BY score42 43. Rsultat Exemples de rsultat de recherche: 43 44. Exemple 2: moteur de recherchede flux RSS Objectif: dcouvrir, indexer et rechercher desflux RSS.44 45. Outils Indexation via Zend Search (voir exemple 3). Dveloppement spcifique: crawler. Dveloppement Python utilisant urllib, string, sgmlparser et threading. Crawler (Python) spcialis dans la dcouverte de flux RSS. Principe: sur base dune liste dURL (amorce), le crawler (multi-thread) ouvre les pages daccueil, identifie les flux RSS et Atom (et les ajoute une liste), extrait les noms de domaine des liens sortants, et ajoute ces noms de domaine aux URLs visiter. But: explorer peu de pages HTML mais trouver un maximum de flux de syndication en un minimum de temps et avec un minimum de bande passante. 45 46. Rsultat Collecte aise de plusieurs dizaines de milliers deflux RSS et Atom, en franais, anglais, nerlandaiset espagnol. Recherche avance: par mots-clefs, par pays, parlangue, restriction possible aux podcasts.46 47. Exemple 3: moteur de recherche dentreprises Point de dpart: donnes de lannuaireLogiciellibre.com. Objectif: A partir dune base de donnes dadresses dentreprises actives dans le logiciel libre... Crer un index Web spcialis... Pour identifier les entreprises actives sur certaines technologies et tudier leur environnement. 47 48. Outils rutiliss Crawl: Wget. Indexation: Zend Search. Extraction dentits: Boilerplate, OpenNLP. Visualisation: WUI et DOT.48 49. Wget (1/2) Utilitaire GNU en ligne de commande, compatibleLinux ou Cygwin, permettant de rcuprer desfichiers en utilisant HTTP, HTTPS et FTP. Commande de base: wget www.cetic.be Stocke localement la page situe ladresse www.cetic.be. Commande pour un crawl: wget -r -l2 -P www -R jpg,gif,png http://www.cetic.be Crawl rcursif de profondeur 2 pour le site http://www.cetic.be et rsultats du crawl dans le rpertoire www (+ rejet des photos).49 50. Wget (2/2) Multiples options: -r (crawl rcursif) Par dfaut: respect de la convention norobots -l (profondeur de rcursion) -P (rpertoire cible pour le stockage) -A et -R (filtrage des URLs par pattern) --user-agent (user agent impos) ... Plus dinfos: http://www.gnu.org/software/wget/manual/ . Alternative: curl (puissant mais... pas de crawlrcursif). 50 51. Lucene (1/2) Outil dindexation support par la fondation Apache(lucene.apache.org). Ec...</p>