Relevante Ergebnisse trotz Tippfehlern: BM25 und Fuzzy Matching kombinieren
Viele Suchfunktionen setzen auf Teilstring-Suche, etwa mit LIKE '%query%' oder strings.Contains. Damit wird nur genau dieselbe Zeichenfolge gefunden: setings passt nicht zu „Open user settings“, und export pdf passt nicht zu „Export the current document as a PDF file“.
Eine bessere Suche muss zwei Probleme lösen: Relevanz und Tippfehlertoleranz. BM25 sortiert Ergebnisse danach, wie relevant ihre Wörter für die Suchanfrage sind, und Fuzzy Matching findet falsch geschriebene Wörter. Suchanfragen, die für dieselbe Idee andere Wörter verwenden, brauchen Synonyme oder semantische Suche. Das geht über diesen Beitrag hinaus.
Dieser Beitrag zeigt anhand eines kleinen Beispiels, wie sich die beiden Techniken ergänzen und welche Entscheidungen bei der Umsetzung die Ergebnisse am stärksten beeinflussen. Außerdem zeigt er, wie dieselbe Suche die Tools eines KI-Agenten auswählen kann.
Das Beispiel durchsucht eine Reihe von Befehlen eines Texteditors. Jeder Befehl hat einen internen Namen und eine kurze Beschreibung, und die Suche berücksichtigt beides. Da die Suche auf englischen Wörtern arbeitet, bleiben die Befehle und Suchanfragen in diesem Beitrag auf Englisch. Diese Befehle kommen im Beitrag vor:
ID | Interner Name | Beschreibung |
|---|---|---|
A | file.exportPDF | Export the current document as a PDF file |
B | file.exportMarkdown | Export the current document to Markdown |
C | view.colorTheme | Pick a color theme for the editor |
D | settings.open | Open user settings |
E | settings.keyboardShortcuts | Edit keyboard shortcuts |
F | file.openFile | Open a file from disk |
G | view.zoomIn | Make the text bigger |
Was ist BM25?
BM25 (Best Matching 25) ist eine Ranking-Funktion. Für eine Suchanfrage und eine Sammlung von Dokumenten vergibt sie jedem Dokument eine Punktzahl, die seine Relevanz für die Anfrage ausdrückt. Im Beispiel ist jeder Befehl ein Dokument. BM25 wurde in den 1990er-Jahren entwickelt und ist bis heute die Standard-Ranking-Funktion in Lucene und Elasticsearch.
BM25 vergleicht keinen Rohtext. Zuerst werden die Befehle und die Suchanfrage in Terme umgewandelt: vereinfachte Wörter, die sich leichter vergleichen lassen. Dieser Schritt heißt Tokenisierung. Im Beispiel
wird alles in Kleinbuchstaben umgewandelt,
werden interne Namen wie
exportPDFin „export“ und „pdf“ zerlegt,werden häufige Wörter wie „the“ oder „to“ entfernt,
werden Endungen wie „-ing“ oder „-s“ entfernt, sodass „exporting“, „exports“ und „export“ alle zu „export“ werden.
Die Beschreibung von B, „Export the current document to Markdown“, wird zu den Termen „export“, „current“, „document“ und „markdown“.
Die BM25-Formel beruht auf drei Prinzipien:
Seltene Terme zählen mehr. Ein Term, der in vielen Befehlen vorkommt, etwa „file“, sagt wenig über die Relevanz aus. Ein Term, der nur in einem vorkommt, etwa „pdf“ in A, ist ein starkes Signal. Diese Komponente heißt inverse Dokumenthäufigkeit (IDF).
Wiederholung bringt abnehmenden Nutzen. Ein Dokument, das einen Term fünfmal enthält, ist relevanter als eines, das ihn einmal enthält, aber nicht fünfmal so relevant. Der Parameter
k1, üblicherweise 1,2, steuert, wie schnell dieser Effekt gesättigt ist.Die Dokumentlänge wird normalisiert. Längere Texte enthalten mehr Terme und würden sonst häufiger passen. Der Parameter
b, üblicherweise 0,75, steuert die Stärke dieser Normalisierung.
Für jeden Term der Suchanfrage berechnet BM25 einen Wert pro Prinzip:
seltenheit = ln(1 + (N − n + 0.5) / (n + 0.5))
länge = 1 − b + b × (dokumentlänge / durchschnittliche dokumentlänge)
häufigkeit = f × (k1 + 1) / (f + k1 × länge)
termwert = seltenheit × häufigkeitN ist die Anzahl der Dokumente, n die Anzahl der Dokumente, die den Term enthalten, und f gibt an, wie oft der Term im Dokument vorkommt. Die Punktzahl eines Dokuments ist die Summe der Termwerte aller Terme der Suchanfrage. Ein Term, der im Dokument nicht vorkommt, hat f = 0 und trägt daher nichts bei.
Was ist Fuzzy Matching?
BM25 findet nur Terme, die in den Befehlen vorkommen. Ein falsch geschriebenes Wort wie setings kommt in keinem vor. Sind alle Wörter der Suchanfrage falsch geschrieben, findet BM25 also nichts. Hier hilft Fuzzy Matching: Es sucht nach Wörtern, die der Suchanfrage fast gleichen.
Ein gängiges Maß dafür, wie ähnlich sich zwei Wörter sind, ist die Levenshtein-Distanz: die kleinste Anzahl einzelner Buchstabenänderungen (einen Buchstaben hinzufügen, entfernen oder ersetzen), die nötig ist, um ein Wort in das andere umzuwandeln. Bei setings fehlt ein „t“ zu „settings“, die Distanz ist also 1.
Ein falscher Buchstabe wiegt in einem kurzen Wort schwerer als in einem langen. Deshalb wird die Distanz in eine Ähnlichkeit zwischen 0 und 1 umgerechnet, wobei 1 identisch bedeutet:
ähnlichkeit = 1 - distanz / länge des längeren wortesFür setings und „settings“ beträgt die Ähnlichkeit 1 − 1/8 = 0,875. Das Beispiel akzeptiert einen Befehl ab einer Ähnlichkeit von 0,75. Besteht die Suchanfrage aus mehreren Wörtern, wird für jedes davon das ähnlichste Wort im Befehl gesucht, und der Durchschnitt dieser Ähnlichkeiten muss 0,75 erreichen.
Warum beides kombinieren?
Jede Technik löst einen Fall, den die andere nicht lösen kann. Die Tabelle vergleicht Teilstring-Suche, BM25 und Fuzzy Matching anhand von vier Suchanfragen:
Suchanfrage | Sollte finden | Teilstring | BM25 | Fuzzy |
|---|---|---|---|---|
export pdf | A | die beiden Wörter stehen nicht nebeneinander | A | Nicht genutzt: BM25 hat es schon gefunden |
exporting | A, B | im Text steht export, nicht exporting | A, B: exporting wird zu export | Nicht genutzt: BM25 hat es schon gefunden |
theme color | C | die Wörter stehen in umgekehrter Reihenfolge | C: die Wortreihenfolge spielt keine Rolle | Nicht genutzt: BM25 hat es schon gefunden |
setings | D | Tippfehler | kein Befehl enthält setings | D, E: nah genug an settings |
Die beiden werden mit einer Regel kombiniert: Zuerst läuft BM25, und Fuzzy Matching läuft nur, wenn BM25 nichts findet. Fuzzy Matching akzeptiert auch Wörter, die der Suchanfrage nur ähneln, und liefert daher einige falsche Treffer. Liefe es bei jeder Suchanfrage, würden sich diese falschen Treffer unter die guten BM25-Ergebnisse mischen.
Die Regel hat ihren Preis. Bei open setings findet BM25 die Befehle, die „open“ enthalten, etwa D und F. Fuzzy Matching läuft deshalb nie, und der Tippfehler wird nicht korrigiert.
Entscheidungen, die die Ergebnisse beeinflussen
Namen stärker gewichten als Beschreibungen. Ein Treffer im internen Namen ist ein stärkeres Signal als ein Treffer in der Beschreibung. Wir zählen jeden Term im internen Namen doppelt.
Einen relativen Schwellenwert statt fester Top N verwenden. Eine feste Anzahl von Ergebnissen enthält schwache Treffer, wenn es einen klaren Gewinner gibt, und schneidet gute ab, wenn es viele gibt. Wir behalten nur Ergebnisse, die mindestens 50 % der besten Punktzahl erreichen, mit einem absoluten Minimum von 0,05, und normalisieren die Punktzahlen dann so, dass das beste Ergebnis 1,00 hat.
Die Anzahl der Ergebnisse begrenzen. Eine Suchanfrage, die fast alles findet, hilft niemandem. Wir geben höchstens 40 % der Befehle zurück, aufgerundet. Im Code unten ist dieser Anteil die Konstante
maxShare.Auf Gleitkommafehler achten. Wir berechnen die Obergrenze mit
ceil, und das Produkt kann leicht danebenliegen:0.07 * 100ergibt7.000000000000001, also liefertceil8 statt 7. Um das zu vermeiden, ziehen wir vor dem Runden ein kleines Epsilon (1e-9) ab.Gleichstände deterministisch auflösen. Ergebnisse mit derselben Punktzahl können sonst bei jedem Durchlauf in anderer Reihenfolge zurückkommen, was Tests instabil macht. Wir sortieren nach Punktzahl und dann nach internem Namen, damit die Reihenfolge fest bleibt.
Umsetzung
Wir haben das Beispiel als kleines Go-Programm geschrieben, das nur die Standardbibliothek verwendet. Die zentrale Suchfunktion wendet die Fallback-Regel, die Auflösung von Gleichständen und die Obergrenze an:
func (idx *Index) Search(query string) []Result {
results := idx.bm25(query)
if len(results) == 0 {
results = idx.fuzzy(query) // nur wenn BM25 nichts findet
}
// Deterministische Reihenfolge: zuerst Punktzahl, dann Name.
sort.SliceStable(results, func(i, j int) bool {
if results[i].Score != results[j].Score {
return results[i].Score > results[j].Score
}
return results[i].Command.Name < results[j].Command.Name
})
limit := int(math.Ceil(maxShare*float64(len(idx.docs)) - 1e-9))
if len(results) > limit {
results = results[:limit]
}
return results
}Ergebnisse für drei Suchanfragen, mit Punktzahlen, die so normalisiert sind, dass das beste Ergebnis 1,00 hat:
Suchanfrage | Ergebnisse |
|---|---|
exporting | B (1,00), A (0,96) |
export pdf | A (1,00) |
setings | E (0,88), D (0,88) |
Bei exporting enthalten A und B „export“ an denselben Stellen: im internen Namen und in der Beschreibung. Der Unterschied ist die Länge. Die Beschreibung von A endet mit „as a PDF file“ und ist damit länger als die von B mit „to Markdown“. Passen zwei Befehle auf dieselben Terme, gibt BM25 dem kürzeren eine höhere Punktzahl (das dritte Prinzip), deshalb liegt B knapp vor A. Bei export pdf enthält auch B „export“, aber seine Punktzahl liegt unter 50 % der Punktzahl von A, daher entfernt der relative Schwellenwert es. Bei setings erscheint E, weil sein interner Name „settings“ enthält. E und D haben dieselbe Punktzahl und werden deshalb nach internem Namen sortiert.
Denselben Ansatz nutzen wir, um die Tools unserer KI-Agenten auszuwählen. Ein Agent erhält mit jeder Anfrage den Namen und die Beschreibung jedes verfügbaren Tools. Je mehr Tools er hat, desto länger wird die Anfrage, und das kann die Auswahl des Modells weniger zuverlässig machen.
Ein Tool hat dieselbe Form wie ein Befehl. Deshalb indexieren wir Tools nach Name und Beschreibung, verwenden die Anfrage des Nutzers als Suchanfrage und schicken nur die ausgewählten Tools an das Modell:
func selectTools(idx *Index, all []Command, request string) []Command {
results := idx.Search(request)
if len(results) == 0 {
return all // nichts gefunden: das Modell sieht alle Tools
}
selected := make([]Command, len(results))
for i, r := range results {
selected[i] = r.Command
}
return selected
}Zum Testen behandeln wir die Editor-Befehle als Tools eines Agenten:
Anfrage | Ausgewählte Tools |
|---|---|
export the document as pdf and markdown | A, B |
open the settings and pick a theme | C, D |
markdwon | B, über den Fuzzy-Fallback |
do the same for the other one | keine, daher werden alle Tools geschickt |
Bei einem Agenten wiegen einige der Entscheidungen oben anders:
Ein fehlendes Tool kostet mehr als ein zusätzliches. Anfragen brauchen oft mehr als ein Tool, wie in den ersten beiden Beispielen. Das Modell entscheidet weiterhin, welche Tools es aufruft, und kann ein zusätzliches Tool also ignorieren. Ein fehlendes Tool ist schlimmer: Der Agent kann einen Teil der Aufgabe nicht erledigen. Deshalb behalten wir jedes Tool über dem relativen Schwellenwert statt nur des besten, während die Obergrenze die Auswahl klein hält.
Wenn nichts passt, alle Tools schicken. Folgenachrichten wie do the same for the other one enthalten keinen der Terme, auf die es ankommt, also findet die Suche nichts. Ohne Tools könnte der Agent nicht handeln, deshalb erhält das Modell alle: Die Anfrage wird länger, aber der Agent arbeitet weiter. Eine Möglichkeit, solche Fälle abzufangen, ist, die vorherige Nachricht zur Suchanfrage hinzuzufügen.
Beschreibungen sind Teil des Index. Die Suche kann ein Tool nur über die Wörter in seinem Namen und seiner Beschreibung finden. increase the font size wählt nichts aus, weil G als „Make the text bigger“ beschrieben ist. Mit „font“ in der Beschreibung wird G ausgewählt. Beschreibungen mit den Wörtern, die Nutzer verwenden, verbessern die Auswahl, und das Modell liest dieselben Beschreibungen, um zu entscheiden, welches Tool es aufruft.
Fazit
BM25 und Fuzzy Matching eignen sich gut für kleine und mittlere Sammlungen wie Befehle, Einstellungen, Produkte oder Dokumentationsseiten. Beide laufen im Arbeitsspeicher, brauchen keine externen Dienste und liefern deterministische Ergebnisse. Das macht sie leicht testbar.
Allerdings gibt es einige Grenzen:
Kein semantisches Verständnis. Eine Suche nach
enlargefindet G („Make the text bigger“) nicht, weil die beiden keine Terme gemeinsam haben. Synonyme und Absichten erfordern semantische Suche mit Embeddings, die sich in einer hybriden Suche mit BM25 kombinieren lässt.Begrenzte Skalierbarkeit. Der Fuzzy-Fallback vergleicht die Suchanfrage mit jedem Wort in jedem Befehl. Bei kleinen Sammlungen ist das kein Problem, mit wachsender Sammlung wird es aber langsamer.
Abstimmung der Parameter. Werte wie die 50-%-Grenze oder der Ähnlichkeitsschwellenwert von 0,75 hängen von den Daten ab und sollten anhand echter Suchanfragen von Nutzern überprüft werden.
Für größere Sammlungen bieten Engines wie die Volltextsuche von Postgres, Meilisearch und Elasticsearch ein Ranking nach Relevanz, und einige bieten auch Tippfehlertoleranz. Wer weiß, wie BM25 und Fuzzy Matching funktionieren, kann diese Engines leichter konfigurieren und besser verstehen, warum sie Ergebnisse in einer bestimmten Reihenfolge liefern.
