Autour de moteurs de recherche.

Cette section est consacrée aux mécanismes de recherche textuelle : comment préparer (structurer, stocker) l'information facilitant la recherche (localement, dans un fichier, et globalement, dans le réseau mondial), comment algorithmiser la recherche efficace et facile à formuler, etc. Cette problématique seule remplirait un cours annuel.

Afin d'implémenter un mécanisme de recherche sur le Web, on a besoin de plusieurs ingrédients ; superficiellement on doit mentionner au moins le suivant :

Finalement, il est essentiel qu'un moteur de recherche soit équipé des dispositifs de recherche inexacte, avec le spectre de "similitudes" assez large. Il ne s'agit pas seulement de mots similaires, mais aussi de concepts similaires, synonymes/hyponymes, etc. Nous entrons ainsi dans le domaine du Web sémantique.

Comment le faire...

L'idée de base du crawler est en principe très simple. On parcourt le document-racine, et on répertorie les liens, genre
<a href="http://unSite.utile/ici/docum.html">

On a donc besoin d'un parseur HTML, permettant d'identifier les liens les comparer, et suivre. On peut le faire à la main, assez facilement aves les expressions régulières ou autres dispositifs grammaticaux. La librairie standard urllib nous aidera à récupérer les contenus des URLs.

Cependant plusieurs parseurs/crawlers ont déjà été codés, c'est une manipulation fréquente ! L'année dernière en TAL nous avons utilisé Beautiful Soup. (Voir aussi la doc. Il y a aussi une traduction française, mais je vous conseille de lire l'original.).

Un parseur HTML doit reconnaître les balises avec leurs attributs, et transformer une chaîne en une hiérarchie d'objets.. Si on lance : 

from bs4 import BeautifulSoup as BS
f=open("Master.html","r",encoding="utf-8")
soup=BS(f)
on obtient un objet, qui peut être analysé. La demande ht=soup.find_all('hr') donne 
 
[<hr class="ha0"/>,
 <hr class="ha1"/>,
 <hr color="#ff7000" size="6" width="75%"/>,
 <hr color="#00ff00" size="6" width="75%"/>,
 <hr class="ha0"/>,
 <hr class="ha0"/>]
ce qui est un objet ResultSet (presque une liste, mais c'est plus riche).

On peut ensuite vérifier ht[2].attrs, et obtenir {'size': '6', 'color': '#ff7000', 'width': '75%'}. C'est une vraie "soupe" structurée, ou .attrs permet de vérifier les attributs d'un objet interne, .contents : la liste des descendants, etc. Le paquetage facilite une analyse complète du document, le re-formatage, conversions, etc., les éléments sont modifiables : ht[4]['class']="ha1" modifie l'apparence d'une de mes barres de séparation (après avoir recomposé et remplacé le document d'origine). La liste
lnks=[lnk.get('href') for lnk in soup.find_all('a')] contient 

['https://dias.users.greyc.fr/?op=paginas/tal.html',
 'https://store.continuum.io/cshop/anaconda/',
 'http://nltk.org/',
 ...
 'tp2010.html',
 'tp0511.html',
 "javascript:lgo('TalPresa.html','Ltal')",
 "javascript:lgo('Intro0.html','Ltal')",
 ...]
Ce sont les chaînes avec les adresses des pages liées. On peut alors exécuter 
import urllib.request as urlr
fh = urlr.urlopen(lnks[2]); sh=fh.read().decode('utf-8')
et dans fh vous avez le contenu de la page secondaire, le contenu de la documentation du NLTK. Le décodage est indispensable, car par défaut l'accès en lecture à une adress URL retourne non pas une chaîne, mais bytes, un tableau d'octets (car a priori on ne connait pas le protocole de codage sur le serveur). C'est tout concernant les propriétés universelles du crawling. Les détails, comme les filtrages, mémorisations, descente récursive à une profondeur donnée - tout ceci dépend des circonstances.

Sur cette page vous trouverez un crawler complet, qui utilise Beautiful Soup, mais c'est une version ancienne, sous Python 2 (et BS 3 ; la version actuelle 4 n'est pas entièrement compatible). Quelqu'un veut mettre à jour ce paquetage? NIST vous sera reconnaissant...

Le parcours récursif local, par la hiérarchie des répertoires (sans chercher les liens dans les fichiers) est une tâche pour le module os. 

import os
q=os.walk( ... chemin ...) # par ex walk('../samples') etc.
Ceci construit un itérateur de tous les fichiers et des sous-répertoires. Ceci n'est pas un crawling documentaire, on ne suit pas le liens dans les documents, mais c'est important pour la constitution d'une base documentaire.

Indexation

Trouver les mots dans un document, est une manipulation déjà discutée. Ici le but est très différent, on l'appelle parfois la construction de l'index inverse. On doit, pour un ensemble de mots, trouver les documents auxquels ces mots appartiennent. La recherche d'un terme, par ex. "bombe atomique" avec Google, déclenche la procédure de récupération des descriptifs des documents qui contiennent ce terme, et où il est pertinent. Si la recherche donne comme résultat cette page de mon cours, le moteur est visiblement stupide.

Les détails de l'indexation intelligente sont très nombreux et compliqués, et les stratégies doivent être formalisables et implémentables. Un formalisme populaire de la pondération des mots est TF-IDF (Term Frequency-Inverse Document Frequency) – l'évaluation de l'importance d'un terme dans un document, relative à un corpus.

Le poids du terme augmente avec sa fréquence dans le texte, bien sûr, après avoir neutralisé les "stop-words" : "le", "un", "the, etc., dans plusieurs langues. Ce poids dépend aussi de la fréquence du terme dans le corpus ; ici les mots peu fréquents deviennent pertinents. La formule de pertinence utilisée parfois (des modifications existent) est basé sur le suivant. La fréquence inverse de document est

\(\displaystyle{\mathrm{idf}_i = \log \frac{|D|}{|\{d_j: t_i \in d_j\}|}}\,.\)

Ici \(|D|\) est le nombre de documents dans le corpus. Le dénominateur est le nombre de documents où le terme \(t_i\) apparaît (c'est-à-dire \(n_{i,j} \neq 0\)). La formule pour \(\mathrm{tf}_{ij}\) (term frequency) est le nombre d'occurrences de ce terme dans le document considéré. Le résultat final est le produit des deux.
On pourra ainsi considérer quelques documents comme plus pertinents que les autres, et ils seront placés à la tête de la liste retournée par le moteur. Cette stratégie neutralise les mots communs, mais normalement ils sont éliminés par force avant, ainsi il a moins de comparaisons, moins de mots à indexer. La stratégie tf-idf e été généralisée plusieurs fois ; on utilise souvent une formule plus complexe, connue sous le nom de BM25 Okapi. Son explication demande une solide connaissance de la théorie de probabilité, on essaie d'évaluer la "quantité d'information" (liée à l'entropie relative des termes dans des documents, etc.)

Pertinence relative des documents

Si un document est cité (référencé) par plusieurs autres, alors il constitue – justement – une référence, et même si un terme n'est pas très fréquent dedans, d'autres documents peuvent promouvoir celui-là. (Dans le papier original d'Einstein sur l'électrodynamique des corps en mouvement, on ne trouvera pas beaucoup d'occurrences du terme "théorie de relativité"...).

Ceci est un facteur important, donc il est abusé : plusieurs vautours augmentent la popularité d'un site X en créant des documents-bidon qui possèdent X comme référence.
Dans le jargon du domaine il existe un nom pour ce phénomène : "spamdexing". Hélas cette sorte d'activité prolifère. Plusieurs pages contiennent des termes totalement étranges au vrai but, uniquement pour être vues. Le résultat? Une page qui dit : "non, nous n'avons pas de bombe atomique en stock, mais nous proposons l'abonnement à un site érotique d'excellente qualité et pas cher..."

Similitude entre les documents

Puisque l'Internet est en permanence cloné, les documents sont copiés et re-copiés des milliers de fois, les moteurs de recherche globaux risquent de retourner au client plusieurs liens équivalents ou presque, ce qui n'apporte rien de plus qu'un d'eux. Il faut donc souvent catégoriser les documents, et trouver une mesure de similitude entre les textes.

Dans le modèle vectoriel des documents (Gerald Slaton, années '70, exploité avant, dans SMART), un texte est representé dans un espace N-dimensionnel comme un vecteur, où les "axes" sont spécifiés par le vocabulaire des termes d'indexation. Pour chaque terme, son poids (tf-idf ou autre) dans le document détermine la position du document selon cet axe.

Donc, un document est un vecteur : \(d_j = (w_{1,j}, w_{2,j}, \ldots , w_{t,j})\), une requête composite également: \(q=(w_{1,q}, w_{2,q},\ldots , w_{n,q})\).
Si on est capable de donner des valeurs numériques aux poids selon les "axes", on peut calculer les normes : \(||q||^2 = \sum{q_i^2}\), et la similitude comme le cosinus de l'angle entre deux vecteurs :

\(\displaystyle{\mathrm{sim}(w,d) = \cos \theta = \frac{w \cdot d}{||w|| \,\, ||d||}}\,.\)

Deux documents qui ne partagent des termes utiles sont orthogonaux, leur similitude est zéro. Si elle est proche de 1, statistiquement les documents sont textuellement similaires.

La discussion de la théorie peut encore continuer longtemps... Nous nous arrêtons ici, le sujet sera repris en TP. Comment indexer pratiquement une collection de documents?

Manuellement ceci demande la création d'une base de données (ou d'un dictionnaire), où on répertorie les documents où le terme a été localisé. Les détails, comme la pertinence, doivent être spécifiés à côté. Normalement l'indexation se déroule simultanément avec le crawling, et les détails à sauvegarder (est-ce que le lien du document est suffisant, ou nous voulons aussi le numéro de ligne avec le terme?... etc.) dépendent du moteur, et des requêtes. Plusieurs indexeurs ont été codés.

Whoosh

L'année dernière nous avons exploité le paquetage Whoosh qui est un indexeur, un dispositif de recherche (pas un super-moteur mondial, seulement une machine utilisable pour des simples tâches), et un spell-checker (vérification inexacte).

Whoosh de Matt Chaput est un programme en Python pur, facile à utiliser. Probablement votre dernier devoir obligatoire sera basé sur son usage.

Whoosh utilise Okapi BM25F comme la fonction de pertinence, mais il est très paramétrable. Whoosh n'est pas un crawler, pour indexer une collection de documents (ceci peut se faire en plusieurs étapes), l'utilisateur devra construire cette collection (locale ou distante, via URLs).

La première chose à faire est la création d'un dossier dédié pour l'index, et la création d'un schéma de l'index : l'ensemble de champs, où on stocke l'information requise, par ex. le titre, et le chemin d'accès à un document associé à un terme. 

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)

Ce schéma a trois champs : deux textes, et un ID qui peut être textuel, mais qui est considéré comme une unité indivisible et unique. Quand vous chercherez un terme, la réponse vous donnera cet ID, ainsi que le titre du document (qui peut être récupéré de la page Web, ou ajouté à la main, etc.) Vous pourrez ajouter à ce schéma d'autres champs, comme la date de la création.

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, 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)]
alors le vecteur des termes, ou l'index direct contiendra 
DOC      POSTINGS
1 	  [(text=apple, freq=2)]
2 	  [(text=apple, freq=5), (text='bear', freq=7)]
3 	  [(text=apple, freq=1)]
D'autres choses, comme les champs dynamiques, et la modification des schémas dans une base existante, ne seront pas discutés ici.

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)
Et c'est tout pour commencer. L'index est là, avec le contenu indexé, et un peu d'info supplémentaire. S'il faut répéter cette expérience, il faut nettoyer l'index, ou - ce qui est plus simple - détruire tout d'abord. Plus d'information : dans la doc, par ex. sur le sujet de la mise à jour de l'index si les documents changent.

