Tu tapes une requête sur ton moteur de recherche préféré et, en une fraction de seconde, des millions de résultats pertinents s'affichent. Magique ? Non, algorithmique ! Derrière cette apparente simplicité se cachent des algorithmes fascinants, étudiés en NSI et tombables au bac. Dans cet article, on décortique ensemble le fonctionnement d'un moteur de recherche : du robot qui explore le web jusqu'au célèbre PageRank, en passant par l'indexation et le classement. Prêt à comprendre ce qui se passe sous le capot ? C'est parti !
Comment fonctionne un moteur de recherche ?
Un moteur de recherche, c'est un peu comme une immense bibliothèque numérique. Pour qu'il puisse répondre à tes questions, il doit d'abord connaître le contenu du web. Trois grandes étapes se succèdent :
- Le crawling (exploration) : des robots appelés crawlers ou spiders parcourent le web en suivant les liens de page en page. Ils téléchargent le contenu HTML et le ramènent au moteur.
- L'indexation : le contenu collecté est analysé, découpé en mots-clés et stocké dans une structure de données géante appelée index. C'est comme l'index d'un livre : pour chaque mot, on sait quelles pages le contiennent.
- Le classement (ranking) : quand tu fais une requête, le moteur compare tes mots-clés à son index, récupère les pages correspondantes, puis les trie par pertinence selon des algorithmes comme PageRank.
En NSI, on s'intéresse surtout à cette dernière étape : comment un algorithme peut-il décider qu'une page est plus importante qu'une autre ? C'est là que la théorie des graphes entre en jeu.
Le web vu comme un graphe
Le web est modélisé comme un graphe orienté : chaque page est un sommet (ou nœud), et chaque lien hypertexte est une arête orientée allant d'une page vers une autre. Cette représentation abstraite permet d'appliquer des algorithmes puissants. Tu as déjà vu les graphes en NSI ? Sinon, un petit tour sur nos cours te sera utile !
Le PageRank : l'algorithme qui a fait la fortune de Google
Inventé par Larry Page et Sergey Brin à Stanford en 1998, PageRank attribue à chaque page web un score de 0 à 1 (la somme des scores vaut 1). L'idée de base est simple : une page est importante si d'autres pages importantes pointent vers elle.
Imagine que tu es un surfeur qui clique au hasard sur les liens. Avec une probabilité d (souvent 0,85), tu suis un lien sortant de la page actuelle. Avec une probabilité 1-d, tu recommences sur une page au hasard. La probabilité que tu te trouves sur une page donnée après un très grand nombre de clics, c'est son PageRank !
Formule mathématique
Pour une page A, le PageRank se calcule ainsi :
PR(A) = (1-d) / N + d * Σ ( PR(Ti) / C(Ti) )
Où :
- N est le nombre total de pages
- d est le facteur d'amortissement (généralement 0,85)
- Ti sont les pages qui pointent vers A
- C(Ti) est le nombre de liens sortants de TiEn clair : chaque page qui pointe vers A lui transmet une fraction de son propre score, proportionnelle au nombre de ses liens sortants. Plus une page reçoit de liens de qualité, plus son score augmente.
Calcul itératif : implémentation en Python
On calcule le PageRank par itérations successives jusqu'à convergence. Voici une implémentation simple et testable :
def pagerank(graphe, d=0.85, iterations=100):
"""
Calcule le PageRank de chaque page.
graphe : dict {page: [liste des pages pointées]}
Retourne un dict {page: score}
"""
N = len(graphe)
# Initialisation : chaque page a le même score 1/N
PR = {page: 1/N for page in graphe}
for _ in range(iterations):
nouveau_PR = {}
for page in graphe:
# Somme des contributions des pages qui pointent vers 'page'
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
# Exemple d'utilisation
graphe = {
'A': ['B', 'C'],
'B': ['C'],
'C': ['A'],
'D': ['C']
}
scores = pagerank(graphe)
for page, score in sorted(scores.items(), key=lambda x: -x[1]):
print(f"{page} : {score:.4f}")Dans cet exemple, la page C reçoit des liens de A, B et D : elle devrait avoir le meilleur score. N'hésite pas à tester ce code sur nos exercices pour t'entraîner !
Convergence et complexité
Le PageRank converge généralement en quelques dizaines d'itérations. L'algorithme a une complexité en O(k * (N + M)) où k est le nombre d'itérations, N le nombre de pages et M le nombre de liens. Pour le web entier (des milliards de pages), c'est un défi de calcul énorme, mais les moteurs modernes utilisent des variantes optimisées.
De la théorie à la pratique : comment un moteur classe les résultats
Le PageRank n'est qu'une partie de l'équation. Les moteurs modernes (Google, Bing) utilisent des centaines de signaux :
- Pertinence sémantique : la page contient-elle les mots de la requête ? Sous quelle forme ?
- Fraîcheur : la page est-elle récente ?
- Popularité : combien de liens pointent vers elle ? (PageRank)
- Expérience utilisateur : le site est-il rapide, mobile-friendly, sans publicité intrusive ?
- Localisation : résultats adaptés à ta région et à ta langue.
En NSI, tu dois surtout maîtriser les concepts algorithmiques : graphes, parcours (BFS/DFS), calcul itératif, complexité. Ces notions sont réutilisables bien au-delà des moteurs de recherche.
Un cas concret : l'indexation inversée
Pour retrouver rapidement les pages contenant un mot, on utilise un index inversé : un dictionnaire qui associe chaque mot à la liste des documents où il apparaît. Voici comment on pourrait le construire en Python :
def construire_index(documents):
"""
documents : liste de chaînes de caractères
Retourne un dict {mot: [indices des documents]}
"""
index = {}
for i, doc in enumerate(documents):
mots = doc.lower().split()
for mot in set(mots): # set pour éviter les doublons
if mot not in index:
index[mot] = []
index[mot].append(i)
return index
# Exemple
docs = [
"Le chat dort",
"Le chien aboie",
"Le chat et le chien jouent"
]
idx = construire_index(docs)
print(idx['chat']) # [0, 2]Cet index permet de répondre instantanément à une requête comme « chat » en retournant les documents 0 et 2, sans parcourir tous les textes. C'est le même principe que les moteurs de recherche, à très grande échelle.
Réviser le bac NSI : conseils de méthode
L'épreuve de NSI au bac comporte une partie écrite (3h30) et une partie pratique (1h). Les algorithmes des moteurs de recherche peuvent tomber sous forme de :
- Exercice de programmation : écrire une fonction qui calcule un PageRank simplifié ou construit un index.
- Question de cours : expliquer le principe du crawling, de l'indexation ou du PageRank.
- Analyse de complexité : donner l'ordre de grandeur d'un algorithme.
- Manipulation de graphes : représenter un réseau de pages et simuler un parcours.
Pour bien te préparer :
- Maîtrise les structures de données : dictionnaires, listes, ensembles. Ils sont partout dans les moteurs de recherche.
- Entraîne-toi à coder PageRank et l'index inversé sans regarder la correction.
- Révise les graphes : parcours en largeur (BFS), en profondeur (DFS), et leur implémentation en Python.
- Comprends la complexité algorithmique : O(n), O(n²), O(n log n).
- Utilise des ressources complémentaires comme Allolycée pour des fiches de révision, ou Allobac pour des annales corrigées.
Et si tu veux approfondir les bases de données, jette un œil à notre article sur SQL : les moteurs de recherche utilisent aussi des requêtes pour interroger leurs index !
Conclusion
Les moteurs de recherche sont un formidable terrain d'application pour l'informatique : graphes, algorithmes probabilistes, structures de données, complexité… Tout ce que tu apprends en NSI prend vie dans ces outils que tu utilises tous les jours. Le PageRank n'est qu'un exemple, mais il montre comment une idée mathématique simple peut révolutionner l'accès à l'information.
Alors, prêt à coder ton propre mini-moteur de recherche ? Commence par les exercices, n'aie pas peur de te tromper, et surtout : amuse-toi ! La NSI, c'est avant tout comprendre en faisant. Bon courage pour tes révisions, tu vas y arriver ! 🚀
