Le web regorge de pages sur tous les sujets, des contributions multiples et variées qui changent souvent. Leur point commun : elles sont écrites en langage HTML et possèdent des liens les reliant les unes aux autres.
Comment trouver l’information pertinente sur des millions de serveurs ?
Un moteur de recherche (Search Engine) est un outil qui parcourt le web et indexe automatiquement le contenu qu’il visite. Il permet d’accéder à différentes ressources comme des textes, des vidéos, des images, de la musique…
Il fonctionne suivant trois opérations essentielles :
- l’exploration (Crawling) : le moteur de recherche envoie ses robots d’indexation (spider, crawler, bot) de lien en lien pour rechercher toutes les données des pages à archiver (mots clés, métadonnées) ;
- l’indexation (Indexing) : le moteur de recherche indexe tous les mots dans une base de données suivant des critères de poids ou notoriété ;
- la recherche (Ranking) : le moteur de recherche doit trier et identifier les pages à partir des mots utilisés dans la requête ainsi que ses tables d’index.
20 milliards de sites sont visités (crawlés) par Google, chaque jour.
Avant de commencer
Prérequis : maîtriser les bases de la programmation Python (variables, boucles, entrées/sorties, fonctions)
Contexte de la mise en œuvre de l'activité : en classe, en présence de l'enseignant
Présentation
Cette activité propose de vous faire découvrir comment un moteur de recherche indexe les différentes pages web qu'il a en mémoire.
Un moteur de recherche doit charger périodiquement toutes les pages web qu’il désire indexer. Il dispose de plusieurs robots qui chargent les pages web en parallèle. Ils se répartissent les adresses URL de façon équitable pour qu’une même URL ne soit pas chargée deux fois : on pourrait imaginer qu’un robot charge toutes les URL débutant par « A », un autre, celles débutant par « B », et ainsi de suite.
En pratique, on définit plutôt une fonction de hachage qui convertit l’URL en un nombre.
Soit la liste de vingt cinq mots :
00 vie(s), 01 saison(s), 02 continent(s), 03 femme(s), 04 homme(s), 05 enfant(s), 06 monde(s), 07 chat(s), 08 voiture(s), 09 couleur(s), 10 quatre, 11 cinq, 12 rouge(s), 13 bleu(es), 14 meilleur(es), 15 belle(s), 16 perdu(es), 17 est, 18 sont, 19 dans, 20 ont, 21 garage(s), 22 fou(s), 23 folle(s), 24 doué(es).
1. Écrire une phrase qui représente le titre d'une page web, avec 3 ou 4 mots clés choisis dans la liste. Les articles LE, LA, L’, LES, UN, UNE, DE, D’, DES etc. et les adjectifs possessifs MON, SA, SES, SON etc. ne sont pas comptés.
Le moteur de recherche peut maintenant indexer l’ensemble de la phrase en commençant par la page, le mot puis sa position dans la phrase.
Exemple pour une page 3 : « Le chat perdu et l'enfant » ce qui donne : 3070, 3161, 3052 (3 P3 - mot 05 - position 2).
Préparation
Pour convertir une chaîne de caractères en une liste en utilisant l'espace comme séparateur, on peut utiliser la méthode split :
chaine = "toto le héro"
chaine.split(" ") renvoie ['toto', 'le', 'héro']
Pour connaître l'index d'un élément dans une liste on utilise la méthode index.
ma_liste = [1, "a", "toto"]
ma_liste.index("a") renvoie 1
On peut ajouter un élément avec :
a = 3
ma_liste += [f"{a}"] renvoie [1, "a", "toto", '3'] # entier convertit en caractère
et si l'on veut que cet élément (un entier) soit affiché sur deux chiffres,
ma_liste += [f"{a:02}"] renvoie [1, "a", "toto", '03']
On peut réduire la liste en enlevant le premier et le dernier élément de la liste avec :
ma_liste[1, -1] renvoie ["a", "toto"]
On peut parcourir toute la liste et donner l'index de chaque élément sur deux chiffres :
for i in ma_liste:
print(i, "a pour indice ", f"{ma_liste.index(i):02}") renvoie 1 a pour indice 00
a a pour indice 01
toto a pour indice 02
3 a pour indice 03
Traitement des données avec Python
On souhaite réaliser une fonction explore qui traduit les titres de plusieurs pages (p1, p2, p3...) en codes, comme vu dans la présentation.
P3 = "Le chat perdu et l'enfant" --> 3070 3161 3052
2. Copiez et complétez le programme suivant :
liste_mots = ["vie", "saison", "continent", "femme", "homme", "enfant",
"monde", "chat", "voiture", "couleur", "quatre", "cinq",
"rouge", "bleu", "meilleur", "belle", "perdu", "est",
"sont", "dans", "ont", "garage", "fou", "folle", "doué"]
def trouve_mot(mot):
"""renvoie l'index du mot si le mot est dans la liste"""
for m in liste_mots:
if m in mot:
return .....................................
return None
def explore(p, phrase):
"""convertit la phrase de la page p en codes"""
code = ""
mots = .................................................# convertir la phrase en une liste de mots
i = 0
for mot in mots:
id_mot = trouve_mot(mot)
if id_mot ...........................:
code += f"{p}{id_mot:02}{i} "
i .......................
return code
phrases = ["La vie est belle",
"Les quatre saisons",
"La couleur rouge de la vie",
"Le chat perdu et l'enfant",
"Le garage à voitures"]
liste_codes = []
for i, phrase in enumerate(phrases):
code = explore(i, phrase)
print(f"'{phrase}' a pour code : {code}")
liste_codes += code.strip().split(" ") # stocker les codes dans une liste
Le moteur de recherche doit indiquer les pages contenant des mots clés. L'internaute peut, par exemple, demander les pages contenant le mot clé "vie".
3. Complétez le code suivant
def recherche(mot):
id_mot = ........................................
reponse = ""
for m in .........................:
if f"{id_mot:02}" in m[1:-1]:
reponse += f"p{m[0]} "
return ...................
# recherche internet du mot "vie" sur l'ensemble des phrases stockées sous forme de code
mot = "vie"
reponse = .....................................
print(f"le mot '{mot}' est dans {reponse}")