Recherche avec Whoosh

Vous ouvrez un index existant, et vous spécifiez son "robot de recherche" : 
from whoosh.index import *  # (surtout open_dir)
nd="../indexdir"
ix = open_dir(nd)

sch=ix.searcher()
La phase essentielle est la création de la requête. Ceci peut être un terme (mot) ou une composition booléenne, par exemple 
from whoosh.query import *
qry = And([Term("content", "python"), 
           Term("content", "href")])
Ce qui précise les termes cherchés, dans quels champs, et comment combinés. Les opérations Or et Not sont également possibles. Mais ceci n'est pas commode (surtout si la recherche se fait à travers une interface dehors du programme Python). Alors il y a des utilitaires, comme le parseur de requêtes en forme textuelle : 
from whoosh.query import *
from whoosh.qparser import QueryParser

qstring="Python OR href"
parser = QueryParser("content", ix.schema)
qry = parser.parse(qstring)
Ensuite il suffit de lancer la recherche : 
res = sch.search(qry,terms=True)
# et, par exemple, pour voir si on a trouvé quelque chose :
print(len(res))
Les objets sch et res contiennent plusieurs éléments utiles dans l'analyse. Par ex. list(sch.documents) donne [{'path': '../Master.html', 'title': 'Master'}, {'path': '../tp0410.html', 'title': 'Second document'}].

