Un moteur de recherche en 80 lignes de Python

• microsearch est une implémentation jouet destinée à comprendre concrètement l’intérieur d’un moteur de recherche : la classe centrale du moteur tient en moins de 80 lignes, mais le projet est plus vaste si l’on inclut le crawler, l’API et les templates HTML
• Partant du constat que les petits sites web et blogs sont difficiles à découvrir via les grands moteurs de recherche, il collecte des articles depuis 642 flux RSS pour constituer les données de recherche
• Grâce au crawl asynchrone basé sur asyncio, le temps de collecte est passé de 20 minutes à 20 secondes, et le corps de texte nettoyé est stocké sous forme de données Parquet
• La recherche fonctionne sur un index inversé qui associe les mots à leur nombre d’occurrences par URL, et le tri des résultats utilise BM25, fondé sur le contenu, plutôt que PageRank, fondé sur les liens
• Une UI FastAPI fournit un champ de recherche et des pages de résultats, mais des fonctionnalités comme les opérateurs de requête, l’indexation en n-grammes, l’expansion de requêtes/documents ou l’indexation pendant le crawl sont encore absentes

---

Objectif et périmètre de microsearch

• microsearch est une implémentation de moteur de recherche en Python publiée dans un dépôt GitHub
• L’objectif n’est pas de créer un moteur de recherche de production, mais un exemple jouet utilisable montrant comment un moteur de recherche fonctionne en interne
• Le corpus visé ressemble davantage à de petits sites web et blogs, souvent peu visibles dans la concurrence SEO sur Google
• L’implémentation centrale du moteur de recherche fait moins de 80 lignes, mais l’ensemble du projet est plus volumineux si l’on inclut le code auxiliaire comme le crawler de données, l’API et les templates HTML
• L’implémentation est née d’un travail avec Solr et Lucene, dans le cadre d’une démarche visant à comprendre plus en profondeur le fonctionnement des moteurs de recherche

Crawler basé sur RSS

• Pour constituer les données à rechercher, des flux RSS de blogs sont crawlés
• Le corpus utilise au total 642 flux RSS
  • Environ 100 proviennent de blogs lus directement, sur le ML, la data science, les mathématiques, etc.
  • Les quelque 500 restants proviennent du projet surprisetalk blogs.hn
• Le crawl consiste à extraire les URL des articles depuis chaque flux RSS, à télécharger le HTML des articles, puis à nettoyer le texte du corps
• Le nettoyage HTML utilise BeautifulSoup pour supprimer script et style, puis transforme le contenu en texte en normalisant les retours à la ligne et les espaces
• Le crawl asynchrone avec aiohttp et asyncio a réduit le temps d’exécution de 20 minutes à 20 secondes
• Le résultat est placé dans un DataFrame contenant les URL et le corps de texte nettoyé, puis enregistré dans output.parquet

Structure de l’index inversé

• La première structure de données clé du moteur de recherche est l’index inversé
• Un index inversé associe des mots-clés à des documents, ce qui permet de retrouver rapidement dans quels documents apparaît un mot donné
• L’implémentation utilise un defaultdict de forme dict[str, dict[str, int]]
  • La clé externe est le mot
  • La clé interne est l’URL
  • La valeur interne est le nombre de fois où ce mot apparaît dans le document de cette URL
• La classe SearchEngine possède deux dictionnaires internes
  • _index : stocke le nombre d’occurrences par URL pour chaque mot
  • _documents : stocke le contenu original par URL
• index(url, content) normalise le contenu, le sépare par espaces, puis incrémente le nombre d’occurrences de chaque mot par URL
• bulk_index() reçoit une liste d’URL et de contenus, et indexe plusieurs documents en une seule fois
• get_urls(keyword) normalise le mot-clé, puis renvoie les URL contenant ce mot ainsi que son nombre d’occurrences

Normalisation des chaînes et recherche de base

• La normalisation des chaînes remplace la ponctuation par des espaces, supprime les espaces en double, puis convertit en minuscules
• Pour réduire les différences de casse, Foo et foo sont traités comme le même mot-clé
• Si l’on indexe deux documents d’exemple, une recherche sur foo renvoie les deux documents
  • Foo : Hello, World! My name is Foo!
  • Bar : Hello, World! My name is Bar, I'm not Foo!
• À ce stade, on sait seulement si un document contient le terme recherché et combien de fois il le contient ; un classement séparé est donc nécessaire pour ordonner les résultats

Ranker BM25

