Eine einfache Suchmaschine bauen, die tatsächlich funktioniert

 (karboosx.net)
9 Punkte von GN⁺ 2025-11-18 | 1 Kommentare | Auf WhatsApp teilen
  • Implementiert eine Suchmaschinenarchitektur, die ohne externe Dienste funktioniert, unter Nutzung der bestehenden Datenbank, mit Fokus auf Tokenisierung, Gewichtung und Scoring
  • Die Kernidee ist, alle Texte zu tokenisieren und zu speichern und bei Suchanfragen Tokens auf dieselbe Weise abzugleichen, um die Relevanz zu berechnen
  • Durch die Kombination von Word-, Prefix- und N-Gram-Tokenizern werden exakte Treffer, Teiltreffer und Tippfehler gleichermaßen abgedeckt; jeder Tokenizer hat dabei ein eigenes Gewicht
  • Über ein Gewichtungssystem und einen SQL-basierten Scoring-Algorithmus werden Dokumentlänge, Token-Vielfalt und durchschnittliche Qualität gemeinsam bewertet
  • Die Struktur ist hoch skalierbar und transparent: Neue Tokenizer oder Dokumenttypen lassen sich hinzufügen, Gewichte anpassen und das Scoring frei verändern

Warum eine Suchmaschine selbst bauen?

  • Externe Dienste wie Elasticsearch oder Algolia sind leistungsstark, bringen aber den Aufwand mit sich, komplexe APIs zu erlernen und Infrastruktur zu betreiben
  • Wenn man einfach nur eine Suchfunktion braucht, die in die bestehende Datenbank integriert ist und sich leicht debuggen lässt, ist ein Eigenbau sinnvoll
  • Das Ziel ist eine einfache Suchmaschine, die ohne externe Abhängigkeiten relevante Ergebnisse liefert

Das Kernkonzept: Tokenisierung und Matching

  • Das Grundprinzip besteht darin, sämtliche Texte zu tokenisieren und zu speichern und bei der Suche auf dieselbe Weise Tokens zu erzeugen und abzugleichen
  • Im Indexierungs-Schritt wird der Inhalt in Tokens zerlegt und zusammen mit Gewichten gespeichert
  • Im Such-Schritt wird die Query genauso tokenisiert, passende Tokens werden gesucht und ein Score berechnet
  • Im Scoring-Schritt wird mithilfe der gespeicherten Gewichte ein Relevanzwert ermittelt

Entwurf des Datenbankschemas

  • Es werden zwei Tabellen verwendet: index_tokens und index_entries
    • index_tokens: speichert eindeutige Tokens und tokenizer-spezifische Gewichte
    • index_entries: verknüpft Tokens mit Dokumenten und speichert den finalen Score unter Berücksichtigung von Feld-, Dokument- und Tokenizer-Gewichten
  • Formel zur Berechnung des Endgewichts:
    field_weight × tokenizer_weight × ceil(sqrt(token_length))
  • Indizes werden für Dokumentabfragen, Token-Abfragen, feldbezogene Queries und Gewichtsfilter gesetzt

Das Tokenisierungssystem

  • WordTokenizer: trennt nach Wörtern, entfernt kurze Wörter, für exakte Treffer (Gewicht 20)
  • PrefixTokenizer: erzeugt Wortpräfixe, für Autocomplete und Teiltreffer (Gewicht 5)
  • NGramsTokenizer: erzeugt Zeichenkombinationen fester Länge, für Tippfehler und Teiltreffer (Gewicht 1)
  • Alle Tokenizer führen gemeinsam Kleinschreibung, Entfernen von Sonderzeichen und Normalisierung von Leerzeichen durch