Voulez-vous savoir ce que vous avez indexé? 

r=[str(x,'utf-8') for x in sch.lexicon("content")]
La valeur de r vaut :
['000', '003020', ... 'abcef', 'abréviation', 'abréviations', 'absolument', 'accord', 'accès', 'adaptée', ... 'défaillances', 'définie', 'définissable', 'définition', 'définitions', 'déjà', 'dépassent', 'détails', 'dûment', 'edward', 'efface', 'effacer', 'efficace', ... 'xmlns', 'xy', 'yel', 'yes', 'yx', 'z.br', 'zemljimlnbvazer', 'zip', 'ça', 'échelle', ... '\u0438\u043e\u0441\u0438\u0444\u043e\u0432\u0438\u0447', '\u043b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d']

Exercice. Où ai-je utilisé le mot 'zemljimlnbvazer'?? Ceci n'est pas polonais...)

Exercice sérieux. . Qu'est-ce que cette séquence indexée : '\u043b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d'?

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'}>
Afin d'éviter la présence des flots de données ouverts, il est recommandé de fermer le searcher après son travail : 
try:
  sch=ix.searcher()
  ...
finally: sch.close()
ou : 
with ix.searcher() as sch:
   ...
Le reste du processus passe par l'analyse des propriétés de l'objet résultat. Nous n'allons pas discuter la paramétrisation de la recherche plus élaborée, ou personnalisée, mais ce n'est pas difficile.

Analyse des résultats

Un objet de type Results se comporte comme une liste de résultats (et on peut limiter sa longueur avec limits=N). Puisque title et path ont été stockés, le "Hit" les répertorie. Cet objet se comporte comme un dictionnaire, avec les méthodes keys et values. Et res[0].items() donne [('title', 'Master'), ('path', '../Master.html')].

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)
Alors d["href"] retourne 15. Si au lieu de "frequency" nous utilisons "positions", ce terme fournira la liste [48, 81, 95, 406, 852, 858, 1763, 1826, 3651] (ce qui n'est pas très utile).

Comment trouver les lignes contenant les termes

Ceci peut être assez compliqué, et les techniques variées sont utilisées. Les objets de classe "Matcher" dans Whoosh stockent l'information qui peut être utile, mais l'apprentissage de ces modules très mal documentés, vous prendra une semaine !

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.