• Le tri des résultats de recherche utilise BM25
• PageRank classe les documents à partir des liens, tandis que BM25 calcule un score à partir du contenu des documents
• SearchEngine possède les paramètres par défaut k1=1.5 et b=0.75 pour le calcul BM25
• La classe fournit les propriétés nécessaires au calcul du classement
  • posts : liste des URL indexées
  • number_of_documents : nombre total de documents
  • avdl : longueur moyenne des documents
• idf(kw) calcule la fréquence inverse de document d’un mot-clé donné
  • Nombre total de documents N
  • Nombre de documents contenant ce mot-clé n_kw
  • Utilise la formule log((N - n_kw + 0.5) / (n_kw + 0.5) + 1)
• bm25(kw) calcule le score BM25 pour chaque URL contenant ce mot-clé
• search(query) normalise la requête, la découpe en mots, puis renvoie la somme des scores BM25 de chaque mot par URL
• Dans l’exemple, une recherche sur foo seul donne au document Foo un score supérieur à Bar, tandis qu’une recherche sur foo bar donne un meilleur score au document Bar

Interface FastAPI

• Le moteur de recherche est exposé sous forme de petite application FastAPI
• L’application crée une instance de SearchEngine et, au démarrage, lit les URL et contenus depuis les données Parquet pour les indexer avec bulk_index()
• Les principales routes sont au nombre de trois
  • / : rend la page de recherche et transmet la liste des articles indexés
  • /results/{query} : exécute la recherche et affiche les 5 meilleures URL sur la page de résultats
  • /about : rend la page de présentation
• Les résultats sont triés par score décroissant, puis seuls les top-N URL sont sélectionnés
• L’UI et l’UX ont une grande marge d’amélioration, mais la recherche fonctionne rapidement et les résultats ne sont pas mauvais

Fonctionnalités manquantes et limites

• L’implémentation ne comprend pas plusieurs fonctionnalités que l’on attendrait d’un vrai moteur de recherche
• Il n’y a pas d’opérateurs de requête
  • Par exemple, elle ne prend pas en charge les recherches excluant un mot précis, comme how to build a search engine -solr sur Google
• Il n’y a pas d’indexation en n-grammes
  • La recherche de documents où deux mots apparaissent dans un ordre précis, comme "search engine", n’est pas prise en charge
• Il n’y a pas d’expansion de requête ou de document
  • Une recherche sur engine ne trouve pas automatiquement les documents contenant engines
• Le crawl et l’indexation sont séparés
  • Il serait possible de les intégrer en indexant les documents dès leur réception, et de rendre également ce processus asynchrone

Prochaines étapes

• Le projet permet de mieux se faire une intuition de la manière dont Solr fonctionne en interne
• Il confirme aussi que le code asynchrone est très efficace pour les tâches centrées sur les E/S
• La prochaine étape consiste à ajouter au moteur de recherche une fonctionnalité de recherche sémantique
• Des expérimentations ont été menées avec des modèles d’embeddings et l’ANN, et le prochain travail consiste à intégrer cette fonctionnalité dans microsearch

[GN⁺]

Commentaires sur Hacker News

• C’est vraiment génial. Je suis en train de créer avec Pandas un moteur de recherche BM25 assez rapide pour des tests en local : https://github.com/softwaredoug/searcharray
  Si j’utilise Pandas, c’est parce que BM25 seul ne suffit pas, et que je veux calculer et combiner facilement avec pandas/numpy d’autres facteurs comme la fraîcheur ou la popularité
  À noter que la partie difficile, c’est la recherche d’expressions exactes. Le matching d’expressions a beaucoup de cas limites, et il faut aussi prendre en compte des choses comme le slop. Il faut également compresser les informations de position avec le moins de mémoire possible : https://github.com/softwaredoug/searcharray/blob/main/searcharray/utils/roaringish.py

  • J’ai déjà traité le matching d’expressions dans un projet jouet : https://github.com/vasilionjea/lofi-dx/blob/main/test/search/inverted-search.test.ts#L140
    Je pense avoir testé ça assez à fond, mais je serais ravi d’avoir des retours. Les informations de position ont été encodées en delta puis en base36
  • Je me demande si l’ajout d’une analyse de sentiment a aidé pour le traitement des expressions, ou si au contraire ça a nui. Les expressions sont difficiles à gérer, et je réfléchis à ce qu’on peut faire pour améliorer les performances
  • Je me demande comment tu es tombé sur cet article et as commenté aussi vite. Est-ce que tu utilises un outil de veille de recherche qui parcourt la première page pour repérer des mots-clés qui t’intéressent, ou est-ce juste un hasard ?

