LTAL, Projet : Moteur de recherche

Idée : Ce projet est un exercice en construction et l'application d'un moteur de recherche à partir d'outils de haut niveau, concrètement : Whoosh de Matt Chaput. Voir aussi la doc. Ceci est une librairie en Python pur, destiné à faciliter la construction des codes de recherche, d'indexation, etc. On travaillera sur l'indexation, la pertinence, etc. On peut en profiter pour la construction des correcteurs orthographiques (il gère les codes basés sur la distance de Levenshtein). La librairie dispose de plusieurs algorithmes du domaine, par ex. de la ranking function BM25F (une variante du tf-idf, voir Wikipédia), des procédures d'analyse des textes, des parseurs de requêtes, etc. Plusieurs choses ici peuvent vous être utiles, en toute indépendance de ce projet et de l'option TAL. Installez Whoosh chez vous et lisez la documentation. (Elle n'est pas idéale, et manque de vrais exemples.) Whoosh a été partiellement inspiré par Lucene, une populaire et efficace machinerie de recherche, écrite en Java, la base d'un populaire serveur de recherche textuelle : Solr ; les deux appartenant au monde Apache, donc libres et bien maintenus.

Énoncé

Vous devez ensuite tester le système sur une configuration grandeur nature. Par exemple, vous essayerez d'indexer deux de mes dossiers d'enseignement qui vous doivent être connus : https://karczmarczuk.users.greyc.fr/TEACH/TAL/, et ... /TEACH/PyObj/ (pas la peine de faire plus !). Il vous faudra suivre récursivement les liens, et traiter seulement les fichiers .html. Après l'indexation on peut passer à la recherche.

• Cherchez l'usage des noms de langages de programmation : Python, Java, Haskell, et (peut-être?) quelques autres, avec leurs fréquences et positions (des chaînes dans le document, non pas dans les numéros des mots. Concrètement : les numéros de lignes, comme dans notre exemple d'indexation du livre de Verne). Affichez toutes les lignes de tous les documents qui contiennent ces mots.

Introduction

Cependant, le vrai problème de recherche inclut :

