Fuzzy matchning gör det möjligt att identifiera icke-exakta matchningar av ditt målobjekt. Det är grundstenen i många ramverk för sökmotorer och en av huvudanledningarna till att du kan få relevanta sökresultat även om du har ett stavfel i din sökfråga eller ett annat verbalt tempus.
Som man kan förvänta sig finns det många algoritmer som kan användas för fuzzy sökning på text, men i stort sett alla sökmotorramverk (inklusive bleve) använder främst Levenshtein-distansen för fuzzy strängmatchning:
Levenshtein-distans
Också känd som Edit Distance, är det antalet omvandlingar (strykningar, infogningar eller substitutioner) som krävs för att omvandla en källsträng till målsträngen. Om till exempel måltermen är ”book” och källan är ”back” måste du ändra det första ”o” till ”a” och det andra ”o” till ”c”, vilket ger oss ett Levenshtein-avstånd på 2. Edit Distance är mycket lätt att implementera och är en populär utmaning under kodintervjuer (du kan hitta Levenshtein-implementationer i JavaScript, Kotlin, Java och många andra här).
Det finns även stöd för Damerau-Levenshtein-distansen i vissa ramverk:
Damerau-Levenshtein-distans
Det är en utvidgning av Levenshtein-distansen som tillåter en extra operation: Omställning av två intilliggande tecken:
Ex: TSAR till STAR
Damerau-Levenshtein distans = 1 (Byte av S- och T-positioner kostar bara en operation)
Levenshtein distans = 2 (Ersätt S med T och T med S)
Fuzzy matchning och relevans
Fuzzy matchning har en stor sidoeffekt; det ställer till det med relevansen. Även om Damerau-Levenshtein är en algoritm som tar hänsyn till de flesta av den vanliga användarens felstavningar kan den också innehålla ett betydande antal falska positiva, särskilt när vi använder ett språk med i genomsnitt bara 5 bokstäver per ord, som till exempel engelska. Det är därför som de flesta ramverk för sökmotorer föredrar att hålla sig till Levenshtein-avståndet. Låt oss se ett verkligt exempel på det:
Först ska vi använda det här filmkatalog-dataset. Jag rekommenderar den starkt om du vill leka med fulltextsökning. Låt oss sedan söka efter filmer med ”book” i titeln. En enkel kod skulle se ut på följande sätt:
|
1
2
3
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);
|
Koden ovan ger följande resultat:
|
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
poäng: 4.826942606027416
Träffpunkter:
field:title
term:book
fragment:
—————————–
2) The Book of Eli
score: 4.826942606027416
Sökresultat:
field:title
term:book
fragment:
—————————–
3) Livets bok
poäng: 4.826942606027416
Träffpunkter:
field:title
term:book
fragment:
—————————–
4) Black Book
poäng: 4.826942606027416
Träffpunkter:
field:title
term:book
fragment:
—————————–
5) Djungelboken
poäng: 4.826942606027416
Träffpunkter:
field:title
term:book
fragment:
—————————–
6) Djungelboken 2
poäng: 3.9411821821308689627
Träffpunkter:
field:title
term:book
fragment:
—————————–
|
Som standard är resultaten okänsliga för stora och små bokstäver, men du kan enkelt ändra detta beteende genom att skapa nya index med olika analysatorer.
Nu lägger vi till en fuzzy matchningsfunktion till vår fråga genom att ställa in fuzziness som 1 (Levenshtein distans 1), vilket innebär att ”book” och ”look” har samma 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);
|
Och här är det luddiga sökresultatet:
|
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) Hook
poäng: 1.1012248063242538
Träffpunkter:
field:title
term:hook
fragment:
—————————–
2) Here Comes the Boom
poäng: 0.778683535148361213
Träffpunkter:
field:title
term:boom
fragment:
—————————–
3) Look Who’s Talking Too
poäng: 0.704747266634351538
Träffpunkter:
field:title
term:look
fragment:
—————————–
4) Titta vem som pratar
poäng: 0.704747266634351538
Träffpunkter:
field:title
term:look
fragment:
—————————–
5) The Book Thief
poäng: 0.52288117537184
Träffpunkter:
field:title
term:book
fragment:
—————————–
6) The Book of Eli
poäng: 0.52288117537184
Träffpunkter:
field:title
term:book
fragment:
—————————–
|
Nu är filmen ”Hook” det allra första sökresultatet, vilket kanske inte är exakt vad användaren förväntar sig när han eller hon söker efter ”Book”.
Hur man minimerar falska positiva resultat vid suddiga sökningar
I en idealisk värld skulle användarna aldrig göra några stavfel när de söker efter något. Det är dock inte den värld vi lever i, och om du vill att dina användare ska få en trevlig upplevelse måste du hantera åtminstone ett redigeringsavstånd på 1. Därför är den verkliga frågan: Hur kan vi göra fuzzy strängmatchning samtidigt som vi minimerar relevansförlusten?
Vi kan dra nytta av en egenskap hos de flesta ramverk för sökmotorer: En matchning med ett lägre redigeringsavstånd får vanligtvis högre poäng. Den egenskapen gör det möjligt för oss att kombinera dessa två förfrågningar med olika fuzziness-nivåer till en:
|
1
2
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);
|
Här är resultatet av den oklara frågan ovan:
|
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
poäng: 2.398890092610849
Träffpunkter:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
2) The Book of Eli
poäng: 2.398890092610849
träffpunkter:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
3) Livets bok
poäng: 2.398890092610849
träffpunkter:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) Black Book
poäng: 2.398890092610849
träffplatser:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
5) Djungelboken
poäng: 2.398890092610849
träffpunkter:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
6) Djungelboken 2
poäng: 1.958685557004688
träffpunkter:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
7) National Treasure: Book of Secrets
poäng: 1.696271480836808062
träffpunkter:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
8) American Pie Presents: The Book of Love
Poäng: 1.517191317611584
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
9) Hook
poäng: 0.5052232518679681
Träffpunkter:
field:title
term:hook
fragment:
—————————–
10) Here Comes the Boom
poäng: 0.357246781294941
Träffpunkter:
field:title
term:tree
fragment:
—————————–
11) Titta vem som pratar också
poäng: 0.3233166333301992025
Platser för träff:
field:title
term:look
fragment:
—————————–
12) Titta vem som pratar
poäng: 0.3233166333301992025
Träffpunkter:
field:title
term:look
fragment:
—————————–
|
Som du kan se är detta resultat mycket närmare vad användaren kan förvänta sig. Observera att vi använder en klass som heter DisjunctionQuery nu, disjunktioner är en motsvarighet till ”OR”-operatorn i SQL.
Vad mer kan vi förbättra för att minska den negativa bieffekten av en fuzzy matchningsalgoritm? Låt oss analysera vårt problem på nytt för att förstå om det behöver förbättras ytterligare:
Vi vet redan att fuzzy lookups kan ge oväntade resultat (t.ex. Book -> Look, Hook). Men en sökning med en enda term är vanligtvis en fruktansvärd fråga, eftersom den knappt ger oss en antydan om vad exakt användaren försöker åstadkomma.
Även Google, som utan tvekan har en av de mest utvecklade fuzzy-sökalgoritmerna som används, vet inte exakt vad jag letar efter när jag söker efter ”table”:
Så, vad är den genomsnittliga längden på nyckelord i en sökfråga? För att besvara den frågan kommer jag att visa en graf från Rand Fishkins presentation från 2016. (Han är en av de mest kända gurus i SEO-världen)
Enligt grafen ovan har ~80 % av sökfrågorna 2 eller fler nyckelord, så låt oss försöka söka efter filmen ”Black Book” med 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) Black Book
poäng: 0.694644242424065404
Träffpunkter:
field:title
term:book
fragment:
—————————–
field:title
term:black
fragment:
—————————–
2) Hook
score: 0.4013974252803939857
Hit Locations:
field:title
term:hook
fragment:
—————————–
3) Attackera blocket
poäng: 0.2838308365090324
Träffpunkter:
field:title
term:block
fragment:
—————————–
4) Here Comes the Boom
poäng: 0.283830308365090324
Träffpunkter:
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
poäng: 0.25687349813115684
träffpunkter:
field:title
term:look
fragment:
—————————–
7) Grosse Pointe Blank
poäng: 0.231717469073782136
Träffpunkter:
field:title
term:blank
fragment:
—————————–
8) The Book Thief
poäng: 0.19059065534780495
Träffpunkter:
field:title
term:book
fragment:
—————————–
9) The Book of Eli
poäng: 0.19059065534780495
Träffpunkter:
field:title
term:book
fragment:
—————————–
10) Livets bok
poäng: 0.19059065534780495
Träffpunkter:
field:title
term:book
fragment:
—————————–
11) Djungelboken
Poäng: 0.19059065534780495
Träffpunkter:
field:title
term:book
fragment:
—————————–
12) Tillbaka till framtiden
poäng: 0.17061000968368
Träffpunkter:
field:title
term:back
fragment:
—————————–
|
Inte dåligt. Vi fick den film vi sökte efter som första resultat. En disjunktionssökning skulle dock fortfarande ge bättre resultat.
Men ändå ser det ut som om vi har en ny trevlig egenskap här; bieffekten av fuzziness matching minskar något när antalet nyckelord ökar. En sökning på ”Black Book” med fuzziness 1 kan fortfarande ge resultat som back look eller lack cook (vissa kombinationer med edit distance 1), men det är osannolikt att dessa är riktiga filmtitlar.
En sökning på ”book eli” med fuzziness 2 skulle fortfarande ge 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
47
|
1) Ed Wood
poäng: 0.030723793900031805
Träffpunkter:
field:title
term:wood
fragment:
—————————–
field:title
term:ed
fragment:
—————————–
2) Man of Tai Chi
poäng: 0.027104276198262626
Träffpunkter:
field:title
term:chi
fragment:
—————————–
field:title
term:tai
fragment:
—————————–
3) The Book of Eli
Poäng: 0.02608335441670756
Träffpunkter:
field:title
term:eli
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) The Good Lie
poäng: 0.02439822770591834
träffpunkter:
field:title
term:lie
fragment:
—————————–
field:title
term:good
fragment:
—————————–
|
Men eftersom ett engelskt ord i genomsnitt är fem bokstäver långt skulle jag INTE rekommendera att man använder ett redigeringsavstånd som är större än två, såvida inte användaren söker efter långa ord som det är lätt att stava fel på, som till exempel ”Schwarzenegger” (åtminstone för personer som inte är tyskar eller österrikare).
Slutsats
I den här artikeln diskuterade vi fuzziness-matchning och hur man kan övervinna dess stora bieffekt utan att förstöra relevansen. Observera att fuzzy matchning bara är en av många funktioner som du bör dra nytta av när du implementerar en relevant och användarvänlig sökning. Vi kommer att diskutera några av dem under den här serien: Vi kommer att ta upp följande saker i denna serie: N-Grams, Stopwords, Steeming, Shingle och Elision. Etc.
Kolla också in del 1 och del 2 i den här serien.
Under tiden, om du har några frågor, kan du twittra mig på @deniswsrosa.
Författare
- Denis Rosa, Developer Advocate, Couchbase –
