Eine Suchmaschine in 80 Zeilen Python

 (alexmolas.com)
6 Punkte von GN⁺ 2024-02-08 | 1 Kommentare | Auf WhatsApp teilen
  • microsearch ist eine Toy-Implementierung, um das Innenleben einer Suchmaschine direkt zu verstehen. Die zentrale Suchmaschinenklasse umfasst weniger als 80 Zeilen, mit Crawler, API und HTML-Templates ist das Projekt aber größer.
  • Vor dem Hintergrund, dass kleine Websites und Blogs von großen Suchmaschinen oft schlecht gefunden werden, wurden Beiträge aus 642 RSS-Feeds gesammelt, um Suchdaten zu erstellen.
  • Durch asynchrones Crawling auf Basis von asyncio sank die Erfassungszeit von 20 Minuten auf 20 Sekunden; der bereinigte Haupttext wird als Parquet-Daten gespeichert.
  • Die Suche arbeitet auf einem invertierten Index, der Wörter mit ihrer Häufigkeit pro URL verknüpft; für das Ranking der Ergebnisse wird statt linkbasiertem PageRank das inhaltsbasierte BM25 verwendet.
  • Eine FastAPI-Oberfläche bietet Suchfeld und Ergebnisseite, aber Funktionen wie Query-Operatoren, n-Gram-Indexierung, Query-/Dokumenterweiterung oder Indexierung während des Crawlings fehlen noch.

Ziel und Umfang von microsearch

  • microsearch ist eine in einem GitHub-Repository veröffentlichte Python-Implementierung einer Suchmaschine.
  • Das Ziel ist keine Suchmaschine für den Produktiveinsatz, sondern ein nutzbares Toy-Beispiel, das zeigt, wie Suchmaschinen intern funktionieren.
  • Das Suchziel liegt näher bei kleinen Websites und Blogs, die im Google-SEO-Wettbewerb nicht gut gefunden werden.
  • Die Kernimplementierung der Suchmaschine umfasst weniger als 80 Zeilen, aber mit Hilfscode wie Daten-Crawler, API und HTML-Templates ist das Gesamtprojekt größer.
  • Die Implementierung entstand beim Arbeiten mit Solr und Lucene sowie beim Versuch, die Funktionsweise von Suchmaschinen tiefer zu verstehen.

RSS-basierter Crawler

  • Um Daten für die Suche zu erzeugen, werden Blog-RSS-Feeds gecrawlt.
  • Insgesamt wurden 642 RSS-Feeds verwendet.
    • Etwa 100 davon sind Blogs, die der Autor selbst liest, etwa zu ML, Data Science und Mathematik.
    • Die übrigen rund 500 stammen aus dem Projekt surprisetalk blogs.hn.
  • Das Crawling folgt dem Ablauf, aus jedem RSS-Feed Beitrags-URLs zu extrahieren, das HTML der Beiträge herunterzuladen und anschließend den Haupttext zu bereinigen.
  • Die HTML-Bereinigung entfernt mit BeautifulSoup script und style und wandelt den Inhalt nach Bereinigung von Zeilenumbrüchen und Leerraum in Text um.
  • Mit asynchronem Crawling über aiohttp und asyncio sank die Laufzeit von 20 Minuten auf 20 Sekunden.
  • Das Ergebnis wird als DataFrame mit URL und bereinigtem Haupttext erstellt und in output.parquet gespeichert.

Struktur des invertierten Index

  • Die erste zentrale Datenstruktur der Suchmaschine ist der invertierte Index.
  • Ein invertierter Index bildet Keywords auf Dokumente ab und ermöglicht so, schnell zu finden, in welchen Dokumenten ein bestimmtes Wort vorkommt.
  • Die Implementierung verwendet ein defaultdict in der Form dict[str, dict[str, int]].
    • Der äußere Schlüssel ist das Wort.
    • Der innere Schlüssel ist die URL.
    • Der innere Wert ist die Anzahl, wie oft das Wort im Dokument dieser URL vorkommt.
  • Die Klasse SearchEngine besitzt zwei interne Dictionaries.
    • _index: speichert die Häufigkeit pro URL für jedes Wort
    • _documents: speichert den Originalinhalt pro URL
  • index(url, content) normalisiert den Inhalt, teilt ihn an Leerzeichen auf und erhöht dann für jedes Wort die Häufigkeit pro URL.
  • bulk_index() nimmt Listen von URLs und Inhalten entgegen und indexiert mehrere Dokumente auf einmal.
  • get_urls(keyword) normalisiert das Keyword und gibt die URLs zurück, die dieses Wort enthalten, zusammen mit ihrer Häufigkeit.

