Fuzzy Matching ermöglicht es Ihnen, nicht exakte Übereinstimmungen Ihres Zielobjekts zu identifizieren. Es ist der Grundstein vieler Suchmaschinen-Frameworks und einer der Hauptgründe, warum Sie relevante Suchergebnisse erhalten können, selbst wenn Sie einen Tippfehler in Ihrer Anfrage oder eine andere Wortbedeutung haben.
Wie zu erwarten, gibt es viele Algorithmen, die für die unscharfe Suche nach Text verwendet werden können, aber praktisch alle Suchmaschinen-Frameworks (einschließlich bleve) verwenden hauptsächlich die Levenshtein-Distanz für den unscharfen Abgleich von Zeichenketten:
Levenshtein-Distanz
Auch bekannt als Editierdistanz, ist sie die Anzahl der Transformationen (Löschungen, Einfügungen oder Ersetzungen), die erforderlich sind, um eine Quellzeichenkette in die Zielzeichenkette zu verwandeln. Wenn der Zielbegriff beispielsweise „book“ und die Quelle „back“ ist, müssen Sie das erste „o“ in „a“ und das zweite „o“ in „c“ umwandeln, was eine Levenshtein-Distanz von 2 ergibt.Edit Distance ist sehr einfach zu implementieren und eine beliebte Herausforderung bei Code-Interviews (Levenshtein-Implementierungen in JavaScript, Kotlin, Java und vielen anderen finden Sie hier).
Zusätzlich unterstützen einige Frameworks auch die Damerau-Levenshtein-Distanz:
Damerau-Levenshtein-Distanz
Sie ist eine Erweiterung der Levenshtein-Distanz und erlaubt eine zusätzliche Operation: Transposition zweier benachbarter Zeichen:
Beispiel: TSAR zu STAR
Damerau-Levenshtein-Distanz = 1 (Vertauschen von S- und T-Positionen kostet nur eine Operation)
Levenshtein-Distanz = 2 (Ersetzen von S durch T und T durch S)
Fuzzy Matching und Relevanz
Fuzzy Matching hat einen großen Nebeneffekt: Es bringt die Relevanz durcheinander. Obwohl Damerau-Levenshtein ein Algorithmus ist, der die meisten Rechtschreibfehler des Benutzers berücksichtigt, kann er auch eine beträchtliche Anzahl falscher Positivmeldungen enthalten, insbesondere wenn wir eine Sprache mit durchschnittlich nur 5 Buchstaben pro Wort wie Englisch verwenden. Aus diesem Grund bevorzugen die meisten Suchmaschinen-Frameworks die Levenshtein-Distanz. Sehen wir uns ein echtes Beispiel dafür an:
Zunächst werden wir diesen Filmkatalog-Datensatz verwenden. Ich empfehle ihn sehr, wenn Sie mit der Volltextsuche spielen wollen. Dann lassen Sie uns nach Filmen mit „Buch“ im Titel suchen. Ein einfacher Code würde wie folgt aussehen:
|
1
2
3
4
5
6
|
String indexName = „movies_index“;
MatchQuery query = SearchQuery.match(„book“).field(„title“);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(6));
printResults(movies);
|
Der obige Code bringt die folgenden Ergebnisse:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
1) Der Bücherdieb
Note: 4.826942606027416
Trefferpunkte:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
2) Das Buch Eli
Treffer: 4.826942606027416
Trefferorte:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
3) Das Buch des Lebens
Treffer: 4.826942606027416
Trefferorte:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
4) Black Book
score: 4.826942606027416
Hit Locations:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
5) Das Dschungelbuch
Treffer: 4.826942606027416
Trefferorte:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
6) Das Dschungelbuch 2
Ergebnis: 3.9411821308689627
Fundstellen:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
|
Standardmäßig wird bei den Ergebnissen die Groß- und Kleinschreibung nicht berücksichtigt, aber Sie können dieses Verhalten leicht ändern, indem Sie neue Indizes mit verschiedenen Analysatoren erstellen.
Nun fügen wir unserer Abfrage eine Fuzzy-Matching-Fähigkeit hinzu, indem wir Fuzziness auf 1 (Levenshtein-Distanz 1) setzen, was bedeutet, dass „book“ und „look“ die gleiche Relevanz haben.
|
1
2
3
4
5
6
|
String indexName = „movies_index“;
MatchQuery query = SearchQuery.match(„book“).field(„title“).fuzziness(1);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(6));
printResults(movies);
|
Und hier ist das Fuzzy-Suchergebnis:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
1) Haken
punkten: 1.1012248063242538
Trefferstellen:
Feld:Titel
Begriff:Haken
Fragment:
—————————–
2) Here Comes the Boom
score: 0.7786835148361213
Hit Locations:
Feld:Titel
Begriff:Boom
Fragment:
—————————–
3) Look Who’s Talking Too
score: 0.7047266634351538
Hit Locations:
Feld:Titel
Begriff:Aussehen
Fragment:
—————————–
4) Look Who’s Talking
score: 0.7047266634351538
Hit Locations:
field:title
term:look
fragment:
—————————–
5) Der Bücherdieb
Punktzahl: 0.52288117537184
Trefferpunkte:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
6) Das Buch Eli
Punktzahl: 0.52288117537184
Trefferstellen:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
|
Nun ist der Film „Hook“ das allererste Suchergebnis, was vielleicht nicht genau das ist, was der Benutzer bei einer Suche nach „Buch“ erwartet.
Wie man falsch-positive Ergebnisse bei unscharfen Suchanfragen minimiert
In einer idealen Welt würden Benutzer niemals Tippfehler bei der Suche nach etwas machen. Das ist jedoch nicht die Welt, in der wir leben, und wenn Sie möchten, dass Ihre Benutzer eine angenehme Erfahrung haben, müssen Sie mindestens eine Editierdistanz von 1 handhaben. Daher lautet die eigentliche Frage: Wie können wir Fuzzy-String-Matching machen und gleichzeitig den Relevanzverlust minimieren?
Wir können uns eine Eigenschaft der meisten Suchmaschinen-Frameworks zunutze machen: Eine Übereinstimmung mit einer geringeren Edit-Distanz wird in der Regel höher bewertet. Diese Eigenschaft ermöglicht es uns, zwei Abfragen mit unterschiedlichen Unschärfegraden zu einer einzigen zu kombinieren:
|
1
2
3
4
5
6
7
8
|
String indexName = „movies_index“;
String word = „Buch“;
MatchQuery titleFuzzy = SearchQuery.match(word).fuzziness(1).field(„title“);
MatchQuery titleSimple = SearchQuery.match(word).field(„title“);
DisjunctionQuery ftsQuery = SearchQuery.disjuncts(titleSimple, titleFuzzy);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, ftsQuery).highlight().limit(20)); printResults(result);
|
Hier ist das Ergebnis der obigen Fuzzy-Abfrage:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
1) Der Bücherdieb
Partitur: 2.398890092610849
Trefferstellen:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
Feld:Titel
Begriff:Buch
Fragment:
—————————–
2) The Book of Eli
score: 2.398890092610849
Hit Locations:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
Feld:Titel
Begriff:Buch
Fragment:
—————————–
3) Das Buch des Lebens
score: 2.398890092610849
Hit Locations:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
Feld:Titel
Begriff:Buch
Fragment:
—————————–
4) Black Book
score: 2.398890092610849
Hit Locations:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
Feld:Titel
Begriff:Buch
Fragment:
—————————–
5) The Jungle Book
score: 2.398890092610849
Hit Locations:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
Feld:Titel
Begriff:Buch
Fragment:
—————————–
6) The Jungle Book 2
score: 1.958685557004688
Hit Locations:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
Feld:Titel
Begriff:Buch
Fragment:
—————————–
7) National Treasure: Book of Secrets
score: 1.6962714808368062
Hit Locations:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
Feld:Titel
Begriff:Buch
Fragment:
—————————–
8) American Pie Presents: The Book of Love
score: 1.517191317611584
Hit Locations:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
Feld:Titel
Begriff:Buch
Fragment:
—————————–
9) Hook
score: 0.5052232518679681
Hit Locations:
Feld:Titel
Begriff:Haken
Fragment:
—————————–
10) Here Comes the Boom
score: 0.357246781294941
Trefferstellen:
Feld:Titel
Begriff:Baum
Fragment:
—————————–
11) Look Who’s Talking Too
score: 0.32331663301992025
Hit Locations:
Feld:Titel
Begriff:Aussehen
Fragment:
—————————–
12) Look Who’s Talking
score: 0.32331663301992025
Hit Locations:
Feld:Titel
Begriff:Aussehen
Fragment:
—————————–
|
Wie Sie sehen, liegt dieses Ergebnis viel näher an dem, was der Benutzer erwarten könnte. Beachten Sie, dass wir jetzt eine Klasse namens DisjunctionQuery verwenden. Disjunktionen sind ein Äquivalent zum „OR“-Operator in SQL.
Was könnten wir noch verbessern, um den negativen Nebeneffekt eines Fuzzy-Matching-Algorithmus zu verringern? Lassen Sie uns unser Problem noch einmal analysieren, um zu verstehen, ob es weiterer Verbesserungen bedarf:
Wir wissen bereits, dass Fuzzy-Suchen einige unerwartete Ergebnisse liefern können (z.B. Buch -> Look, Hook). Eine Suche nach einem einzigen Begriff ist jedoch in der Regel eine schreckliche Abfrage, da sie uns kaum einen Hinweis darauf gibt, was genau der Benutzer zu erreichen versucht.
Selbst Google, das wohl einen der am weitesten entwickelten unscharfen Suchalgorithmen im Einsatz hat, weiß nicht genau, wonach ich suche, wenn ich nach „Tisch“ suche:
Wie lang sind also die Schlüsselwörter in einer Suchanfrage im Durchschnitt? Um diese Frage zu beantworten, zeige ich eine Grafik aus Rand Fishkins Präsentation von 2016. (Er ist einer der berühmtesten Gurus in der SEO-Welt)
Nach dem obigen Diagramm haben ~80% der Suchanfragen 2 oder mehr Keywords, also lassen Sie uns versuchen, mit Unschärfe 1 nach dem Film „Black Book“ zu suchen:
|
1
2
3
4
5
6
|
String indexName = „movies_index“;
MatchQuery query = SearchQuery.match(„Black Book“).field(„title“).fuzziness(1);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(12));
printResults(movies);
|
Result:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
1) Black Book
score: 0.6946442424065404
Trefferpunkte:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
Feld:Titel
Begriff:Schwarz
Fragment:
—————————–
2) Hook
score: 0.40139742528039857
Hit Locations:
Feld:Titel
Begriff:Haken
Fragment:
—————————–
3) Attack the Block
score: 0.2838308365090324
Hit Locations:
Feld:Titel
Begriff:Block
Fragment:
—————————–
4) Here Comes the Boom
score: 0.2838308365090324
Hit Locations:
Feld:Titel
Begriff:Boom
Fragment:
—————————–
5) Look Who’s Talking Too
score: 0.25687349813115684
Hit Locations:
field:title
term:look
fragment:
—————————–
6) Look Who’s Talking
score: 0.25687349813115684
Hit Locations:
field:title
term:look
fragment:
—————————–
7) Grosse Pointe Blank
score: 0.2317469073782136
Treffpunkte:
Feld:Titel
Begriff:Blank
Fragment:
—————————–
8) Der Bücherdieb
Treffer: 0.19059065534780495
Trefferorte:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
9) Das Buch Eli
Treffer: 0.19059065534780495
Trefferorte:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
10) Das Buch des Lebens
Punktzahl: 0.19059065534780495
Fundstellen:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
11) Das Dschungelbuch
Treffer: 0.19059065534780495
Trefferorte:
Feld:Titel
Begriff:Buch
Fragment:
—————————–
12) Zurück in die Zukunft
Treffer: 0.17061000968368
Trefferorte:
Feld:Titel
Begriff:Zurück
Fragment:
—————————–
|
Nicht schlecht. Wir haben den gesuchten Film als erstes Ergebnis erhalten. Allerdings würde eine Disjunktionsabfrage immer noch eine bessere Reihe von Ergebnissen liefern.
Aber trotzdem sieht es so aus, als hätten wir hier eine neue nette Eigenschaft; der Nebeneffekt der Unschärfeabstimmung nimmt leicht ab, wenn die Anzahl der Schlüsselwörter steigt. Eine Suche nach „Black Book“ mit Unschärfe 1 kann immer noch Ergebnisse wie „back look“ oder „lack cook“ bringen (einige Kombinationen mit Editierabstand 1), aber es ist unwahrscheinlich, dass dies echte Filmtitel sind.
Eine Suche nach „book eli“ mit Fuzziness 2 würde es immer noch als drittes Ergebnis bringen:
|
1
2
3
4
5
6
|
String indexName = „movies_index“;
MatchQuery query = SearchQuery.match(„book eli“).field(„title“).fuzziness(2);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(12));
printResults(movies);
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
1) Ed Wood
Ergebnis: 0.030723793900031805
Trefferstellen:
Feld:Titel
Begriff:Holz
Fragment:
—————————–
feld:titel
begriff:ed
fragment:
—————————–
2) Man of Tai Chi
score: 0.0271042761982626
Hit Locations:
Feld:Titel
Begriff:Chi
Fragment:
—————————–
feld:titel
begriff:tai
fragment:
—————————–
3) The Book of Eli
score: 0.02608335441670756
Hit Locations:
Feld:Titel
Begriff:eli
Fragment:
—————————–
Feld:Titel
Begriff:Buch
Fragment:
—————————–
4) The Good Lie
score: 0.02439822770591834
Hit Locations:
Feld:Titel
Begriff:Lüge
Fragment:
—————————–
Feld:Titel
Begriff:Gut
Fragment:
—————————–
|
Da jedoch das durchschnittliche englische Wort 5 Buchstaben lang ist, würde ich NICHT empfehlen, eine Edit-Distanz größer als 2 zu verwenden, es sei denn, der Benutzer sucht nach langen Wörtern, die leicht falsch zu schreiben sind, wie zum Beispiel „Schwarzenegger“ (zumindest für Nicht-Deutsche oder Nicht-Österreicher).
Abschluss
In diesem Artikel haben wir uns mit dem Fuzzy-Matching befasst und damit, wie man seine Hauptnebenwirkung überwinden kann, ohne seine Relevanz zu beeinträchtigen. Der unscharfe Abgleich ist jedoch nur eine der vielen Funktionen, die Sie bei der Implementierung einer relevanten und benutzerfreundlichen Suche nutzen sollten. In dieser Serie werden wir einige von ihnen besprechen: N-Gramme, Stoppwörter, Steeming, Shingle, Elision. Etc.
Schauen Sie sich auch Teil 1 und Teil 2 dieser Serie an.
Wenn Sie in der Zwischenzeit Fragen haben, tweeten Sie mich unter @deniswsrosa.
Autor
- Denis Rosa, Developer Advocate, Couchbase –
