Tu utilises Google, Qwant ou DuckDuckGo tous les jours. Mais est-ce que tu t'es déjà demandé comment ces moteurs de recherche font pour trouver la bonne page en une fraction de seconde parmi des milliards ? En NSI, tu peux coder toi-même les algorithmes qui font tourner ces géants. Pas besoin d'être un génie : avec Python et quelques idées clés, tu vas comprendre et implémenter un mini moteur de recherche. Accroche-toi, on part explorer les entrailles du web !
Comment fonctionne un moteur de recherche ?
Un moteur de recherche, c'est un programme qui répond à trois grandes questions :
- Quelles pages existent ? → C'est le rôle du crawler (robot d'indexation) qui parcourt le web en suivant les liens.
- Que contient chaque page ? → On construit un index, souvent un index inversé qui associe chaque mot à la liste des pages où il apparaît.
- Quelle page est la plus pertinente ? → On classe les résultats avec un score. C'est là qu'intervient le célèbre PageRank de Google, mais aussi la similarité entre la requête et le contenu.
En NSI, on simplifie le web à un petit ensemble de pages et on code ces étapes. Tu vas voir, c'est très formateur et ça combine plusieurs notions du programme : dictionnaires, graphes, matrices, algorithmes gloutons.
L'index inversé : la base de tout
Imagine que tu as 3 pages :
- Page A : "Python est un langage de programmation"
- Page B : "Le langage Python est utilisé en NSI"
- Page C : "NSI signifie Numérique et Sciences Informatiques"
Un index inversé associe chaque mot (normalisé en minuscules, sans ponctuation) à la liste des pages qui le contiennent. En Python, on utilise un dictionnaire :
pages = {
'A': "Python est un langage de programmation",
'B': "Le langage Python est utilisé en NSI",
'C': "NSI signifie Numérique et Sciences Informatiques"
}
index = {}
for page, texte in pages.items():
mots = texte.lower().split()
for mot in mots:
if mot not in index:
index[mot] = []
if page not in index[mot]:
index[mot].append(page)
print(index['python']) # ['A', 'B']
print(index['nsi']) # ['B', 'C']
Ce dictionnaire permet de retrouver très vite les pages contenant un mot. C'est exactement ce que fait un moteur de recherche quand tu tapes une requête.
Le PageRank : mesurer l'importance d'une page
L'idée de PageRank est simple : une page est importante si d'autres pages importantes pointent vers elle. C'est un algorithme itératif qui attribue un score à chaque page en fonction des liens entrants.
Le principe mathématique
On modélise le web comme un graphe orienté : les pages sont des nœuds, les liens sont des arcs. On note PR(A) le score de la page A. La formule simplifiée est :
PR(A) = (1-d) + d * (PR(B)/L(B) + PR(C)/L(C) + ...)
où d est le facteur d'amortissement (souvent 0.85), et L(B) le nombre de liens sortants de B. On répète le calcul jusqu'à ce que les scores se stabilisent.
Implémentation en Python
Prenons un mini-web de 3 pages : A pointe vers B et C, B pointe vers C, C pointe vers A.
def pagerank(graphe, d=0.85, iterations=100):
N = len(graphe)
PR = {page: 1/N for page in graphe}
for _ in range(iterations):
nouveau_PR = {}
for page in graphe:
somme = 0
for autre in graphe:
if page in graphe[autre]:
somme += PR[autre] / len(graphe[autre])
nouveau_PR[page] = (1 - d) / N + d * somme
PR = nouveau_PR
return PR
# Graphe : A -> [B, C], B -> [C], C -> [A]
graphe = {
'A': ['B', 'C'],
'B': ['C'],
'C': ['A']
}
scores = pagerank(graphe)
for page, score in scores.items():
print(f"Page {page} : {score:.4f}")
Après convergence, tu verras que la page C a souvent le meilleur score car elle reçoit des liens de A et B, et A est aussi bien classée. Amuse-toi à modifier le graphe pour voir l'influence des liens.
Classer les résultats : similarité et TF-IDF
Le PageRank ne suffit pas : il faut aussi que la page parle de ce que tu cherches. On calcule alors un score de pertinence entre la requête et chaque page. Deux méthodes classiques :
La similarité cosinus
On représente chaque document et la requête par un vecteur de mots. La similarité cosinus mesure l'angle entre ces vecteurs : plus ils pointent dans la même direction, plus le document est pertinent.
import math
def similarite_cosinus(vect1, vect2):
# vect1 et vect2 sont des dictionnaires mot -> poids
produit = sum(vect1.get(mot, 0) * vect2.get(mot, 0) for mot in set(vect1) | set(vect2))
norme1 = math.sqrt(sum(v**2 for v in vect1.values()))
norme2 = math.sqrt(sum(v**2 for v in vect2.values()))
if norme1 == 0 or norme2 == 0:
return 0
return produit / (norme1 * norme2)
Pour obtenir les vecteurs, on peut utiliser les fréquences de mots (TF) ou la pondération TF-IDF qui donne plus de poids aux mots rares.
TF-IDF en bref
TF (Term Frequency) = nombre d'occurrences du mot dans le document divisé par le nombre total de mots.
IDF (Inverse Document Frequency) = log(N / nombre de documents contenant le mot).
Le produit TF * IDF donne un poids élevé aux mots fréquents dans un document mais rares ailleurs. C'est très efficace pour discriminer les pages.
Mise en pratique : un mini moteur de recherche complet
Assemblons tout : un crawler simplifié (liste de pages), un index inversé, un calcul de TF-IDF, et un classement par similarité cosinus. Voici un exemple complet que tu peux tester :
import math
# 1. Corpus de pages
pages = {
'A': "Python est un langage de programmation",
'B': "Le langage Python est utilisé en NSI",
'C': "NSI signifie Numérique et Sciences Informatiques",
'D': "La programmation en Python est amusante"
}
# 2. Index inversé et TF-IDF
def construire_index(pages):
index = {}
for page, texte in pages.items():
mots = texte.lower().split()
for mot in mots:
index.setdefault(mot, []).append(page)
return index
def tf_idf(pages, index):
N = len(pages)
vecteurs = {}
for page, texte in pages.items():
mots = texte.lower().split()
vecteur = {}
for mot in set(mots):
tf = mots.count(mot) / len(mots)
idf = math.log(N / len(index[mot]))
vecteur[mot] = tf * idf
vecteurs[page] = vecteur
return vecteurs
# 3. Requête et similarité
def rechercher(requete, pages, vecteurs, index):
mots_req = requete.lower().split()
vecteur_req = {}
for mot in set(mots_req):
if mot in index:
tf = mots_req.count(mot) / len(mots_req)
idf = math.log(len(pages) / len(index[mot]))
vecteur_req[mot] = tf * idf
scores = {}
for page, vect in vecteurs.items():
scores[page] = similarite_cosinus(vecteur_req, vect)
return sorted(scores.items(), key=lambda x: x[1], reverse=True)
# Test
index = construire_index(pages)
vecteurs = tf_idf(pages, index)
resultats = rechercher("Python programmation", pages, vecteurs, index)
for page, score in resultats:
print(f"{page} : {score:.3f}")
Tu obtiendras les pages A et D en tête car elles contiennent les deux mots. Ce mini moteur illustre parfaitement les concepts clés. Pour aller plus loin, tu peux ajouter le PageRank comme facteur de tri secondaire.
Conseils pour réussir en NSI et au bac
Les algorithmes de moteur de recherche sont au programme de Terminale NSI, notamment dans le module sur les graphes et les algorithmes. Voici quelques astuces :
- Maîtrise les dictionnaires : c'est la structure de données reine pour l'indexation.
- Comprends la complexité : un bon algorithme doit être efficace. Par exemple, la recherche dans un index inversé est en O(1) en moyenne.
- Entraîne-toi sur des exercices : sur nsi-lycee.fr/exercices, tu trouveras des défis progressifs.
- Revois les bases de données : le lien avec SQL est intéressant pour stocker et interroger un index. Va voir le cours SQL.
- Utilise les ressources complémentaires : pour des fiches de révision, Allolycee propose des contenus utiles. Pour des exercices supplémentaires, Allobac est une bonne adresse.
N'hésite pas à coder tes propres variantes. Par exemple, ajoute la gestion des liens entre pages pour combiner PageRank et similarité. C'est exactement ce que font les vrais moteurs !
Conclusion
Tu as maintenant les clés pour comprendre et coder les algorithmes d'un moteur de recherche en Python. De l'index inversé au PageRank, en passant par la similarité cosinus, ces notions sont non seulement au programme de NSI mais aussi au cœur des technologies que tu utilises quotidiennement. Alors lance-toi : code un petit moteur, teste-le, améliore-le. Et si tu veux approfondir, explore les cours NSI pour d'autres pépites. Bon code !
