Eine Suchmaschine in 80 Zeilen Python

Eine in Python geschriebene Suchmaschine mit 80 Zeilen

• Im vergangenen September begann der Autor als Search Data Scientist bei Wallapop und arbeitet dort mit der Open-Source-Suchmaschine Solr.
• Um die Grundprinzipien von Suchmaschinen zu verstehen, entschied er sich, mit Python von Grund auf eine Suchmaschine zu bauen.
• Das Ziel ist, die „Auffindbarkeitskrise kleiner Websites“ zu lösen und kleine Websites, die sich mit Suchmaschinen wie Google nicht finden lassen, wieder groß zu machen.
• Dieser Artikel führt durch den Prozess, mit Python eine Suchmaschine zu bauen; der gesamte Code ist im GitHub-Repository microsearch zu finden.
• Die implementierte Suchmaschine ist keine produktionsreife Suchmaschine, sondern ein nutzbares Spielzeugbeispiel, das zeigt, wie Suchmaschinen intern funktionieren.

microsearch

• Es wird betrachtet, aus welchen Bausteinen microsearch besteht und wie jeder davon erstellt wurde: (1) Crawler, (2) invertierter Index, (3) Ranking, (4) Interface.

Crawler

• Der erste Schritt beim Bau einer Suchmaschine besteht darin, die zu durchsuchenden Daten zu beschaffen.
• Mit der Idee, ein „lokales Google“ zu bauen, wurde die Suchmaschine mit Daten aus den Blogs erstellt, denen der Autor folgt.
• Das Crawling umfasst das Herunterladen und Aufbereiten aller Beiträge aus einer bestimmten Blogliste.
• Um es zu beschleunigen, wurde die Python-Bibliothek asyncio verwendet, wodurch sich die Crawling-Zeit von 20 Minuten auf 20 Sekunden verkürzte.
• Verwendet wurden 642 RSS-Feeds; davon sind etwa 100 häufig gelesene Blogs, die übrigen 500 stammen aus dem Blogprojekt surprisetalk.

Invertierter Index

• Ein invertierter Index ist eine Datenstruktur, die Keywords auf Dokumente abbildet und es erleichtert, Dokumente zu finden, in denen ein bestimmtes Wort vorkommt.
• Wenn ein Nutzer eine Suchanfrage stellt, wird der invertierte Index verwendet, um alle Dokumente zu finden, die zu den Keywords der Anfrage passen.
• Die Logik des invertierten Indexes ist in einer Klasse namens SearchEngine definiert und wird durch die Initialisierung von zwei Dictionaries umgesetzt.

Ranking

• Wenn es für eine gegebene Anfrage eine Menge passender Dokumente gibt, braucht man eine Methode, um diese zu sortieren.
• Die bekannteste Ranking-Methode ist Googles PageRank, aber es gibt auch andere Optionen wie BM25, das Dokumente auf Basis ihres Inhalts bewertet.
• Es werden die fehlenden Teile der Klasse SearchEngine implementiert, einschließlich der Methode zur Berechnung des BM25-Scores.

Interface

• Nachdem die Suchmaschine gebaut wurde, wollte der Autor sie in irgendeiner Form veröffentlichen.
• Dazu wurde eine FastAPI-App erstellt, die einen Endpoint zum Bereitstellen der Suchmaschine anbietet und eine einfache Webseite rendert, auf der gesucht werden kann.
• Damit die Ausgabe leicht lesbar bleibt, wurde entschieden, nur die Top-N-URLs auszuwählen.

Fehlende Funktionen

• Leser, die häufig mit Suchmaschinen arbeiten, werden feststellen, dass in der Implementierung viele Funktionen fehlen.
• Es fehlen unter anderem Query-Operatoren, n-Gram-Indexierung, Query- oder Dokumenterweiterung sowie die Möglichkeit, Crawling und Indexierung gleichzeitig auszuführen.

Fazit

• Durch dieses Projekt gewann der Autor ein besseres Verständnis dafür, wie Solr intern funktioniert, und lernte die Vorzüge von asynchronem Code kennen.
• Als nächsten Schritt beim Bau einer persönlichen Suchmaschine plant er, eine semantische Suche in die Suchmaschine zu integrieren.

Meinung von GN⁺

