Moteur de recherche NSI : PageRank et algorithmes

Tu tapes une requête sur un moteur de recherche et, en une fraction de seconde, il te propose des millions de résultats classés du plus pertinent au moins pertinent. Derrière ce tour de magie se cache un des algorithmes les plus célèbres de l'informatique : PageRank. Dans cet article, on va décortiquer ensemble comment un moteur de recherche fonctionne, pourquoi ce sujet tombe régulièrement au bac NSI, et comment tu peux transformer cette notion en points faciles le jour de l'épreuve.

Pourquoi le moteur de recherche est un sujet en or en NSI

Le programme de NSI fait la part belle aux graphes, aux algorithmes et à la représentation de l'information. Le moteur de recherche est un cas d'usage parfait : il combine ces trois thèmes. Un moteur de recherche, c'est d'abord un immense graphe orienté où chaque page web est un sommet et chaque lien hypertexte une arête. C'est ensuite un algorithme qui parcourt ce graphe pour attribuer un score à chaque page. C'est enfin une structure de données (index, table de hachage) qui permet de retrouver en quelques millisecondes les pages contenant un mot donné.

Quand tu maîtrises ce sujet, tu maîtrises en réalité une bonne partie du programme : graphes, parcours, matrices, complexité, dictionnaires. C'est pour ça qu'on retrouve souvent des questions sur le moteur de recherche NSI dans les sujets de bac. Si tu veux consolider les bases avant d'attaquer cet article, jette un œil à la page cours NSI du site, puis reviens ici pour la mise en pratique.

Un peu d'histoire : de Yahoo! à Google

Dans les années 1990, les moteurs de recherche classaient les pages principalement en comptant les occurrences de mots-clés. Résultat : des pages bourrées de mots répétés sans aucune valeur remontaient en tête. En 1998, Larry Page et Sergey Brin, deux étudiants de Stanford, proposent une idée radicale : une page est importante si d'autres pages importantes pointent vers elle. Cette intuition donne naissance à l'algorithme PageRank et au moteur Google. L'idée est élégante, mathématique, et surtout implémentable en Python en quelques lignes — parfait pour la NSI.

Comprendre PageRank sans se perdre dans les maths

Imagine un petit web de 4 pages : A, B, C et D. Chaque page contient des liens vers d'autres pages. On peut représenter ce mini-web sous forme de graphe orienté :

• A pointe vers B et C
• B pointe vers C
• C pointe vers A
• D pointe vers C

L'idée de PageRank : un internaute se balade au hasard sur ce web. À chaque étape, il clique sur un lien sortant de la page où il se trouve. Sur le long terme, certaines pages seront visitées plus souvent que d'autres. La probabilité de se trouver sur une page donnée à long terme est son score PageRank.

La formule simplifiée

Pour une page P, on note PR(P) son score et L(Q) le nombre de liens sortants de la page Q. La formule est :

PR(P) = somme sur chaque page Q pointant vers P de ( PR(Q) / L(Q) )

Autrement dit, chaque page Q distribue équitablement son propre score entre toutes les pages vers lesquelles elle pointe. Une page qui reçoit beaucoup de liens, ou des liens venant de pages à fort score, obtient donc un score élevé. C'est l'idée centrale à retenir pour l'épreuve.

Le facteur d'amortissement (damping factor)

Dans la vraie vie, un internaute ne clique pas indéfiniment : à un moment, il tape une nouvelle URL. Google modélise ce comportement avec un facteur d (souvent 0,85). Avec probabilité 0,85 on suit un lien, avec probabilité 0,15 on saute vers une page au hasard. La formule complète devient :

PR(P) = (1 - d) / N + d * somme( PR(Q) / L(Q) )

où N est le nombre total de pages. Ce facteur d garantit aussi que l'algorithme converge même si le graphe contient des cycles ou des pages sans lien sortant.

Implémenter PageRank en Python

Passons à la pratique. On va écrire une version simplifiée de PageRank, testable directement dans ton éditeur Python préféré. On représente le graphe par un dictionnaire d'adjacence.

# Graphe orienté représenté par un dictionnaire d'adjacence
# graphe[page] = liste des pages vers lesquelles elle pointe
graphe = {
    'A': ['B', 'C'],
    'B': ['C'],
    'C': ['A'],
    'D': ['C']
}

def pagerank(graphe, d=0.85, iterations=100):
    pages = list(graphe.keys())
    N = len(pages)
    # score initial identique pour toutes les pages
    scores = {p: 1 / N for p in pages}

    for _ in range(iterations):
        nouveaux_scores = {}
        for p in pages:
            # terme d'amortissement : probabilité de tomber sur p au hasard
            score = (1 - d) / N
            # on additionne les contributions des pages qui pointent vers p
            for q in pages:
                if p in graphe[q]:
                    score += d * scores[q] / len(graphe[q])
            nouveaux_scores[p] = score
        scores = nouveaux_scores

    return scores

resultat = pagerank(graphe)
for page, score in sorted(resultat.items(), key=lambda x: -x[1]):
    print(page, round(score, 4))