• C’est vrai. Dans la recherche, la plus grande partie de la difficulté consiste à gérer l’échelle des données. La logique elle-même est étonnamment simple, ou peut facilement le devenir
  Bien sûr, on peut la rendre infiniment complexe, mais ce projet a bien éliminé le superflu. Si on aborde le sujet non pas comme un problème de rendre le moteur de recherche plus gros, mais de rendre physiquement les données plus petites ou d’augmenter le rapport signal/bruit, on peut aller très loin

• Dans src/microsearch/engine.py, il y a du code comme SearchEngine.__init__(self, k1: float = 1.5, b: float = 0.75), mais je n’ai absolument aucune idée de ce que sont k1 ou b, et il n’y a pas un seul commentaire dans tout le fichier
  Les commentaires ne sont plus à la mode en ce moment ? J’imagine que _documents est une clé URL avec comme valeur le contenu de cette URL, mais je peux me tromper. Ça aurait pu être une ressource pour apprendre à construire et étendre un moteur de recherche, mais l’absence de documentation est dommage pour la qualité du code

  • C’est expliqué dans l’article, qui sert lui-même de documentation au code. Le lien vers BM25 renvoie au contexte mathématique, et en cherchant un peu plus sur les paramètres de BM25, on trouve aussi des articles expliquant comment les choisir
  • Pour rendre le titre accrocheur, il fallait réduire autant que possible le nombre de lignes de code ;)
    Plus sérieusement, je suis d’accord qu’en général il vaut mieux avoir la documentation et le code ensemble. Mais ici, c’est un projet pédagogique, donc l’idée était de séparer le code et la doc, et de documenter le code dans l’article de blog
  • Je suis sur mobile donc je ne peux pas regarder en détail, mais k1 et b sont des valeurs de pondération standard utilisées dans TF-IDF ou BM25, ici côté BM25
    Des commentaires seraient utiles, mais pour quelqu’un de familier avec le sujet, ce sont aussi des noms immédiatement reconnaissables
  • k1 et b sont des paramètres d’ajustement de la fonction de classement BM25. Ce ne sont pas des noms inventés par l’auteur original : pratiquement toutes les implémentations et tous les manuels utilisent ces mêmes noms de variables
    Pour qu’une personne connaissant la recherche d’information comprenne, il est même plus juste de les appeler k1 et b : https://en.wikipedia.org/wiki/Okapi_BM25
  • Quand je vois un style du genre a: float, ça me rappelle toujours la conférence de Rich Hickey sur le fait qu’on n’a pas besoin de types, mais de bons noms
    Je déteste vraiment cette tendance, qui donne l’impression de venir de Go, à utiliser des variables d’une seule lettre sans explication et à détourner le système de types comme outil d’appoint pour le nommage. Les noms doivent être bien choisis, car ils peuvent transmettre une information de sens sur ce que fait le programme

• Je ne vois pas trop l’intérêt de se vanter du nombre de lignes de code en utilisant des dépendances externes au lieu de compter le nombre total de \r\n
  Il n’existe pas d’unité SI officielle pour mesurer une base de code, mais je pense qu’il faut bien trouver un moyen de mesurer la charge cognitive

  • Ce n’est pas un critère officiel, mais dans notre équipe on dit parfois, en référence à https://grugbrain.dev, « ce code n’est pas grug » ou « ce code est plutôt grug »
  • Le moteur de recherche en 80 lignes lui-même n’utilise pas de dépendances externes. Il importe seulement collections, math et string, tout le reste vient de la bibliothèque standard
    Plus précisément, on pourrait même dire qu’il s’agit d’un « moteur de moteur de recherche ». Le crawler et l’interface ne sont pas inclus dans ces 80 lignes, mais ils sont nécessaires sous une forme ou une autre, et l’implémentation présentée augmente assez nettement le nombre de lignes et de bibliothèques. Cela dit, ces bibliothèques ne concernent pas le moteur de recherche lui-même. Si on commence à compter des dépendances génériques comme pandas ou fastapi, alors il faudrait peut-être aussi compter les millions de lignes du système d’exploitation, le firmware de la carte réseau, ou la complexité du matériel
  • Pourquoi ne pas célébrer l’accomplissement industriel qui a rendu possible de faire ce genre de chose en 80 lignes ?
  • Ici, ça a du sens. Si le titre avait été « Un moteur de recherche en Python en 4000 lignes », la plupart des gens seraient passés à autre chose, mais 80 lignes, c’est assez court pour donner envie d’y jeter un œil
  • À l’ancienne, il y a la complexité cyclomatique

