Fuzzy matching stelt u in staat om niet-exacte overeenkomsten van uw doel-item te identificeren. Het is de hoeksteen van veel zoekmachineframeworks en een van de belangrijkste redenen waarom u relevante zoekresultaten kunt krijgen, zelfs als u een typefout in uw zoekopdracht hebt of een andere werkwoordsvorm.
Zoals u zou verwachten, zijn er vele algoritmen die kunnen worden gebruikt voor fuzzy zoeken op tekst, maar vrijwel alle zoekmachine frameworks (inclusief bleve) gebruiken voornamelijk de Levenshtein Distance voor fuzzy string matching:
Levenshtein Distance
Ook bekend als Edit Distance, het is het aantal transformaties (verwijderingen, invoegingen, of vervangingen) dat nodig is om een bron string te transformeren naar de doel string. Bijvoorbeeld, als de doelterm “boek” is en de bron is “rug”, dan moet je de eerste “o” veranderen in “a” en de tweede “o” in “c”, wat ons een Levenshtein afstand geeft van 2.Edit Distance is zeer eenvoudig te implementeren, en het is een populaire uitdaging tijdens code interviews (U kunt Levenshtein implementaties in JavaScript, Kotlin, Java, en vele anderen hier vinden).
Daarnaast ondersteunen sommige frameworks ook de Damerau-Levenshtein afstand:
Damerau-Levenshtein afstand
Het is een uitbreiding op de Levenshtein afstand, die één extra bewerking toestaat: Transpositie van twee aangrenzende karakters:
Ex: TSAR naar STAR
Damerau-Levenshtein afstand = 1 (Het verwisselen van S en T posities kost slechts één operatie)
Levenshtein afstand = 2 (Vervang S door T en T door S)
Fuzzy matching en relevantie
Fuzzy matching heeft één groot neveneffect; het verknoeit de relevantie. Hoewel Damerau-Levenshtein een algoritme is dat rekening houdt met de meeste spelfouten van de gewone gebruiker, kan het ook een aanzienlijk aantal fout-positieven bevatten, vooral wanneer we een taal gebruiken met een gemiddelde van slechts 5 letters per woord, zoals het Engels. Dat is de reden waarom de meeste zoekmachine frameworks de voorkeur geven aan Levenshtein afstand. Laten we er eens een echt voorbeeld van bekijken:
Eerst gaan we deze film catalogus dataset gebruiken. Ik raad het ten zeerste aan als je wilt spelen met full-text zoeken. Laten we dan zoeken naar films met “boek” in de titel. Een eenvoudige code zou er als volgt uitzien:
|
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);
|
De bovenstaande code levert de volgende resultaten op:
|
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) The Book Thief
score: 4.826942606027416
Hit Locaties:
field:title
term:book
fragment:
—————————–
2) Het boek van Eli
score: 4.8269426027416
Hit Locations:
field:title
term:book
fragment:
—————————–
3) Het Boek des Levens
score: 4.826942606027416
Hit Locations:
field:title
term:book
fragment:
—————————–
4) Zwartboek
score: 4.826942606027416
Hit Locations:
field:title
term:book
fragment:
—————————–
5) The Jungle Book
score: 4.826942606027416
Hit Locations:
field:title
term:book
fragment:
—————————–
6) The Jungle Book 2
score: 3.9411821308689627
Hit Locations:
field:title
term:book
fragment:
—————————–
|
De resultaten zijn standaard hoofdletterongevoelig, maar u kunt dit gedrag eenvoudig veranderen door nieuwe indexen te maken met verschillende analyzers.
Nu, laten we een fuzzy matching-mogelijkheid aan onze query toevoegen door fuzziness in te stellen op 1 (Levenshtein distance 1), wat betekent dat “boek” en “look” dezelfde relevantie zullen hebben.
|
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);
|
En hier is het fuzzy zoekresultaat:
|
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) Haak
score: 1.1012248063242538
Hit Locations:
field:title
term:hook
fragment:
—————————–
2) Here Comes the Boom
score: 0.7786835148361213
Hit Locations:
field:title
term:boom
fragment:
—————————–
3) Look Who’s Talking Too
score: 0.7047266634351538
Hit Locations:
field:title
term:look
fragment:
—————————–
4) Look Who’s Talking
score: 0.7047266634351538
Hit Locations:
field:title
term:look
fragment:
—————————–
5) The Book Thief
score: 0.5228811753737184
Hit Locations:
field:title
term:book
fragment:
—————————–
6) The Book of Eli
score: 0.5228811753737184
Hit Locations:
field:title
term:book
fragment:
—————————–
|
Nu is de film “Hook” het allereerste zoekresultaat, wat misschien niet precies is wat de gebruiker verwacht bij een zoekopdracht naar “Book”.
Hoe valse positieven te minimaliseren bij fuzzy lookups
In een ideale wereld zouden gebruikers nooit typefouten maken terwijl ze naar iets zoeken. Dat is echter niet de wereld waarin we leven, en als je wilt dat je gebruikers een prettige ervaring hebben, moet je ten minste een bewerkingsafstand van 1 hanteren. Daarom is de echte vraag: Hoe kunnen we fuzzy string matching maken terwijl we het relevantieverlies minimaliseren?
We kunnen gebruik maken van een eigenschap van de meeste zoekmachine frameworks: Een match met een lagere edit-afstand zal meestal hoger scoren. Die eigenschap stelt ons in staat om die twee query’s met verschillende fuzziness niveaus te combineren tot een:
|
1
2
3
4
5
6
7
8
|
String indexName = “movies_index”;
String woord = “Boek”;
MatchQuery titleFuzzy = SearchQuery.match(woord).fuzziness(1).field(“titel”);
MatchQuery titleSimple = SearchQuery.match(woord).field(“titel”);
DisjunctionQuery ftsQuery = SearchQuery.disjuncts(titleSimple, titleFuzzy);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, ftsQuery).highlight().limit(20)); printResults(resultaat);
|
Hier is het resultaat van de fuzzy query hierboven:
|
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) The Book Thief
score: 2.398890092610849
Hit Locaties:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
2) Het boek van Eli
score: 2.398890092610849
trefferlocaties:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
3) The Book of Life
score: 2.398890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) Zwartboek
score: 2.398890092610849
Treflocaties:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
5) The Jungle Book
score: 2.398890092610849
hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
6) The Jungle Book 2
score: 1.958685557004688
hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
7) National Treasure: Book of Secrets
score: 1.6962714808368062
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
8) American Pie Presents: The Book of Love
score: 1.517191317611584
hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
9) Haak
score: 0,5052232518679681
Treflocaties:
field:title
term:hook
fragment:
—————————–
10) Here Comes the Boom
score: 0.357246781294941
Hit Locations:
field:title
term:boom
fragment:
—————————–
11) Look Who’s Talking Too
score: 0.32331663301992025
Hit Locations:
field:title
term:look
fragment:
—————————–
12) Look Who’s Talking
score: 0.32331663301992025
Hit Locations:
field:title
term:look
fragment:
—————————–
|
As you can see, this result is much closer to what the user might expect. Note that we are using a class called DisjunctionQuery now, disjunctions are an equivalent to the “OR” operator in SQL.
What else could we improve to reduce the negative side effect of a fuzzy matching algorithm? Laten we ons probleem opnieuw analyseren om te begrijpen of het verdere verbetering behoeft:
We weten al dat fuzzy lookups enkele onverwachte resultaten kunnen opleveren (bijv. Book -> Look, Hook). Maar een zoekopdracht op één term is meestal een vreselijke query, omdat die ons nauwelijks een hint geeft van wat de gebruiker precies probeert te bereiken.
Zelfs Google, dat aantoonbaar een van de meest hoogontwikkelde fuzzy zoekalgoritmen in gebruik heeft, weet niet precies wat ik zoek als ik zoek naar “tabel”:
Dus, wat is de gemiddelde lengte van trefwoorden in een zoekvraag? Om deze vraag te beantwoorden, laat ik een grafiek zien uit de presentatie van Rand Fishkin uit 2016. (Hij is een van de beroemdste goeroes in de SEO-wereld)
Volgens de bovenstaande grafiek heeft ~80% van de zoekopdrachten 2 of meer zoekwoorden, dus laten we proberen te zoeken naar de film “Black Book” met behulp van vaagheid 1:
|
1
2
3
4
5
6
|
String indexName = “movies_index”;
MatchQuery query = SearchQuery.match(“Zwartboek”).field(“titel”).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) Zwartboek
score: 0.6946442424065404
Hit Locaties:
field:title
term:book
fragment:
—————————–
field:title
term:black
fragment:
—————————–
2) Haak
score: 0,40139742528039857
treflocaties:
field:title
term:hook
fragment:
—————————–
3) Val het blok aan
score: 0.2838308365090324
Hit Locations:
field:title
term:block
fragment:
—————————–
4) Here Comes the Boom
score: 0.2838308365090324
Hit Locations:
field:title
term: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
Hit Locations:
field:title
term:blank
fragment:
—————————–
8) The Book Thief
score: 0.19059065534780495
Hit Locations:
field:title
term:book
fragment:
—————————–
9) Het boek van Eli
score: 0.19059065534780495
Hit Locations:
field:title
term:book
fragment:
—————————–
10) Het Boek des Levens
score: 0,19059065534780495
Hit Locations:
field:title
term:book
fragment:
—————————–
11) The Jungle Book
score: 0.19059065534780495
Hit Locations:
field:title
term:book
fragment:
—————————–
12) Back to the Future
score: 0.17061000968368
Hit Locations:
field:title
term:back
fragment:
—————————–
|
Niet slecht. We hebben de film die we zochten als eerste resultaat. Een disjunctie-query zou echter nog steeds een betere reeks resultaten opleveren.
Maar toch, het lijkt erop dat we hier een nieuwe leuke eigenschap hebben; het neveneffect van fuzziness matching neemt iets af naarmate het aantal trefwoorden toeneemt. Een zoekactie naar “Black Book” met fuzziness 1 kan nog steeds resultaten opleveren zoals back look of lack cook (sommige combinaties met edit distance 1), maar het is onwaarschijnlijk dat dit echte filmtitels zijn.
Een zoekactie naar “book eli” met fuzziness 2 zou het nog steeds als derde resultaat opleveren:
|
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
score: 0.030723793900031805
Hit Locaties:
field:title
term:wood
fragment:
—————————–
field:title
term:ed
fragment:
—————————–
2) Man of Tai Chi
score: 0.0271042761982626
Hit Locations:
field:title
term:chi
fragment:
—————————–
field:title
term:tai
fragment:
—————————–
3) The Book of Eli
score: 0.02608335441670756
Hit Locations:
field:title
term:eli
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) De goede leugen
score: 0.02439822770591834
trefferlocaties:
field:title
term:lie
fragment:
—————————–
field:title
term:good
fragment:
—————————–
|
Aangezien het gemiddelde Engelse woord 5 letters lang is, zou ik echter NIET aanraden een bewerkingsafstand van meer dan 2 te gebruiken, tenzij de gebruiker zoekt naar lange woorden die gemakkelijk verkeerd kunnen worden gespeld, zoals “Schwarzenegger” bijvoorbeeld (althans voor niet-Duitsers of niet-Oostenrijkers).
Conclusie
In dit artikel hebben we fuzziness matching besproken en hoe we de belangrijkste bijwerking ervan kunnen ondervangen zonder de relevantie in gevaar te brengen. Let wel, fuzzy matching is slechts een van de vele functies die je zou moeten benutten bij het implementeren van een relevante en gebruiksvriendelijke zoekopdracht. We gaan er een aantal bespreken tijdens deze serie: N-Grams, Stopwoorden, Steeming, Shingle, Elision. Etc.
Bekijk ook deel 1 en deel 2 van deze serie.
In de tussentijd, als je vragen hebt, tweet me dan op @deniswsrosa.
Author
- Denis Rosa, Developer Advocate, Couchbase –