String-Normalisierung und einfache Suche

  • Die String-Normalisierung ersetzt Satzzeichen durch Leerzeichen, bereinigt mehrfachen Leerraum und wandelt alles in Kleinbuchstaben um.
  • Um Unterschiede bei Groß- und Kleinschreibung zu verringern, werden Foo und foo als dasselbe Keyword behandelt.
  • Wenn zwei Beispieldokumente indexiert werden, liefert eine Suche nach foo beide Dokumente zurück.
    • Foo: Hello, World! My name is Foo!
    • Bar: Hello, World! My name is Bar, I'm not Foo!
  • In diesem Schritt ist nur bekannt, ob ein Dokument den Suchbegriff enthält und wie oft; um die Reihenfolge der Ergebnisse festzulegen, ist daher ein separates Ranking nötig.

BM25-Ranker

  • Für die Sortierung der Suchergebnisse wird BM25 verwendet.
  • PageRank rankt Dokumente auf Basis von Links, BM25 berechnet dagegen Bewertungen auf Grundlage des Dokumentinhalts.
  • SearchEngine besitzt für die BM25-Berechnung die Standardparameter k1=1.5 und b=0.75.
  • Die Klasse stellt Eigenschaften bereit, die für die Ranking-Berechnung benötigt werden.
    • posts: Liste der indexierten URLs
    • number_of_documents: Gesamtzahl der Dokumente
    • avdl: durchschnittliche Dokumentlänge
  • idf(kw) berechnet die inverse Dokumenthäufigkeit für ein bestimmtes Keyword.
    • Gesamtzahl der Dokumente N
    • Anzahl der Dokumente mit diesem Keyword n_kw
    • Verwendet wird die Formel log((N - n_kw + 0.5) / (n_kw + 0.5) + 1)
  • bm25(kw) berechnet für jede URL, die das Keyword enthält, den BM25-Score.
  • search(query) normalisiert die Query, zerlegt sie in Wörter und summiert dann die BM25-Scores der einzelnen Wörter pro URL.
  • Im Beispiel erhält bei einer Suche nur nach foo das Dokument Foo einen höheren Score als Bar; bei einer Suche nach foo bar erhält Bar den höheren Score.

FastAPI-Oberfläche

  • Die Suchmaschine wird als kleine FastAPI-App bereitgestellt.
  • Die App erzeugt eine Instanz von SearchEngine und liest beim Start URLs und Inhalte aus den Parquet-Daten, um sie mit bulk_index() zu indexieren.
  • Es gibt drei zentrale Routen.
    • /: rendert die Suchseite und übergibt die Liste der indexierten Beiträge
    • /results/{query}: durchsucht die Query und zeigt die Top 5 URLs auf der Ergebnisseite an
    • /about: rendert eine Infoseite
  • Die Ergebnisse werden absteigend nach Score sortiert, anschließend werden nur die Top-N-URLs ausgewählt.
  • Bei UI und UX gibt es noch viel Raum für Verbesserungen, aber die Suche arbeitet schnell und die Ergebnisse sind nicht schlecht.

Fehlende Funktionen und Einschränkungen

  • In der Implementierung fehlen mehrere Funktionen, die man von einer echten Suchmaschine erwarten würde.
  • Es gibt keine Query-Operatoren.
    • Eine Suche wie bei Google how to build a search engine -solr, bei der bestimmte Wörter ausgeschlossen werden, wird zum Beispiel nicht unterstützt.
  • Es gibt keine n-Gram-Indexierung.
    • Damit wird keine Suche unterstützt, die nur Dokumente findet, in denen zwei Wörter in einer bestimmten Reihenfolge vorkommen, etwa "search engine".
  • Es gibt keine Query- oder Dokumenterweiterung.
    • Wer nach engine sucht, findet nicht automatisch auch Dokumente, die engines enthalten.
  • Crawling und Indexierung sind getrennt.
    • Beides könnte so integriert werden, dass Dokumente direkt beim Empfang indexiert werden, und auch dieser Prozess ließe sich asynchron gestalten.

