Wie ich die Suche gelöst habe

Die meisten Apps haben irgendeine Art von Suche.

Sie hilft Nutzern, etwas Bestimmtes zu finden, wenn sie dessen genauen Namen nicht kennen. Zumindest definiere ich Suche im Rahmen dieses Artikels so.

Vorweg: Meine Lösung ist nichts Bahnbrechendes. Ich musste sie nur selbst wiederentdecken, weil es schwierig ist, optimierte Lösungen für bestimmte Anwendungsfälle zu finden. Im Internet fand ich nur allgemeine Lösungen, die für mich nicht funktionierten.
Ich möchte, dass alle Suchfunktionen in allen Apps besser werden. Deshalb veröffentliche ich hier meine Erkenntnisse.

Was ist das Problem mit den meisten Suchimplementierungen?

Man braucht eine Suche, weil der Nutzer etwas finden möchte. Deshalb kann man nicht erwarten, dass er die genauen Namen der Dinge, die er finden möchte, schon kennt.

Wenn ich zum Beispiel nach der Farbe “yellow” suche und mich mit “yelow” vertippe, erscheint die gewünschte Farbe nicht. Warum? Weil die Suche nicht sucht, sondern indexiert.

Wenn ich nach der Farbe “dark green” suche und sie aus irgendeinem Grund als “green dark” gespeichert ist, bekomme ich kein Ergebnis. Warum? Weil die Suche nicht berücksichtigt, wie Sprache funktioniert.

Wenn ich nach der Farbe “violet” suche, sie aber als “purple” gespeichert ist, bekomme ich kein Ergebnis. Warum? Weil es manchmal mehrere Wörter für dieselbe Sache gibt.

Welche gängigen Lösungen gibt es?

Vektorsuche

Vektorsuche kennst du vielleicht von Suchmaschinen wie Google. Sie konzentriert sich auf die semantische Bedeutung statt auf den Vergleich von Zeichen. Deshalb funktioniert sie gut, wenn du ein anderes Wort als das gespeicherte verwendest, sofern beide dasselbe beschreiben.

Eine Vektordatenbank speichert die Einträge in einem mehrdimensionalen Raum. In diesem Raum haben Begriffe, die nahe beieinanderliegen, eine ähnliche Bedeutung. Die Wörter “violet” und “purple” sollten sehr nahe beieinanderliegen, während “yellow” und “red” weit voneinander entfernt sein sollten.

Mit Tippfehlern kommt die Vektorsuche allerdings schlecht zurecht. Für eine Vektordatenbank unterscheidet sich der Begriff “yelow” stark vom Begriff “yellow”.

Vektorsuche

Selbst ausprobieren (semantischer Abgleich)

Tippe, um Farben zu suchen.

Fuzzy-Suche

Fuzzy-Suche ist eine gängige Lösung in Developer-Tools wie fzf oder Telescope, aber in anderen Zusammenhängen sehe ich sie selten.

Der Begriff “Fuzzy-Suche” ist nicht an einen bestimmten Algorithmus gebunden. Die häufigste Art der Fuzzy-Suche ist Subsequence-Matching, etwa mit Smith-Waterman oder ähnlichen Algorithmen zum Sequenzalignment.

Dabei werden Strings gefunden, in denen die eingegebenen Zeichen genau in der vorgegebenen Reihenfolge vorkommen. Dazwischen dürfen beliebig viele nicht eingegebene Zeichen als Lücken stehen.

Deshalb kannst du “yellow” finden, selbst wenn du “yelow” eingibst.

Strings, bei denen die eingegebenen Zeichen in einer anderen Reihenfolge stehen oder ein eingegebenes Zeichen im Zielstring vollständig fehlt, werden nicht gefunden. Wenn du also “yelllow” eingibst, passt das wegen des zusätzlichen “l” in der Mitte nicht zu “yellow”.

Fuzzy-Suche

Selbst ausprobieren (Subsequence-Matching)

Tippe, um Farben zu suchen.

Meine Lösung

Diese Methode verändert die übliche Fuzzy-Suche, indem sie die Suchanfrage und die Zielstrings an Whitespace trennt. Eine Anfrage wie “yel sun” wird beispielsweise zu den unabhängigen Wörtern “yel” und “sun”. Das System berechnet für jedes Wort einen Score gegenüber dem Zieleintrag und addiert diese Werte, zum Beispiel score("yel", item) + score("sun", item). Je ähnlicher das Suchwort dem Eintrag ist, desto höher ist der Score. So erreicht “yel sun” für “Sunbeam Yellow” einen hohen Wert.