Quelques remarques importantes :

• On initialise tous les scores à 1/N : c'est neutre et ça évite de favoriser une page arbitrairement.
• On répète l'itération un grand nombre de fois : à chaque tour, les scores se rapprochent de la valeur limite. On dit que l'algorithme converge.
• La complexité est en O(iterations × N²) dans cette version naïve. Les vrais moteurs utilisent des matrices creuses et du calcul parallèle, mais le principe reste le même.

Vérifier la cohérence du résultat

Un bon réflexe en NSI : vérifier que la somme des scores vaut 1 (propriété d'une distribution de probabilité). Ajoute cette ligne à la fin de ton script :

print('Somme des scores :', sum(resultat.values()))

Tu dois obtenir une valeur très proche de 1. Si ce n'est pas le cas, c'est que tu as oublié le terme (1-d)/N ou que tu as mal normalisé. Ce genre de vérification te fait gagner des points précieux au bac, car les correcteurs valorisent l'esprit critique.

Du PageRank au vrai moteur de recherche

PageRank ne fait que classer les pages par importance globale. Mais un moteur de recherche doit aussi répondre à une requête précise. Voici les grandes étapes d'un moteur réel :

• Crawl : des robots parcourent le web en suivant les liens, un peu comme un parcours en largeur dans un graphe.
• Indexation : on construit un index inversé, c'est-à-dire un dictionnaire qui associe chaque mot aux pages qui le contiennent. C'est une structure de type table de hachage.
• Requête : quand tu tapes un mot, le moteur retrouve en temps quasi constant les pages de l'index, puis les classe par score combinant pertinence et PageRank.

Le lien avec le cours SQL est direct : un index inversé se modélise très bien par une base de données relationnelle avec une table mots, une table pages et une table d'association. Tu peux même t'entraîner à écrire des requêtes SQL qui simulent un mini-moteur de recherche.

Un exemple concret : chercher un mot dans un index

index_inverse = {
    'python': ['page1', 'page3', 'page7'],
    'algorithme': ['page2', 'page3'],
    'graphe': ['page1', 'page7']
}

def rechercher(mot):
    return index_inverse.get(mot.lower(), [])

print(rechercher('Python'))  # ['page1', 'page3', 'page7']

Tu vois la puissance de la structure : la recherche est en O(1) en moyenne, ce qui permet de traiter des milliards de pages. C'est exactement ce genre d'exemple qui fait la différence dans une copie de bac.

Méthode de révision et lien avec l'épreuve du bac NSI

Pour réussir les questions sur le moteur de recherche NSI et PageRank, voici une méthode en 4 étapes que je te conseille :

• Étape 1 — Maîtrise le vocabulaire : graphe orienté, sommet, arc, degré entrant, degré sortant, matrice d'adjacence. Sans ça, tu ne peux pas répondre correctement.
• Étape 2 — Sais écrire la formule : la formule de PageRank avec et sans facteur d'amortissement. Entraîne-toi à la recopier de mémoire.
• Étape 3 — Code à la main : écris l'algorithme sur papier, puis teste-le en Python. Repère les pièges : initialisation, division par zéro si une page n'a aucun lien sortant, convergence.
• Étape 4 — Fais des exercices : sur le site, la section exercices NSI propose des graphes à analyser. C'est en pratiquant que tu gagnes en vitesse.

Pour aller plus loin sur la méthode de travail et l'organisation des révisions, tu peux aussi consulter les ressources d'Allolycée qui couvrent l'ensemble du lycée, et pour un accompagnement plus large, Allobac propose des fiches méthode très utiles. Ces sites complètent bien le travail fait en classe.

Les erreurs classiques à éviter

• Oublier le facteur (1-d)/N : la somme des scores ne vaut plus 1.
• Confondre liens entrants et liens sortants. Une page reçoit du score via ses liens entrants.
• Diviser par len(graphe[q]) alors que q n'a pas de successeur : pense au cas des pages puits (dangling nodes).
• Croire que PageRank donne une vérité absolue : c'est un score relatif, qui dépend du graphe considéré.

Conclusion : un algorithme, mille compétences

Le moteur de recherche est bien plus qu'un sujet de cours : c'est une porte d'entrée vers les graphes, les probabilités, les structures de données et la complexité algorithmique. En travaillant PageRank, tu apprends à modéliser un problème réel, à écrire un algorithme itératif, et à vérifier tes résultats. Ces compétences te serviront bien au-delà du bac NSI : en prépa, en licence d'informatique, et même dans ta vie de tous les jours quand tu utiliseras un moteur de recherche.

Alors n'aie pas peur de ce sujet. Prends un papier, dessine un petit graphe de 4 ou 5 pages, applique la formule à la main, puis code-la en Python. Tu verras qu'en une heure de pratique sérieuse, tu maîtriseras un algorithme que des ingénieurs ont mis des années à populariser. Et si tu veux continuer sur cette lancée, explore les autres cours et exercices du site : chaque notion que tu maîtrises aujourd'hui est une brique de plus pour ton projet d'orientation. Bon courage, tu vas y arriver !