Nächste Schritte

  • Durch das Projekt entsteht mehr Intuition dafür, wie Solr intern funktioniert.
  • Bestätigt hat sich auch, dass asynchroner Code bei IO-lastigen Aufgaben einen großen Effekt hat.
  • Der nächste Schritt ist, der Suchmaschine semantische Suche hinzuzufügen.
  • Es wurde bereits mit Embedding-Modellen und ANN experimentiert, und diese Funktion in microsearch zu integrieren, ist die nächste Aufgabe.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-02-08
Meinungen auf Hacker News

  • Das ist wirklich cool. Ich baue mit Pandas eine ziemlich schnelle BM25-Suchmaschine für lokale Tests: https://github.com/softwaredoug/searcharray
    Der Grund für Pandas ist, dass BM25 allein nicht ausreicht; ich möchte andere Faktoren wie Aktualität und Popularität mit pandas/numpy leicht berechnen und kombinieren können.
    Nebenbei: Phrasensuche ist der schwierige Teil. Beim Phrase Matching gibt es viele Grenzfälle, und Dinge wie Slop müssen ebenfalls berücksichtigt werden. Positionsinformationen müssen außerdem in möglichst wenig Speicher komprimiert werden: https://github.com/softwaredoug/searcharray/blob/main/searcharray/utils/roaringish.py

    • Ich habe in einem Spielzeugprojekt Phrase Matching behandelt: https://github.com/vasilionjea/lofi-dx/blob/main/test/search/inverted-search.test.ts#L140
      Ich denke, ich habe es ziemlich gründlich getestet, würde mich aber über Feedback freuen. Die Positionsinformationen habe ich delta-codiert und in base36 codiert.
    • Mich würde interessieren, ob das Einbauen von Sentimentanalyse bei der Phrasenverarbeitung geholfen hat oder eher geschadet hat. Phrasen sind schwer zu handhaben, und ich überlege, was man tun kann, um die Performance zu verbessern.
    • Mich würde interessieren, wie du diesen Beitrag so schnell gefunden und kommentiert hast. Nutzt du so etwas wie ein Such-Monitoring-Tool, das die erste Seite nach interessanten Keywords scannt, oder war es Zufall?

  • Stimmt. Die meisten schwierigen Teile bei Suche liegen im Umgang mit Datenumfang. Die Logik selbst kann erstaunlich einfach sein oder einfach gemacht werden.
    Natürlich kann man sie auch endlos kompliziert machen, aber dieses Projekt hat die unnötigen Teile gut weggelassen. Wenn man es nicht als Problem angeht, die Suchmaschine größer zu machen, sondern die Daten physisch kleiner zu machen oder das Signal-Rausch-Verhältnis zu erhöhen, kommt man ziemlich weit.

  • Wenn man sich src/microsearch/engine.py ansieht, gibt es dort Code wie SearchEngine.__init__(self, k1: float = 1.5, b: float = 0.75), aber ich habe keinerlei Ahnung, was k1 oder b sind, und in der gesamten Datei gibt es keinen einzigen Kommentar.
    Sind Kommentare heutzutage nicht mehr angesagt? _documents scheint ein Mapping zu sein, bei dem der Schlüssel die URL und der Wert der Inhalt dieser URL ist, aber ich könnte mich irren. Das hätte Material sein können, mit dem man lernen und erweitern kann, wie man eine Suchmaschine baut, aber wegen der fehlenden Dokumentation ist die Codequalität enttäuschend.

    • Dieser Teil wird im Artikel erklärt, und der Artikel selbst dient als Dokumentation des Codes. Der BM25-Link führt zum mathematischen Hintergrund, und wenn man ein wenig weiter nach BM25-Parametern sucht, findet man auch verwandte Artikel dazu, wie man sie auswählt.
    • Um den Titel des Artikels aufmerksamkeitsstark zu machen, musste die Zahl der Codezeilen so weit wie möglich reduziert werden ;)
      Spaß beiseite: Ich stimme zu, dass es normalerweise besser ist, wenn Dokumentation und Code zusammenstehen. In diesem Fall ist es aber ein Lehrprojekt, daher wurde Code und Dokumentation getrennt und der Code im Blogpost dokumentiert.
    • Ich bin am Handy und kann nicht im Detail nachsehen, aber k1 und b sind standardmäßige Gewichtungswerte, die bei TF-IDF oder BM25 verwendet werden; hier geht es um BM25.
      Kommentare wären hilfreich, aber für Leute, die mit diesem Problem vertraut sind, sind das auch sofort erkennbare Namen.
    • k1 und b sind Einstellungsparameter der BM25-Rankingfunktion. Das sind keine Namen, die sich der Autor des Originalbeitrags neu ausgedacht hat; fast alle Implementierungen und Lehrbücher verwenden diese Variablennamen.
      Damit jemand aus dem Information-Retrieval-Bereich es versteht, ist es sogar richtig, sie k1 und b zu nennen: https://en.wikipedia.org/wiki/Okapi_BM25
    • Bei Mustern wie a: float muss ich immer an Rich Hickeys Vortrag „Man braucht keine Typen, man braucht richtige Namen“ denken.
      Ich hasse diese Tendenz, die sich anfühlt, als käme sie aus Go: unerklärte einbuchstabige Variablennamen zu verwenden und das Typsystem als Hilfsmittel für Namen zu missbrauchen. Namen können semantische Informationen darüber vermitteln, was ein Programm tut, also sollte man sie richtig verwenden.

  • Ich verstehe nicht, was es bringen soll, mit der Anzahl der Codezeilen statt mit der gesamten Zahl der \r\n zu prahlen, wenn man externe Abhängigkeiten nutzt.
    Es gibt keine SI-Einheit zum Messen einer Codebase, aber die kognitive Last sollte man irgendwie messen.

    • Es ist kein offizieller Maßstab, aber in unserem Team sagen wir manchmal in Anlehnung an https://grugbrain.dev: „Dieser Code ist nicht grug“ oder „Dieser Code ist ziemlich grug“.
    • Die 80-Zeilen-Suchmaschine selbst verwendet keine externen Abhängigkeiten. Sie importiert nur collections, math und string, alles Standardbibliothek.
      Genauer gesagt wäre es vielleicht passender, sie „Suchmaschinen-Engine“ zu nennen. Crawler und Interface sind in diesen 80 Zeilen nicht enthalten, werden aber in irgendeiner Form benötigt, und die gezeigte Implementierung erhöht Zeilenzahl und Bibliotheken deutlich. Trotzdem haben diese Bibliotheken nichts mit der Suchmaschine selbst zu tun. Wenn man anfängt, allgemeine Abhängigkeiten wie pandas oder fastapi mitzuzählen, müsste man vielleicht auch die Millionen Zeilen des Betriebssystems, die Firmware der Netzwerkkarte und die Hardware-Komplexität mitzählen.
    • Warum sollte man nicht die Leistung der Branche feiern, dass so etwas inzwischen in 80 Zeilen möglich ist?
    • Hier hat es eine Bedeutung. Bei „Suchmaschine in 4000 Zeilen Python“ wären die meisten einfach weitergegangen, aber 80 Zeilen sind kurz genug, dass man einmal hineinschaut.
    • Nach der alten Methode gibt es die zyklomatische Komplexität.

  • Gefällt mir. Man kann auch eine Empfehlungs-Engine mit unter 20 Zeilen bauen, die zusammen mit einer Suchmaschine nutzbar ist. Wenn man Session-Logs der angeklickten URLs speichert, kann man in jeder Session ein Sliding Window hinter der aktuellen URL betrachten und näheren Links ein höheres Gewicht geben, um eine Empfehlungsliste zu erstellen.
    Wenn man die Empfehlungen sortiert und nur die Top N behält, erhält man eine Liste empfohlener URLs für eine bestimmte URL. Mit etwas Feinschliff kann man auch eingegebene Suchbegriffe und angeklickte URLs in den Logs mischen und daraus Rechtschreibvorschläge ableiten.

  • Sehr cool und lehrreich. Nur bitte nicht deployen :-)
    Früher brauchte ich mal etwas Ähnliches, allerdings in etwas größerem Maßstab mit einigen zehntausend Dokumenten, und die Antwort war wie immer sqlite. Strukturell ist es dasselbe wie hier, nur dass die Persistenzschicht für den invertierten Index jemand anderes für einen geschrieben hat.

    • SQLite FTS setze ich fast überall ein, und es hat mich noch nie enttäuscht.
    • Tatsächlich ist sogar dieselbe Formel drin. Dank dieses Kommentars hatte ich so etwas wie einen „Aha-Schauer“.

  • Google zeigt bei einer Suche mit Anführungszeichen wie "search engine" nur Ergebnisse an, in denen die beiden Wörter in genau dieser Reihenfolge vorkommen.
    Zumindest in manchen Fällen, aber leider nicht immer. Was Power-User wollen, ist „grep fürs Web“, nicht „Google sagt dir, was es dir zeigen will“.

    • Ich kann mit Sicherheit sagen, dass kaum jemand wirklich „grep fürs Web“ will. Selbst im Vergleich zu einer Suchmaschine, die nur minimale Query Expansion betreibt, ist grep fürs Web klar schlechter.
      Es stimmt, dass Google sich beim Interpretieren von Suchanfragen zu viele Freiheiten nimmt, aber es gibt viele Verarbeitungen, die bei jeder Suchmaschine eindeutig besser sind, als sie nicht zu machen. Das Problem der heutigen Google-Suche ist, dass schwer nachzuvollziehen ist, warum bestimmte Ergebnisse erscheinen; es wirkt, als läge das daran, dass sie sich beim String-Vergleich zu stark auf Embeddings stützt. Es ist frustrierend, wenn etwa "cat food" mit "dog restaurant" matcht: Im Embedding-Raum semantisch nah, aber nicht passend zur menschlichen Schlussfolgerung.

  • Ich finde es nicht fair, von 80 Zeilen Code zu sprechen, wenn externe Bibliotheken wie feedparser, bs4 usw. verwendet werden.

    • Wenn es auf elasticsearch gebaut wäre, würde ich zustimmen; wenn aber der eigentliche Suchmaschinen-Teil in diesen 80 Zeilen implementiert ist, finde ich es fair. Die eingebundenen Bibliotheken sind genau die Art von Dingen, die man besser nicht selbst implementiert.
      Manchmal sind Artikel mit dem Titel „Meine eigene Suchmaschine bauen“ in Wahrheit Installationsanleitungen für searxng oder yacy; das hier ist etwas anderes.
    • Wenn diese Abhängigkeiten sehr verbreitet und Mainstream sind, finde ich das in Ordnung.

  • Gut. Es dürfte auch nicht besonders schwer sein, hier Fuzzy Search hinzuzufügen. Zum Beispiel so, dass eine Suche nach "hackrnew" mit "hackernews" matcht, indem man Ergebnisse findet, deren Präfix-Edit-Distanz unter einem bestimmten Schwellwert liegt.
    Die Grundidee ist, einen weiteren invertierten Index anzulegen, dessen Schlüssel die n-Gramme (meist 3-Gramme) der Wörter in der Dokumentsammlung sind und dessen Postings die Wörter bzw. Wort-IDs sind, in denen dieses n-Gramm vorkommt. Man kann das Lemma PED(x, y) <= delta impliziert |N(x) ∩ N(y)| >= |N(x)| - n ∙ delta nutzen. Man berechnet die n-Gramme der Eingabe x, holt die Postings für jedes n-Gramm und führt Duplikate zusammen; so erhält man die Anzahl der n-Gramme, die jeder Kandidat y mit der Eingabe teilt. Liegt diese Zahl über dem Grenzwert, berechnet man erst dann die tatsächliche PED; liegt sie darunter, überspringt man das und spart viel teure Berechnung.
    Die so erhaltene Wortliste kann man dann gegen den bestehenden Index abfragen. Ich habe diesen Ansatz früher verwendet, als ich für https://dont.watch/ eine clientseitige JS-Fuzzy-Suchmaschine gebaut habe. Wenn man in den JS-Code schaut, sieht man, dass der invertierte Index und der komprimierte n-Gramm-Index direkt als JS-Datei ausgeliefert werden. Die eigentliche Suchmaschine besteht aus etwa 300 Zeilen JS ohne externe Abhängigkeiten und enthält nur sehr grundlegende Heuristiken zur Verbesserung der Suchergebnisse.

    • Um wie viel wächst bei diesem Ansatz die Indexgröße?