• Das Wichtigste an diesem Artikel ist, dass Einzelpersonen selbst eine Suchmaschine bauen können, um die Auffindbarkeit kleiner Websites zu verbessern.
• Die Erfahrung, mit Python und Open-Source-Bibliotheken eine Suchmaschine mit komplexen Funktionen in vereinfachter Form umzusetzen, kann auch Einsteigerinnen und Einsteiger im Software Engineering inspirieren.
• Indem der Artikel anhand eines praktischen Beispiels die Effizienz asynchroner Programmierung und die Bedeutung von Datenstrukturen zeigt, bietet er sowohl technische Einblicke als auch eine praktische Lerngelegenheit.

[GN⁺]

Hacker-News-Kommentare

• Entwicklung einer BM25-Suchmaschine mit Pandas

  • Der Entwickler arbeitet an einer schnellen BM25-Suchmaschine, die in Pandas läuft.
  • Der Grund für die Nutzung von Pandas ist, dass sich damit neben dem BM25-Algorithmus auch andere Faktoren wie Aktualität und Popularität leicht kombinieren lassen.
  • Beim Phrase-Matching gibt es viele Sonderfälle, und es ist wichtig, Positionsinformationen mit möglichst wenig Speicherverbrauch zu komprimieren.

• Code-Review: Klasse SearchEngine

  • Es ist unklar, was die Parameter k1 und b bedeuten, und der Code enthält überhaupt keine Kommentare.
  • Vermutlich verwendet _documents URLs als Schlüssel und den Inhalt der jeweiligen URL als Wert.
  • Schade, dass der Code nicht gut dokumentiert ist. Mit guter Dokumentation hätte er als Lernmaterial zum Aufbau einer Suchmaschine nützlich sein können.

• Die Komplexität von Suchmaschinen

  • Die Hauptschwierigkeit bei Suchmaschinen besteht darin, mit der Datenmenge umzugehen.
  • Die Logik selbst ist überraschend einfach, und das Projekt ist erfolgreich, weil es die meisten unnötigen Teile entfernt.
  • Wichtig ist nicht, die Suchmaschine größer zu machen, sondern die Daten kleiner zu machen oder das Signal-Rausch-Verhältnis zu erhöhen.

• Meinungen zur Zeilenzahl von Code

  • Es wird infrage gestellt, welchen Sinn es hat, bei Nutzung externer Abhängigkeiten mit der Zeilenzahl des Codes zu prahlen.
  • Es gibt zwar keine SI-Einheit für eine Codebasis, aber man sollte die kognitive Belastung irgendwie messen.

• Scherz über eine Formulierung im Code

  • Beim Ausdruck chunk for chunk in chunks if chunk im Code fällt jemandem ein Witz über einen Holzfäller ein.

• Beispielcode für eine Empfehlungsmaschine

  • Es wird Code für eine Empfehlungsmaschine mit weniger als 20 Zeilen Python bereitgestellt, die zusammen mit einer Suchmaschine verwendet werden kann.
  • Sie erzeugt Empfehlungen auf Basis der in Sitzungslogs angeklickten URLs.
  • Wenn man die im Log eingegebenen Suchanfragen mit den angeklickten URLs kombiniert, kann man auch Vorschläge zur Rechtschreibkorrektur erhalten.

• Leistungsvergleich von Parsing-Bibliotheken

  • Es wird erwähnt, dass lxml.html und lxml.html.clean deutlich schneller sein können als BeautifulSoup.

• Ratschläge zur Verwendung von Keywords

  • Um die Qualität englischer Suchergebnisse zu verbessern, wird empfohlen, statt 1-Gramm lieber 2-Gramm und 3-Gramm zu verwenden.
  • N-Gramme helfen dabei, den Kontext zu erhalten.

• Meinung zu einem lehrreichen Projekt

  • Das Projekt ist sehr cool und lehrreich, aber es wird davon abgeraten, es tatsächlich produktiv einzusetzen.
  • Für größere Projekte mit einigen Zehntausend Dokumenten ist die Verwendung von FTS5 in SQLite die richtige Lösung.

• Zweifel an Python für die Verarbeitung großer Datenmengen

  • Es wird infrage gestellt, ob es wirklich eine gute Idee ist, Python, also eine langsame Sprache, für Aufgaben zu verwenden, die große Datenmengen schnell verarbeiten müssen.