Fuzzy matching vă permite să identificați potriviri neexacte ale elementului țintă. Este piatra de temelie a multor cadre ale motoarelor de căutare și unul dintre principalele motive pentru care puteți obține rezultate de căutare relevante chiar dacă aveți o greșeală de scriere în interogare sau un timp verbal diferit.
Așa cum v-ați putea aștepta, există mulți algoritmi care pot fi folosiți pentru căutarea fuzzy pe text, dar practic toate cadrele motoarelor de căutare (inclusiv bleve) folosesc în principal Distanța Levenshtein pentru potrivirea fuzzy a șirurilor de caractere:
Distanța Levenshtein
Cunoscută și sub numele de distanța de editare, reprezintă numărul de transformări (ștergeri, inserții sau substituiri) necesare pentru a transforma un șir sursă în cel țintă. De exemplu, dacă termenul țintă este „carte”, iar sursa este „spate”, va trebui să schimbați primul „o” în „a” și al doilea „o” în „c”, ceea ce ne va da o Distanță Levenshtein de 2. Distanța de editare este foarte ușor de implementat și este o provocare populară în timpul interviurilor de cod (puteți găsi implementări Levenshtein în JavaScript, Kotlin, Java și multe altele aici).
În plus, unele cadre suportă și distanța Damerau-Levenshtein:
Distanța Damerau-Levenshtein
Este o extensie a distanței Levenshtein, care permite o operație suplimentară: Transpunerea a două caractere adiacente:
Ex: TSAR în STAR
Distanța Damerau-Levenshtein = 1 (Schimbarea pozițiilor S și T costă o singură operație)
Distanța Levenshtein = 2 (Înlocuiți S cu T și T cu S)
Corelări neclare și relevanță
Corelările neclare au un mare efect secundar; încurcă relevanța. Deși Damerau-Levenshtein este un algoritm care ia în considerare majoritatea greșelilor de ortografie ale utilizatorilor obișnuiți, acesta poate include și un număr semnificativ de falsuri pozitive, mai ales atunci când folosim o limbă cu o medie de doar 5 litere pe cuvânt, cum este engleza. Acesta este motivul pentru care cele mai multe dintre cadrele motoarelor de căutare preferă să rămână la distanța Levenshtein. Să vedem un exemplu real:
În primul rând, vom folosi acest set de date de catalog de filme. Îl recomand cu căldură dacă doriți să vă jucați cu căutarea full-text. Apoi, haideți să căutăm filme cu „carte” în titlu. Un cod simplu ar arăta în felul următor:
|
1
2
. 3
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);
|
Codul de mai sus va aduce următoarele rezultate:
|
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
scor: 4.82694260606027416
Locații lovite:
câmp:titlu
termen:carte
fragment:
fragment:
fragment:
fragment:
fragment:
:
fragment:
—————————–
2) The Book of Eli
scor: 4.82694242606027416
Hit Locations:
Hit Locations:
câmp:titlu
termen:carte
fragment:
—————————–
3) The Book of Life
scor: 4.82694242606027416
Hit Locations:
Hit Locations:
field:title
term:book
fragment:
fragment:
:
:
:
:
:
:
fragment:
—————————–
4) Black Book
scor: 4.82694242606027416
Hit Locations:
:
field:title
term:book
fragment:
—————————–
5) The Jungle Book
scor: 4.82694242606027416
Hit Locations:
Hit Locations:
field:title
term:book
fragment:
—————————–
6) The Jungle Book 2
scor: 3.941182121308689627
Hit Locations:
Hit Locations:
field:title
term:book
fragment:
—————————–
|
În mod implicit, rezultatele sunt insensibile la majuscule și minuscule, dar puteți schimba cu ușurință acest comportament prin crearea de noi indici cu analizatori diferiți.
Acum, să adăugăm o capacitate de potrivire fuzzy la interogarea noastră prin setarea fuzziness la 1 (distanța Levenshtein 1), ceea ce înseamnă că „carte” și „aspect” vor avea aceeași relevanță.
|
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);
|
Și iată rezultatul căutării fuzzy:
|
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
scorul: 1.1012248063242538
Locații de lovire:
field:title
term:hook
fragment:
fragment:
fragment:
—————————–
2) Here Comes the Boom
scor: 0.778686835148361213
Hit Locations:
Hit Locations:
field:title
term:boom
fragment:
fragment:
—————————–
3) Look Who’s Talking Too
scor: 0.7047266634351538
Hit Locations:
field:title
term:look
fragment:
:
—————————–
4) Look Who’s Talking
scor: 0.70472466634351538
Locații lovite:
field:title
term:look
fragment:
—————————–
5) Hoțul de cărți
scor: 0.52288117537184
Locații lovite:
:
field:title
term:book
fragment:
—————————–
6) Cartea lui Eli
scor: 0.52288117537184
Locații lovite:
field:title
term:book
fragment:
—————————–
|
Acum, filmul numit „Hook” este primul rezultat al căutării, care s-ar putea să nu fie exact ceea ce se așteaptă utilizatorul la o căutare pentru „Book”.
Cum să minimizăm falsurile pozitive în timpul căutărilor fuzzy
Într-o lume ideală, utilizatorii nu ar face niciodată greșeli de scriere în timp ce caută ceva. Cu toate acestea, nu aceasta este lumea în care trăim și, dacă doriți ca utilizatorii dvs. să aibă o experiență plăcută, trebuie să vă ocupați de cel puțin o distanță de editare de 1. Prin urmare, adevărata întrebare este: Cum putem face potrivirea fuzzy a șirurilor de caractere, minimizând în același timp pierderea de relevanță?
Potem profita de o caracteristică a majorității cadrelor motoarelor de căutare: O potrivire cu o distanță de editare mai mică va avea, de obicei, un scor mai mare. Această caracteristică ne permite să combinăm aceste două interogări cu niveluri diferite de fuzzy în una singură:
|
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);
|
Iată rezultatul interogării fuzzy de mai sus:
|
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) Hoțul de cărți
scor: 2.398890092610849
Locații de lovire:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
2) The Book of Eli
scor: 2.398890092610849
Hit Locations:
:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
3) The Book of Life
scor: 2.398890092610849
Hit Locations:
:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) Cartea neagră
punctaj: 2.398890092610849
Locații de lovire:
Locații de lovire:
:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
5) The Jungle Book
scor: 2.398890092610849
Hit Locations:
:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
6) The Jungle Book 2
scor: 1.958688685557004688
Hit Locations:
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
7) National Treasure: Book of Secrets
scor: 1.696272714808368062
Hit Locations:
Hit Locations:
:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
8) American Pie Presents: The Book of Love
scor: 1.517191317611584
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
9) Hook
scor: 0.5052232518679681
Hit Locations:
Hit Locations:
field:title
term:hook
fragment:
—————————–
10) Here Comes the Boom
scor:
: 0.357246781294941
Locații lovite:
field:title
term:tree
fragment:
—————————–
11) Look Who’s Talking Too
scor: 0.32331663301992025
Locații lovite:
field:title
term:look
fragment:
:
:
—————————–
12) Look Who’s Talking
scor: 0.3233166330101992025
Locații lovite:
field:title
term:look
fragment:
—————————–
|
După cum puteți vedea, acest rezultat este mult mai aproape de ceea ce s-ar putea aștepta utilizatorul. Rețineți că acum folosim o clasă numită DisjunctionQuery, disjuncțiile sunt un echivalent al operatorului „OR” din SQL.
Ce am mai putea îmbunătăți pentru a reduce efectul secundar negativ al unui algoritm de potrivire fuzzy? Să reanalizăm problema noastră pentru a înțelege dacă are nevoie de îmbunătățiri suplimentare:
Știm deja că căutările fuzzy pot produce unele rezultate neașteptate (de exemplu, Book -> Look, Hook). Cu toate acestea, o căutare cu un singur termen este, de obicei, o interogare teribilă, deoarece abia dacă ne oferă un indiciu despre ce anume încearcă utilizatorul să realizeze.
Chiar și Google, care are, fără îndoială, unul dintre cei mai dezvoltați algoritmi de căutare fuzzy în uz, nu știe exact ce caut atunci când caut „masă”:
Atunci, care este lungimea medie a cuvintelor cheie într-o interogare de căutare? Pentru a răspunde la această întrebare, voi arăta un grafic din prezentarea lui Rand Fishkin din 2016. (El este unul dintre cei mai faimoși guru din lumea SEO)
Conform graficului de mai sus, ~80% dintre interogările de căutare au 2 sau mai multe cuvinte cheie, așa că haideți să încercăm să căutăm filmul „Black Book” folosind fuzziness 1:
|
1
2
. 3
3
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
99
|
1) Scorul Black Book
: 0.694644242424065404 Locații lovite:
câmp:titlu
termen:carte
fragment:
fragment:
—————————–
field:title
term:black
fragment:
—————————–
2) Hook
scor: 0.401393974252803939857
Locații de lovire:
Hit Locations:
field:title
term:hook
fragment:
fragment:
—————————–
3) Attack the Block
scor: 0.2838308365090324
Hit Locations:
Hit Locations:
field:title
term:block
fragment:
fragment:
—————————–
4) Here Comes the Boom
scor: 0.2838308308365090324
Hit Locations:
Hit Locations:
field:title
term:boom
fragment:
fragment:
—————————–
5) Look Who’s Talking Too
scor: 0.2568687349813115684
Hit Locations:
:
field:title
term:look
fragment:
—————————–
6) Look Who’s Talking
scor: 0.2568687349813115115684
Locații lovite:
field:title
term:look
fragment:
—————————–
7) Grosse Pointe Blank
scor: 0.23171746469073782136
Hit Locations:
Hit Locations:
field:title
term:blank
fragment:
fragment:
—————————–
8) The Book Thief
scor: 0.19059065534780495
Hit Locations:
Hit Locations:
field:title
term:book
fragment:
fragment:
fragment:
:
fragment:
—————————–
9) The Book of Eli
scor: 0.1905909065534780495
Hit Locations:
Hit Locations:
field:title
term:book
fragment:
—————————–
10) The Book of Life
scor: 0.19059065534780495
Hit Locations:
Hit Locations:
field:title
term:book
fragment:
—————————–
11) The Jungle Book
scor: 0.19059065534780495
Hit Locations:
Hit Locations:
field:title
term:book
fragment:
—————————–
12) Back to the Future
scor: 0.17061000968368
Hit Locations:
:
field:title
term:back
fragment:
fragment:
—————————–
|
Nu e rău. Am obținut filmul pe care îl căutam ca prim rezultat. Cu toate acestea, o interogare cu disjuncție ar aduce în continuare un set mai bun de rezultate.
Dar totuși, se pare că avem o nouă proprietate frumoasă aici; efectul secundar al potrivirii neclare scade ușor pe măsură ce crește numărul de cuvinte cheie. O căutare pentru „Black Book” cu fuzziness 1 poate aduce în continuare rezultate precum back look sau lack cook (unele combinații cu distanța de editare 1), dar este puțin probabil ca acestea să fie titluri de filme reale.
O căutare pentru „carte eli” cu fuzziness 2 ar aduce în continuare aceasta ca al treilea rezultat:
|
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
scor: 0.03072323793900031805
Locații de lovire:
field:title
term:wood
fragment:
fragment:
—————————–
field:title
term:ed
fragment:
fragment:
—————————–
2) Omul de Tai Chi
punctaj: 0.027104276198262626
Locații lovite:
:
field:title
term:chi
fragment:
fragment:
—————————–
field:title
term:tai
fragment:
:
—————————–
3) Cartea lui Eli
scor: 0.02608335441670756
Locații lovite:
field:title
term:eli
fragment:
fragment:
—————————–
field:title
term:book
fragment:
fragment:
—————————–
4) Minciuna cea bună
scor: 0.02439822770591834
Locații lovite:
field:title
term:lie
fragment:
fragment:
—————————–
field:title
term:good
fragment:
fragment:
—————————–
|
Cu toate acestea, deoarece cuvântul englezesc mediu are 5 litere, NU aș recomanda utilizarea unei distanțe de editare mai mari de 2, cu excepția cazului în care utilizatorul caută cuvinte lungi care sunt ușor de scris greșit, cum ar fi „Schwarzenegger”, de exemplu (cel puțin pentru cei care nu sunt germani sau austrieci).
Concluzie
În acest articol, am discutat despre potrivirea fuzziness și despre cum să depășim efectul său secundar major fără a da peste cap relevanța sa. Atenție, potrivirea fuzzy este doar una dintre multele caracteristici de care ar trebui să profitați în timp ce implementați o căutare relevantă și ușor de utilizat. Vom discuta câteva dintre ele pe parcursul acestei serii: N-Grams, Stopwords, Steeming, Shingle, Elision. Etc.
Consultați și Partea 1 și Partea 2 a acestei serii.
Între timp, dacă aveți întrebări, trimiteți-mi un mesaj pe Twitter la @deniswsrosa.
Autor
- Denis Rosa, Developer Advocate, Couchbase –
.