Das Gewichtungssystem

  • Feldgewichte: bilden die Bedeutung von Titel, Textkörper, Keywords usw. ab
  • Tokenizer-Gewichte: Word > Prefix > N-Gram
  • Dokumentgewicht: wird aus den beiden Faktoren oben und der Tokenlänge berechnet
  • Mit der Funktion ceil(sqrt()) wird der Einfluss langer Tokens abgeschwächt; bei Bedarf kann dies durch logarithmische oder lineare Funktionen angepasst werden

Der Indexierungs-Service

  • Nur Dokumente, die IndexableDocumentInterface implementieren, können indexiert werden
  • Bei Erstellung oder Änderung eines Dokuments erfolgt die Indexierung über Event-Listener oder Befehle (app:index-document, app:reindex-documents)
  • Ablauf:
    • Vorhandenen Index entfernen und neue Tokens erzeugen
    • Für jedes Feld alle Tokenizer ausführen
    • Prüfen, ob ein Token existiert, und es andernfalls anlegen (findOrCreateToken)
    • Mit den berechneten Gewichten einen Batch-Insert in index_entries durchführen
  • Die Struktur ist auf Vermeidung von Duplikaten, bessere Performance und Updates ausgelegt

Der Such-Service

  • Die Query wird mit denselben Tokenizern verarbeitet, um dieselbe Token-Menge wie bei der Indexierung zu erhalten
  • Nach dem Entfernen von Duplikaten werden die Tokens nach Länge sortiert (lange Tokens zuerst) und auf maximal 300 begrenzt
  • Über eine SQL-Query werden Tokens und Dokumente gejoint sowie Relevanz-Scores berechnet und sortiert
  • Die Ergebnisse werden als SearchResult(documentId, score) zurückgegeben

Der Scoring-Algorithmus

  • Basisscore: SUM(sd.weight)
  • Korrektur für Token-Vielfalt: LOG(1 + COUNT(DISTINCT token_id))
  • Korrektur für durchschnittliches Gewicht: LOG(1 + AVG(weight))
  • Strafe für Dokumentlänge: 1 / (1 + LOG(1 + token_count))
  • Normalisierung: durch den Maximalwert teilen, um den Bereich 0–1 zu erhalten
  • Über einen Mindestfilter für Token-Gewichte (st2.weight >= ?) werden bedeutungslose Treffer mit geringem Gewicht entfernt

Verarbeitung der Ergebnisse

  • Suchergebnisse werden mit Dokument-ID und Score zurückgegeben und über ein Repository in die eigentlichen Dokumente umgewandelt
  • Mit der Funktion FIELD() werden Dokumente abgerufen, ohne die Reihenfolge der Suchergebnisse zu verlieren

Skalierbarkeit des Systems

  • Neue Tokenizer lassen sich durch Implementierung von TokenizerInterface hinzufügen
  • Neue Dokumenttypen können durch Implementierung von IndexableDocumentInterface registriert werden
  • Gewichte und Scoring-Logik lassen sich allein durch Anpassung des SQLs verändern