• J’aime bien. On pourrait aussi faire un moteur de recommandation en moins de 20 lignes à utiliser avec le moteur de recherche. Si on conserve les logs de session des URL cliquées, on peut regarder, dans chaque session, une fenêtre glissante après l’URL actuelle et attribuer un poids plus élevé aux liens les plus proches afin de construire une liste de recommandations
  En triant les recommandations et en ne gardant que les N premières, on obtient une liste d’URL recommandées pour une URL donnée. Avec quelques ajustements, on peut aussi mélanger dans les logs les requêtes saisies et les URL cliquées pour produire des suggestions orthographiques

• Très cool et instructif. Cela dit, ne le déployez pas :-)
  J’ai eu besoin de quelque chose de similaire il y a longtemps, mais à une échelle un peu plus grande, avec quelques dizaines de milliers de documents, et la réponse était, comme souvent, sqlite. Structurellement, c’est la même chose qu’ici, sauf que la couche de persistance de l’index inversé avait été écrite par quelqu’un d’autre à ma place

  • J’utilise SQLite FTS presque partout, et ça ne m’a jamais déçu
  • Il y a même exactement la même formule. Ce commentaire m’a donné un vrai « frisson de compréhension »

• Avec Google, si on cherche avec des guillemets comme "search engine", il n’affiche que les résultats où les deux mots apparaissent dans cet ordre
  C’est vrai au moins dans certains cas, mais malheureusement pas toujours. Ce que veulent les utilisateurs avancés, c’est un « grep pour le web », pas « ce que Google a envie de vous montrer »

  • Je parierais que presque personne ne veut réellement un « grep pour le web ». Même comparé à un moteur de recherche qui ne fait qu’une très légère expansion de requête, un grep pour le web est clairement moins bon
    Google prend certes trop de libertés dans son interprétation des requêtes, mais il y a aussi beaucoup de traitements qu’il vaut clairement mieux faire que ne pas faire, quel que soit le moteur. Le problème de Google Search aujourd’hui, c’est qu’il est difficile de déduire pourquoi il renvoie tel résultat, et on dirait que c’est parce qu’il s’appuie beaucoup trop sur les embeddings plutôt que sur la comparaison de chaînes. C’est frustrant quand "cat food" correspond à "dog restaurant" : dans l’espace des embeddings, c’est sémantiquement proche, mais cela ne correspond pas au raisonnement humain

• Je ne trouve pas très honnête de parler de 80 lignes de code quand on utilise des bibliothèques externes comme feedparser, bs4, etc.

  • Je serais d’accord si c’était construit sur elasticsearch, mais si la partie moteur de recherche elle-même est effectivement implémentée dans ces 80 lignes, alors je trouve ça honnête. Les bibliothèques importées sont justement du genre qu’il vaut mieux ne pas réécrire soi-même
    Parfois, un article intitulé « créer mon propre moteur de recherche » n’est en réalité qu’un guide d’installation de searxng ou yacy, mais ici ce n’est pas le cas
  • Si la dépendance est très courante et grand public, ça me va

• Bien. Il ne devrait pas être très difficile d’ajouter ici une fonctionnalité de recherche floue. Par exemple, faire en sorte qu’une recherche sur "hackrnew" corresponde à "hackernews", en trouvant les résultats dont la distance d’édition sur préfixe est inférieure à un certain seuil
  L’idée de base consiste à ajouter un index inversé supplémentaire, dont les clés sont les n-grammes des mots présents dans la collection de documents (en général des 3-grammes), et dont les postings sont les mots ou identifiants de mots où ces n-grammes apparaissent. On peut utiliser le lemme auxiliaire PED(x, y) <= delta alors |N(x) ∩ N(y)| >= |N(x)| - n ∙ delta. On calcule les n-grammes de l’entrée x, on récupère les postings de chacun de ces n-grammes, puis on fusionne les doublons pour obtenir, pour chaque mot candidat y, le nombre de n-grammes partagés. Si ce nombre dépasse le seuil, on calcule alors le PED réel ; sinon, on l’ignore, ce qui permet de réduire fortement les calculs coûteux
  Il suffit ensuite d’interroger l’index existant avec la liste de mots ainsi obtenue. J’ai déjà utilisé cette approche pour créer un moteur de recherche flou en JS côté client sur https://dont.watch/. En regardant le code JS, on peut voir que l’index inversé et l’index de n-grammes compressé sont transmis tels quels dans des fichiers JS. Le moteur de recherche lui-même fait environ 300 lignes de JS sans dépendance externe, avec seulement des heuristiques très basiques pour améliorer les résultats

  • Avec cette méthode, de combien augmente la taille de l’index ?