• Recherche dans plusieurs documents, parfois très nombreux. En principe, l'indexation de plusieurs documents est similaire à l'indexation individuelle, on considère un document comme une "section" nommée d'un "super-document", mais ils peuvent être très nombreux, et parfois il faut les actualiser sélectivement. Le processus d'indexation d'un site Web peut inclure le suivi des liens, et l'indexation récursive des cibles. Il est obligatoire de reconnaître des documents déjà indexés, limiter la profondeur récursive, ne pas aller n'importe où (par ex., ne jamais sortir de la racine du site).
• L'indexation n'est presque jamais en vrac (tous les mots sans distinction préalable). L'index doit constituer une sorte de base de données structurée, où on distingue des catégories des termes (les champs) : l'auteur, la date d'émission, le titre, le contenu, l'URL du site, etc. Cette structuration s'appelle le schéma d'index. Selon la catégorie du document, on trouve des champs assez variés ; par ex. dans l'indexation des mails ou des discussions dans des blogs, on trouve la nécessité d'indexer les sujets, l'adresse du destinataire (peut-être différent de celle du propriétaire du blog), etc.
• Un requête peut chercher un terme concret, ou plusieurs liés par des opérateurs Booléens (ET, OU, NON). Aussi, on peut chercher des phrases : combinaisons des termes voisins (donc, il faudrait stocker les positions des termes cherchés dans le document). En général : le processus d'indexation est une action "professionnelle", où la règle est : l'efficacité, mais la recherche est une activité des utilisateurs, et elle doit être commode. L'indexeur ET le parseur des requêtes doivent inclure la lemmatisation des termes. La construction des interfaces de recherche est une tâche très importante, mais elle dépasse largement les bornes de ce cours...
• La réponse est - normalement - la collection de documents qui répondent à la requête, et elle peut être volumineuse, donc le classement des résultats partiels selon leur pertinence est très important. Ceci a été abordé en cours, mais, bien sûr, sans trop de détails. Vous devez apprendre comment on réalise dans la pratique le modèle d'espace vectoriel, et aussi l'approche tf-idf (term frequency – inverse document frequency), afin de savoir comment classer les documents.
• Il ne faut pas confondre l'indexation et la recharche dans une base documentaire, avec la recherche sur le Web. Cette dernière inclut le parcours à travers le graphe des liens par des robots "crawlers" ou "spiders" (la terminologie française n'est pas stable ; on parle de "collecteurs"). Whoosh n'est pas un crawler. L'utilisateur doit lui fournir la liste de documents, avec leurs chemins d'accès, afin de les indexer, et vous allez le faire (probablement) aussi. Faire un crawler intelligent qui ne confond pas les liens et les non-liens, qui ne se bloque pas à cause de liens faux ou cycliques, qui ne s'égare pas dans des rédirections trop profondes, etc., n'est pas trivial. Il existe un bon nombre de crawlers gratuits, en particulier un paquetage Python connu : Scrapy (mais qui ne marche toujours pas sous Python 3 ; ceci est prévu, mais l'attente est longue). Un autre crawler, BeautifulSoup est également à votre disposition (et je l'utilise...). Son installation est facile, mais faites attention avec les librairies de support, comme html5lib ou lxml.

  [Ceci dit, si dans l'avenir, comme des dizaines de milliers d'informaticiens vous opterez pour Python comme votre outil de travail sur le Web (Java n'est pas le langage qui domine sans partage, malgré quelques affirmations sectaires...), vous serez obligés de maîtriser les modules et paquetages standard (distribués avec Python) d'accès au Web comme urllib ou urllib2, avec l'extension Requests, la librairie lxml, etc. Ceci mène à la nécessité d'apprendre des outils système en Python, les modules os, shutil, etc. Python n'est pas qu'un langage, mais comme Java, il constitue un environnement de travail. ]

  Un indexeur pur comme Whoosh peut indexer votre site Web, si vous avez l'accès direct, actif, au système de fichiers qui le composent. Pour un site qui réside sur un serveur distant, ceci est plus difficile, voire impossible (il faut pouvoir lancer une application sur le serveur).

Comment collecter les documents d'un répertoire et d'un site Web.

Files ; outils standard

import os
f=os.walk(chemin, params ...)

[   (   '..',
        ['Doc', 'GD', 'Gra', ...],
        ['36180.pdf', 'apptre.html', 'Automates-nombre.gv', ...]),
    (   '..\\Doc',
        ['nxdoc'],
        [   '- Building Probabilistic Models For Natural Language.pdf',
            '0703109v2.pdf',
            '1_1_Brunet.pdf',
            ...]),
    (   '..\\Doc\\nxdoc',
        ['examples', 'reference', 'tutorial', ...],
        ['.buildinfo', 'bibliography.html', 'contents.html', ...]),
    (   '..\\Doc\\nxdoc\\examples', ...
   ...
    (   '..\\TB',
        ['dec'],
        [   'test1.txt',
            'test1.xml',
            'treebolic-installer-2.0.6-20130131.exe',
            ...]),
    ('..\\TB\\dec', [], []),
   ...
  ]

Web crawling

import urllib.request as ur
dc=ur.urlopen("https://karczmarczuk.users.greyc.fr/TEACH/TAL/Master.html")
doc=dc.read()

from bs4 import BeautifulSoup as BS
soup = BS(doc)

for lnk in soup.find_all('a'):
    x=lnk.get('href'); if x: print(x)

https://dias.users.greyc.fr/?op=paginas/tal.html
#attent
http://nltk.org/
http://nltk.org/book/
tp0609.html
tp1309.html
...
proHyph.html
proTree.html
proEng.html

Afin de suivre les liens, il faut savoir reconstruire les URLs à partir des fragments, et aussi éliminer les éléments inutiles. Le module urllib.parse facilite l'analyse des chaînes qui décrivent l'accès Web. Exemple :

from urllib.parse import urlparse
o = urlparse("https://dias.users.greyc.fr/?op=paginas/tal.html")

ParseResult(scheme='https', 
            netloc='dias.users.greyc.fr', 
            path='/',  params='', 
            query='op=paginas/tal.html', 
            fragment='')

BeautifulSoup peut faire beaucoup plus, récupérer les balises concrètes (ou leurs hiérarchies), ou des éléments de la page avec un id concret, récupérer le texte purifié, sans le balisage (avec .get_text()), et en général, profiter de plusieurs fonctionnalités présents dans html5lib, lxml, etc.

Indexation avec Whoosh.

nd="../indexdir"
os.mkdir(nd)     # Il faut importer os.path .

schema = Schema(title=TEXT(stored=True), 
                path=ID(stored=True), 
                content=TEXT(vector=True))
ix = create_in(nd, schema)

Le paramètre stored=True signifie que le paramètre – qui ne fait forcément pas partie de l'index, on ne peut pas le chercher – est stocké dans la base, et quand on trouve le document, on peut récupérer sa valeur.

Le champ vector (et aussi : format) spécifient quel type d'information est stocké sur le disque et comment. vector concerne le "forward index", utile pour savoir - pour un document - les positions (numéros des mots) et les fréquences des termes indexés. Les formats prédéfinis sont : Existence - oui ou nom pour un terme, sans autre précision ; Stored - le terme n'est pas indexé, seulement stocké et peut faire partie des résultats ; Frequency - l'index mémorise le nombre d'occurrences ; Positions - l'index mémorise les positions séquentielles des mots. Ceci ne facilite pas directement la recherche de la position du terme dans le document, comme dans notre petit exemple d'indexation du livre de Verne, (sauf que nous avons mémorisé les lignes), mais on y reviendra.

La classe TEXT du champ utilise par defaut Frequency, si on n'a pas besoin des contextes des termes, et la paramétrisation inclut phrase=False, ou Positions, si phrase=True (ceci tient par défaut).

Concernant les "vecteurs" et l'index direct, un exemple semble approprié. Si l'index inversé contient l'info suivante, avec les documents numérotés:

apple 	[(doc=1, freq=2), (doc=2, freq=5), (doc=3, freq=1)]
bear 	[(doc=2, freq=7)]

DOC      POSTINGS
1 	  [(text=apple, freq=2)]
2 	  [(text=apple, freq=5), (text='bear', freq=7)]
3 	  [(text=apple, freq=1)]

Quand le schéma est défini, on peut commencer le travail d'indexation. Voici comment ajouter deux documents à l'index.

writer = ix.writer()
def op(nf):r=open(nf,'r',encoding='utf-8'); return r
f1="../Master.html"
f2="../tp0410.html"
fo1=op(f1); fo2=op(f2)

writer.add_document(title="Master", path=f1,
                    content=fo1.read())
writer.add_document(title="Second document", path=f2,
                    content=fo2.read())
writer.commit()  #(ou .cancel() si on abandonne)

Recherche avec Whoosh

from whoosh.index import *  # (surtout open_dir)
nd="../indexdir"
ix = open_dir(nd)

sch=ix.searcher()

from whoosh.query import *
qry = And([Term("content", "python"), Term("content", "href")])

from whoosh.query import *
from whoosh.qparser import QueryParser

qstring="Python OR href"
parser = QueryParser("content", ix.schema)
qry = parser.parse(qstring)

res = sch.search(qry,terms=True)
# et, par exemple, pour voir si on a trouvé quelque chose :
print(len(res))

Voulez-vous savoir ce que vous avez indexé?

r=[str(x,'utf-8') for x in sch.lexicon("content")]

(Exercice supplémentaire. Où ai-je, diable, utilisé le mot 'zemljimlnbvazer'?? Je vous assure que ceci n'est ni polonais, ni portugais...)

Exercice supplémentaire sérieux. . Qu'est-ce que cette séquence indexée : '\u043b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d'? C'est une question sérieuse, et je demande une réponse concrète.

Concernant les résultats :

>>> res
<Top 2 Results for Or([Term('content', 'python'), Term('content', 'href')]) 
   runtime=0.0014853843156043575>
>>> res[0]
<Hit {'path': '../Master.html', 'title': 'Master'}>
>>> res[1]
<Hit {'path': '../tp0410.html', 'title': 'Second document'}>

try:
  sch=ix.searcher()
  ...
finally: sch.close()

with ix.searcher() as sch:
   ...

Analyse des résultats

Puisque dans une recherche simple et restreinte on sait ce que l'on cherche, le résultat ne contient pas forcément le terme trouvé, sauf si .search(...) contient terms=True, comme ici. La réponse aura alors .matched_terms(), qui donne [('content', b'python'), ('content', b'href')].

Nous allons à présent trouver la fréquence des termes. Cette information est stockée lors de l'indexation, donc on la trouve sans analyser les résultats de la recherche. L'expression sch.frequency("content","href") donne 24, c'est le nombre d'occurrences dans tous les documents. Afin de trouver la fréquence dans un document, il faut parcourir l'"index direct". C'est un peu lent, car la structure est séquentielle, mais la programmation est commode, car nous pouvons facilement transformer in itérateur en dictionnaire.

v=sch.vector_as("frequency",0,"content") # Master.
d=dict(v)

Comment trouver les lignes contenant les termes

La proposition est la suivante. Revenez à l'indexation. Pour chaque fichier qui devra être indexé, au lieu d'indexer par "content" le contenu du fichier, obtenu par .read(), vous allez lire le fichier ligne par ligne par readline() ou readlines(), et traiter chaque ligne comme un document séparé ! Il faudra stocker l'information qui identifie ce "document" : son chemin (le nom du document entier), le nom (classe ID construite à partir du numéro de la ligne), et aussi la position du début de la ligne dans le document, obtenue par la fonction système tell(). (Lisez le programme ndex0.py).

Vous aurez ainsi probablement une "base" avec des dizaines de milliers de "documents" très courts indexés. Quand un searcher trouve ces documents, vous récupérez le champ contenant le chemin d'accès, et vous le placez dans un dictionnaire, apparié avec les "noms" des documents indexés, c'est à dire, les numéros des lignes. Après la fin de la recherche vous procédez comme dans le programme ndex0 : vous ovrez le grand document, et avec seek() vous positionnez le ficher sur la ligne trouvée, ce qui permettra d'afficher les termes trouvés.

Ceci conclut le projet.

Quelques utilitaires [Lecture optionnelle, hors projet]

• Comment ouvrir une page web dans le navigateur, depuis un programme Python?
  L'accès Web est actuellement prévu dans tous les systèmes d'exploitation. Voici une possibilité.

  import webbrowser
  hndl=webbrowser.get()   # ou, disons, .get('Firefox.exe')
  hndl.open(chemin_d'accès) #  par ex. .open('../local_file.html')
  

  ou avec .open('http:// ...').

  Une autre possibilité est de lancer un sub-processus avec un exécutable :

  import subprocess as su
  su.call(['Firefox.exe','https://karczmarczuk.users.greyc.fr/TEACH/TAL'])
  

• Comment faire un serveur Web (http) en Python?
  Ceci est facile, les outils sont là, même très nombreux. Afin de faire un serveur minimaliste, qui renvoie au client les pages statiques (ne réagit pas aux formulaires HTML, aux requêtes POST), il vou suffit 10 secondes et une ligne de code. Lancez dans un terminal (shell système ; de préférence un autre terminal que celui où vous travaillez, car l'action est bloquante) :

  python -m http.server 9900
  

  (si "python" lance Python 3). Le nombre 9900 est ici le numéro du port, vous pouvez choisir un autre. Ceci charge le module en question et l'exécute. Le programme python lance une boucle sans fin, le serveur attend les requêtes. Dirigez votre navigateur vers : http://localhost:9900 et vous aurez le répertoire courant, là où le serveur a été lancé.

  Testez le serveur, cliquez sur les différents liens, et observez sur le terminal le rapport de l'activité du serveur. Il affiche ce qu'il fait. Pour qu'il puisse montrer une certaine intelligence, il faut surcharger les méthodes des "handlers" qui récupèrent les requêtes envoyées par le navigateur. Ce test utilise le handler : SimpleHTTPRequestHandler qui sert les fichiers statiques et les répertoires. C'est une sous-classe primitive de BaseHTTPRequestHandler qui ne fait même pas ça, et déclare une erreur (GET n'est pas pris en charge, et GET est le protocole de la requête envoyée quand vous demandez un fichier par un simple URL).

  Le lancement manuel de ce serveur peut se faire de manière suivante :

  import http.server as hs
  import socketserver as so
  
  def run():
      PORT = 9700
      Handler = hs.SimpleHTTPRequestHandler
      httpd = so.TCPServer(("",PORT), Handler)
      print("a l'ecoute sur le port :", PORT)
      httpd.serve_forever()
  
  run()
  

  Toutes les classes et méthodes sont écrites en Python, et disponibles en sources dans la Lib standard. C'est ici qu'il faut chercher les détails, par exemple comment arrêter le serveur (ceci nécessite un thread parallèle, où on lance httpd.shutdown()...), comment ajouter des fonctionnalités supplémentaires, lancer des applications de support, etc. Vous trouvez d'autres exemples (simples et lisibles) ici, avec des dizaines de références sur des solutions existantes.

  Bien sûr, il existent aussi des outils permettant de construire un client graphique, visuel du Web.

Retour à l'index