Fazit

  • Diese Struktur ist eine einfache, aber tatsächlich funktionierende Suchmaschine, die auch ohne externe Infrastruktur ausreichend Leistung bietet
  • Die Vorteile sind klare Logik, vollständige Kontrolle und leichtes Debugging
  • Sie unterstreicht, dass Code, den man selbst versteht und kontrolliert, oft wertvoller ist als ein komplexes System

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-11-18
Hacker-News-Kommentare

  • Die Grundidee der Suche ist einfach und ein interessantes Problemfeld.
    Aber die wirklich schwierigen Teile sind der Umgang mit großen Datenmengen und die Verarbeitung mehrdeutiger Suchanfragen.
    Ein DBMS-basierter Ansatz ist für kleine Websites in Ordnung, stößt aber bei der Größenordnung der englischen Wikipedia schnell an Grenzen.
    Als Einstieg ist das SeIRP e-book eine gute kostenlose Ressource.

    • Große Datenmengen sind natürlich schwierig, aber der Umgang mit mehrdeutigen Anfragen ist meiner Meinung nach ein Teilproblem der Frage: „Wie bestimmt man das relevanteste Ergebnis?“
      Besonders knifflig ist, dass es keine eindeutig richtige Antwort gibt.
      Google zeigt manchmal Werbung als „relevantestes Ergebnis“ an, daher ist Marginalia Search ein guter Kontrastfall.
      Mich würde interessieren, ob du dir schon einmal die TREC-Papers angesehen hast.
    • Heutzutage ist meiner Meinung nach eher die Vermeidung von SEO-Spam das größere Problem.
      Suchmaschinen müssen ständig gegen gegnerische Akteure kämpfen, die Werbeeinnahmen abschöpfen wollen.
      Das wird zu einem endlosen Katz-und-Maus-Spiel, bei dem die Qualitätsmetriken laufend geändert werden müssen, damit sie nicht ausgenutzt werden können.
    • Wenn man mit SQLite auf einem einzelnen Server (in der Größenordnung von etwa tausend Dollar) textzentrierte Geschäftsprozesse betreibt, würde mich interessieren, welche Größe eines Dokumentenspeichers praktisch handhabbar ist.
      Ich würde gern wissen, wie groß ein Korpus sein kann, den man durchsuchen kann, wenn man von etwa 5 Sekunden pro Query und 12 Queries pro Minute ausgeht.
    • Ich mag Marginalia Search wirklich sehr.
    • Die Schwierigkeit bei der Suche liegt meiner Meinung nach nicht nur in der Datenmenge, sondern auch in der Entscheidung, welche Ergebnisse zurückgegeben werden sollen.
      Es ist zum Beispiel schwer zu beurteilen, ob der Wiki-Artikel zu Gilligan’s Island oder ein Fan-Blog das „bessere“ Ergebnis ist.
      Wenn dann noch Manipulation des Rankings oder Keyword Stuffing dazukommen, wird es zu einer viel komplexeren Herausforderung als reine Skalierungsprobleme.

  • Suche ist wirklich schwer.
    Sogar Unternehmen mit enormen Ressourcen und technischer Stärke wie Apple, Microsoft und OpenAI haben Suche mit niedriger Qualität.
    Das ist nicht bloß ein technisches Problem.

    • Der Grund, warum die meisten Unternehmen Suche nicht gut umsetzen, ist, dass Unternehmenskultur und Entwicklungsweise mit der Entwicklung von Suchsystemen kollidieren.
      Um die Suchqualität zu verbessern, muss man Ranking-Parameter fein abstimmen, aber solche Arbeit lässt sich mit Verwaltungssystemen wie Sprints oder Jira nur schwer planen.
      Letztlich ist das ein Bereich, in dem Entwickler Vertrauen und Autonomie brauchen.
    • Bei manchen Unternehmen ist die Qualität aber einfach deshalb niedrig, weil Suche keine Priorität hat.
      In AI-Modelle werden Milliarden investiert, aber Webapps oder Suche sind zweitrangig, und entsprechend fällt das Ergebnis aus.

  • Ich habe vor etwa zehn Jahren einmal mit einem Kollegen, der in Suchmaschinendesign promovierte, zusammengearbeitet.
    Er sprach mit großer Leidenschaft über die Integration von Suche und Datenbanken, und ich habe dadurch viel gelernt.
    Irgendwann würde ich gern tief in das Innenleben von Apache Solr und Lucene eintauchen.

    • Ich kann auch stundenlang über mein Fachgebiet reden, aber es gibt nicht viele Menschen, die sich für die detaillierte Implementierung großer Systeme interessieren.

  • Früher gab es keine Open-Source-Suchlösungen, also musste man sie selbst bauen.
    Die Lehre aus dieser Erfahrung lautet: „Baue keine eigene Suchmaschine.“
    Zahlreiche Menschen haben sich über Jahre an diesem Problem abgearbeitet, und wenn man es selbst macht, landet man in einer endlosen Wartungshölle.
    Sobald Anforderungen wie „Bitte fügt eine Tippfehlerkorrektur hinzu“ oder „Nächstes Jahr sollten wir auch eine Taxonomie einbauen“ kommen, ist es vorbei.

  • Ich habe den Kurs zum Bau von Suchmaschinen, den Professor David Evans von der Virginia University gegeben hat, sehr genossen.
    Eine „klassische Suchmaschine“ selbst zu bauen, war ein ausgesprochen unterhaltsames Projekt.
    Siehe den Kurslink und die YouTube-Playlist.

    • Ich habe den Kurs auch besucht, und er war selbst für Programmieranfänger spannend und dicht gepackt.

  • Mich stört an den Suchmaschinen, die ich oft nutze, dass sie Abkürzungen oder Wörter mit 2 bis 3 Buchstaben ignorieren.
    Wenn bei einer Suche nach kurzen Wörtern wie „mp3“ oder „PHP“ einfach alles entfernt wird, ist das wirklich unpraktisch.

  • Toby Segarans Programming Collective Intelligence hat mich zu vielen Ideen rund um Suche, Empfehlungen und Klassifikatoren inspiriert.

    • Ich mochte das Buch auch, habe aber später gesehen, wie der Autor auf YouTube sagte, man solle es heute nicht mehr verwenden, weil es veraltet sei.
    • Es war wirklich ein gutes Buch, und ich frage mich, ob es eine aktualisierte Ausgabe auf dem Stand von 2025 gibt.

  • Interessanter Artikel.
    Ich frage mich, wie hoch der Grad an Tokenizer-Optimierung bei den populären Suchmaschinen ist.

  • Ich frage mich, wie skalierbar dieses System arbeiten wird.
    Elasticsearch zeigt auch jenseits der empfohlenen Größenordnung ziemlich beeindruckende Leistung.

  • Eine einfache Textsuchmaschine zu bauen, ist nicht schwer.
    Aber eine gute Suchmaschine zu bauen, ist eine ganz andere Geschichte.
    Es reicht nicht, einfach nur einen Algorithmus wie BM25 zu implementieren.
    Die meisten Unternehmen, die ich beraten habe, nutzten zunächst Eigenlösungen und sind am Ende doch zu Elasticsearch oder Opensearch gewechselt.
    Eine eigene Implementierung wirkt anfangs simpel, wird aber mit der Zeit durch Ranking-Probleme und Leistungsabfall komplex.
    Symptome wie „zu langsam“ oder „liefert seltsame Ergebnisse“ kehren dann immer wieder.
    Elasticsearch löst solche Probleme schon seit 10 Jahren, und heute ist es noch deutlich weiter entwickelt.
    Es heißt oft, es sei schwer zu konfigurieren, aber inzwischen wird vieles automatisch eingerichtet, und es gibt viele Managed Services.
    Es ist sogar leichter zu handhaben als Postgres.
    Letztlich ist die Optimierung des Index-Mappings das Entscheidende.
    Manche sagen zwar, solche erweiterten Funktionen brauche man nicht, aber in Wirklichkeit hängt die Qualität der Suche direkt vom Überleben des Geschäfts ab.
    Wenn man wirklich gute Suche will, muss man diese Komplexität letztlich in Kauf nehmen.

    • Ich nutze ebenfalls standardmäßig Elasticsearch.
      Aufkommende Alternativen wie SeekStorm, die in letzter Zeit oft auf HN erwähnt werden, wirken ebenfalls interessant, aber ich habe sie noch nicht in echten Produktionsfällen gesehen.
    • Ich stimme der Aussage zu, dass es „keine unnötigen Features“ gibt.
      Besonders der Tipp, dynamic mapping zu deaktivieren und unnötige Felder nicht zu indexieren, war nützlich.
    • Mich würde interessieren, was du von ManticoreSearch hältst.
      Soweit ich weiß, ist das Projekt älter als Lucene.