Fuzzy matching giver dig mulighed for at identificere ikke-eksakte matches af dit målemne. Det er grundstenen i mange søgemaskinerammer og en af hovedårsagerne til, at du kan få relevante søgeresultater, selv om du har en stavefejl i din forespørgsel eller en anden verbalform.
Som du måske kan forvente, er der mange algoritmer, der kan bruges til fuzzy søgning på tekst, men stort set alle søgemaskineframeworks (herunder bleve) bruger primært Levenshtein-distancen til fuzzy string matching:
Levenshtein-distance
Også kendt som Edit Distance, er det antallet af transformationer (sletninger, indsættelser eller substitutioner), der er nødvendige for at omdanne en kildestring til målstrengen. Hvis målbegrebet f.eks. er “book”, og kilden er “back”, skal du ændre det første “o” til “a” og det andet “o” til “c”, hvilket giver en Levenshtein-afstand på 2. Edit Distance er meget let at implementere, og det er en populær udfordring under kodeinterviews (du kan finde Levenshtein-implementeringer i JavaScript, Kotlin, Java og mange andre her).
Derudover understøtter nogle frameworks også Damerau-Levenshtein-distancen:
Damerau-Levenshtein-distancen
Det er en udvidelse af Levenshtein-distancen, der tillader en ekstra operation:
Ex: TSAR til STAR
Damerau-Levenshtein-afstand = 1 (ombytning af S- og T-positioner koster kun én operation)
Levenshtein-afstand = 2 (erstat S med T og T med S)
Fuzzy matching og relevans
Fuzzy matching har en stor bivirkning; det ødelægger relevansen. Selv om Damerau-Levenshtein er en algoritme, der tager højde for de fleste af de almindelige brugeres stavefejl, kan den også indeholde et betydeligt antal falske positive resultater, især når vi bruger et sprog med et gennemsnit på kun 5 bogstaver pr. ord, som f.eks. engelsk. Derfor foretrækker de fleste af søgemaskinerammerne at holde sig til Levenshtein-afstanden. Lad os se et reelt eksempel på det:
Først skal vi bruge dette filmkatalog-datasæt. Jeg kan varmt anbefale det, hvis du ønsker at lege med fuldtekstsøgning. Lad os derefter søge efter film med “bog” i titlen. En simpel kode ville se ud som følgende:
|
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);
|
Overstående kode vil give følgende resultater:
|
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
46
47
|
1) The Book Thief
score: 4.826942606027416
Hitsteder:
field:title
term:book
fragment:
—————————–
2) The Book of Eli
score: 4.82694242606027416
Hit Locations:
field:title
term:book
fragment:
—————————–
3) The Book of Life
score: 4.82694242606027416
Hit Locations:
field:title
term:book
fragment:
—————————–
4) Black Book
score: 4.82694242606027416
Hit Locations:
field:title
term:book
fragment:
—————————–
5) The Jungle Book
score: 4.82694242606027416
Hit Locations:
field:title
term:book
fragment:
—————————–
6) The Jungle Book 2
score: 3.9411821821308689627
Hit Locations:
field:title
term:book
fragment:
—————————–
|
Som standard er resultaterne ufølsomme over for store og små bogstaver, men du kan nemt ændre denne adfærd ved at oprette nye indekser med forskellige analysatorer.
Nu kan vi tilføje en fuzzy matching-funktion til vores forespørgsel ved at indstille fuzziness til 1 (Levenshtein-afstand 1), hvilket betyder, at “book” og “look” vil have den samme relevans.
|
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);
|
Og her er det fuzzy søgeresultat:
|
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
46
47
|
1) Hook
score: 1.1012248063242538
Rammeplaceringer:
field:title
term:hook
fragment:
—————————–
2) Here Comes the Boom
score: 0.778683535148361213
Hit Locations:
field:title
term:boom
fragment:
—————————–
3) Look Who’s Talking Too
score: 0.70474726666634351538
Hit Locations:
field:title
term:look
fragment:
—————————–
4) Se, hvem der taler
score: 0.704747266634351538
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 er filmen “Hook” det allerførste søgeresultat, hvilket måske ikke er præcis det, brugeren forventer i en søgning efter “Book”.
Sådan minimerer man falske positive resultater under fuzzy opslag
I en ideel verden ville brugerne aldrig lave tastefejl, når de søger efter noget. Det er imidlertid ikke den verden, vi lever i, og hvis du ønsker, at dine brugere skal have en behagelig oplevelse, er du nødt til at håndtere mindst en redigeringsafstand på 1. Derfor er det egentlige spørgsmål: Hvordan kan vi lave fuzzy strengmatchning og samtidig minimere relevancetabet?
Vi kan drage fordel af en egenskab ved de fleste søgemaskineframeworks: Et match med en lavere redigeringsafstand vil normalt score højere. Denne egenskab gør det muligt for os at kombinere disse to forespørgsler med forskellige fuzziness-niveauer til én:
|
1
2
3
3
4
5
6
7
8
|
String indexName = “movies_index”;
String word = “Book”;
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);
|
Her er resultatet af den fuzzy forespørgsel ovenfor:
|
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
Hitsteder:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
2) The Book of Eli
score: 2.398890090092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
3) The Book of Life
score: 2.398890090092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) Black Book
score: 2.398890092610849
Hit Locations:
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.69627141480836808062
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
8) American Pie Presents: The Book of Love
score: 1.517191311317611584
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
9) Hook
score: 0.5052232518679681
Hit Locations:
field:title
term:hook
fragment:
—————————–
10) Here Comes the Boom
score:
0.357246781294941
Hit Locations:
field:title
term:tree
fragment:
—————————–
11) Se, hvem der også taler
score: 0.3233166333301992025
Hit Locations:
field:title
term:look
fragment:
—————————–
12) Se, hvem der taler
score: 0.3233166333301992025
Hit Locations:
field:title
term:look
fragment:
—————————–
|
Som du kan se, er dette resultat meget tættere på det, som brugeren kan forvente. Bemærk, at vi bruger en klasse kaldet DisjunctionQuery nu, disjunktioner svarer til “OR”-operatoren i SQL.
Hvad kan vi ellers forbedre for at reducere den negative bivirkning af en fuzzy matching-algoritme? Lad os analysere vores problem igen for at forstå, om det har brug for yderligere forbedringer:
Vi ved allerede, at fuzzy opslag kan give nogle uventede resultater (f.eks. Book -> Look, Hook). Men en søgning med et enkelt begreb er normalt en forfærdelig forespørgsel, da den knap nok giver os et hint om, hvad brugeren præcist forsøger at opnå.
Selv Google, som vel nok har en af de mest udviklede fuzzy søgealgoritmer, der er i brug, ved ikke præcis, hvad jeg leder efter, når jeg søger efter “bord”:
Så, hvad er den gennemsnitlige længde af nøgleord i en søgeforespørgsel? For at besvare dette spørgsmål vil jeg vise en graf fra Rand Fishkins præsentation fra 2016. (Han er en af de mest berømte guruer i SEO-verdenen)
Ifølge grafen ovenfor har ~80% af søgeforespørgslerne 2 eller flere søgeord, så lad os prøve at søge efter filmen “Black Book” ved hjælp af fuzziness 1:
|
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) Sort bog
score: 0.69464424242406565404
Rammeplaceringer:
field:title
term:book
fragment:
—————————–
field:title
term:black
fragment:
—————————–
2) Hook
score: 0.4013974252803939857
Hit Locations:
field:title
term:hook
fragment:
—————————–
3) Angrib blokken
score: 0.283830308365090324
Hit Locations:
field:title
term:block
fragment:
—————————–
4) Here Comes the Boom
score: 0.283830308365090324
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.231746469073782136
Hit Locations:
field:title
term:blank
fragment:
—————————–
8) The Book Thief
score: 0.19059065534780495
Hit Locations:
field:title
term:book
fragment:
—————————–
9) The Book of Eli
score: 0.19059065534780495
Hit Locations:
field:title
term:book
fragment:
—————————–
10) The Book of Life
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:
—————————–
|
Nok dårligt. Vi fik den film, vi søgte efter, som det første resultat. En disjunktionssøgning ville dog stadig give et bedre sæt resultater.
Men alligevel ser det ud til, at vi har en ny fin egenskab her; bivirkningen af fuzziness matching aftager en smule, når antallet af nøgleord stiger. En søgning efter “Black Book” med fuzziness 1 kan stadig give resultater som back look eller lack cook (nogle kombinationer med edit distance 1), men det er usandsynligt, at disse er rigtige filmtitler.
En søgning efter “book eli” med fuzziness 2 vil stadig give det som tredje resultat:
|
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
46
47
|
1) Ed Wood
score: 0.03072379393900031805
Hitplaceringer:
field:title
term:wood
fragment:
—————————–
field:title
term:ed
fragment:
—————————–
2) Man of Tai Chi
score: 0.027104276198262626
Hit Locations:
Hit Locations:
field:title
term:chi
fragment:
—————————–
field:title
term:tai
fragment:
—————————–
3) The Book of Eli
score: 0.0260833544167070756
Hit Locations:
field:title
term:eli
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) The Good Lie
score: 0.02439822770591834
Hit Locations:
field:title
term:lie
fragment:
—————————–
field:title
term:good
fragment:
—————————–
|
Men da det gennemsnitlige engelske ord er 5 bogstaver langt, vil jeg IKKE anbefale at bruge en redigeringsafstand større end 2, medmindre brugeren søger efter lange ord, der er lette at stave forkert, som f.eks. “Schwarzenegger” (i det mindste for ikke-tyskere eller ikke-østrigere).
Slutning
I denne artikel har vi diskuteret fuzziness matching, og hvordan man kan overvinde dens vigtigste bivirkning uden at rode med relevansen. Husk på, at fuzzy matching blot er en af de mange funktioner, som du bør drage fordel af, når du implementerer en relevant og brugervenlig søgning. Vi vil diskutere nogle af dem i løbet af denne serie: N-Grams, Stopwords, Steeming, Shingle, Elision. Etc.
Kig også på del 1 og del 2 af denne serie.
I mellemtiden, hvis du har spørgsmål, kan du tweete mig på @deniswsrosa.
Author
- Denis Rosa, Developer Advocate, Couchbase –