Weil die Anfrage in Wörter aufgeteilt wird, spielt die Reihenfolge der Eingabe keine Rolle. Anschließend werden die Ergebnisse gefiltert, indem der Schwellenwert für den Gesamtscore auf 50 % des höchsten erreichten Scores gesetzt wird. Weder eine gewöhnliche Vektorsuche noch eine gewöhnliche Fuzzy-Suche würde diesen konkreten Fall abdecken. Dieser Algorithmus löst die üblichen Einschränkungen der Fuzzy-Suche. Für den Abgleich semantischer Bedeutung braucht man aber weiterhin eine Vektordatenbank.

Für die meisten Anwendungsfälle halte ich das für die beste Lösung. Sie ist schnell, genau und leicht zu implementieren. Außerdem lässt sie sich leicht an die eigenen Bedürfnisse anpassen. Du kannst beispielsweise eine größere oder kleinere Abweichung vom höchsten Score als Schwellenwert wählen, um die Empfindlichkeit der Suche anzupassen.

Magische Suche

Selbst ausprobieren (meine Lösung)

Tippe, um Farben zu suchen.

Für den Gesamtscore wird die Suchanfrage an Whitespace in unabhängige Wörter aufgeteilt. Der Algorithmus berechnet für jedes Wort einen Score gegenüber dem Zieleintrag und addiert diese Werte.

Den Score jedes einzelnen Wortes bestimmt der Smith-Waterman-Algorithmus für lokales Alignment.

Für ein Suchwort der Länge $m$ und einen Zieltext der Länge $n$ wird eine $(m+1) \times (n+1)$ -Matrix $H$ mit Nullen initialisiert. Jede Zelle $H_{i,j}$ bestimmt den maximalen Alignment-Score bis zum Zeichen $i$ im Wort und zum Zeichen $j$ im Text.

Der Score jeder Zelle wird mit dieser Rekursionsgleichung berechnet:

H_{i,j} = \max \begin{cases} 0 \\ H_{i-1, j-1} + S(a_i, b_j) \\ H_{i-1, j} + W \\ H_{i, j-1} + W \end{cases}

Dabei gilt:

$S(a_i, b_j)$ ist der Score für eine Übereinstimmung oder Abweichung. Er beträgt 2, wenn die Zeichen übereinstimmen, und -1, wenn sie nicht übereinstimmen.
$W$ ist der Punktabzug für eine Lücke und wird auf -1 gesetzt.
Die 0 setzt negative Scores zurück, sodass das lokale Alignment an jeder Stelle im Text neu beginnen kann.

Der endgültige Score des Wortes ist der höchste einzelne ganzzahlige Wert in der ausgefüllten Matrix $H$ .

func RunMagicSearch(query string, items []SearchItem) []SearchResult {
	// The total score is calculated by splitting the search query by whitespace into independent words.
	words := SplitByWhitespace(ToLower(query))
	var scored []SearchResult

	for _, item := range items {
		score := MagicScore(words, ToLower(item.Name))
		if score > 0 {
			scored = append(scored, SearchResult{Item: item, Score: score})
		}
	}

	SortByScoreDescending(scored)

	if len(scored) == 0 {
		return []SearchResult{}
	}

	// Results are then filtered by setting a threshold for the total score to 50% of the highest achieved score.
	topScore := scored[0].Score
	threshold := topScore * 0.5
	var filtered []SearchResult

	for _, result := range scored {
		if result.Score >= threshold {
			filtered = append(filtered, result)
		}
	}

	return filtered
}

func MagicScore(words []string, text string) float64 {
	totalScore := float64(0)

	// The algorithm calculates a score for each word against the target item and adds them together.
	for _, word := range words {
		totalScore += SmithWatermanScore(word, text)
	}

	return totalScore
}

Die gesamte Zeitkomplexität beträgt $O(K \cdot W \cdot m \cdot n + K \log K)$ , wobei:

$K$ : Anzahl der Einträge in der Liste.
$W$ : Anzahl der Wörter pro Anfrage.
$m$ : Länge eines Suchwortes.
$n$ : Länge eines Zieltextes.

Mögliche alternative Verfahren zur Bestimmung des Schwellenwerts:

Statistische Varianz: Ergebnisse ausschließen, die eine bestimmte Anzahl von Standardabweichungen unter dem mittleren Score der aktuellen Ergebnismenge liegen.
Größter Score-Abfall, Elbow-Methode: Scores absteigend sortieren und den Schwellenwert an der größten numerischen Lücke zwischen aufeinanderfolgenden Scores setzen.
Logarithmische Skalierung: Den Schwellenwert anhand einer nichtlinearen Kurve bestimmen, die von der Zeichenlänge der Anfrage oder ihrer Gesamtzahl an Wörtern abhängt.
1D-Clustering: Die zurückgegebenen Scores mit Jenks Natural Breaks oder K-Means in zwei getrennte Gruppen aufteilen, Treffer und Rauschen.