A Fuzzy Matching lehetővé teszi a célelem nem pontos egyezéseinek azonosítását. Ez számos keresőmotor-keretrendszer alapköve, és az egyik fő oka annak, hogy releváns keresési eredményeket kaphatsz akkor is, ha a lekérdezésedben elírás van, vagy eltérő igeidőt használsz.
Amint az várható volt, számos algoritmus létezik, amely a szövegeken végzett fuzzy kereséshez használható, de gyakorlatilag minden keresőmotor-keretrendszer (beleértve a bleve-et is) elsősorban a Levenshtein-távolságot használja a fuzzy string-illesztéshez:
Levenshtein-távolság
Az Edit Distance néven is ismert távolság a forrássztring célsztringgé alakításához szükséges transzformációk (törlések, beszúrások vagy helyettesítések) száma. Ha például a célkifejezés a “könyv”, a forrás pedig a “hát”, akkor az első “o”-t “a”-ra, a második “o”-t pedig “c”-re kell változtatni, ami 2 Levenshtein-távolságot eredményez.Az Edit Distance nagyon könnyen megvalósítható, és népszerű kihívás a kódinterjúk során (Levenshtein implementációkat találsz JavaScript, Kotlin, Java és sok más nyelven itt).
Kiegészítésképpen néhány keretrendszer támogatja a Damerau-Levenshtein távolságot is:
Damerau-Levenshtein távolság
Ez a Levenshtein távolság kiterjesztése, amely egy extra műveletet tesz lehetővé: Két szomszédos karakter áthelyezése:
Például: TSAR STAR-ra
Damerau-Levenshtein távolság = 1 (Az S és T pozíciók felcserélése csak egy műveletbe kerül)
Levenshtein távolság = 2 (S-t T-re és T-t S-re cseréljük)
Fuzzy matching és relevancia
A fuzzy matchingnek van egy nagy mellékhatása; összekuszálja a relevanciát. Bár a Damerau-Levenshtein algoritmus figyelembe veszi a legtöbb közönséges felhasználói helyesírási hibát, jelentős számú hamis pozitív eredményt is tartalmazhat, különösen akkor, ha olyan nyelvet használunk, ahol egy szó átlagosan csak 5 betűből áll, mint például az angol. Ezért a legtöbb keresőmotor-keretrendszer inkább marad a Levenshtein-távolságnál. Lássunk erre egy valós példát:
Először ezt a filmkatalógus adathalmazt fogjuk használni. Nagyon ajánlom, ha teljes szöveges kereséssel akarsz játszani. Ezután keressünk olyan filmeket, amelyeknek a címében szerepel a “könyv” szó. Egy egyszerű kód a következőképpen nézne ki:
|
1
2
3
. 4
5
6
|
String indexName = “movies_index”;
MatchQuery query = SearchQuery.match(“könyv”).field(“cím”);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(6));
printResults(movies);
|
A fenti kód a következő eredményeket hozza:
|
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) A könyvtolvaj
pontszám: 4.826942606027416
Találati helyek:
mező:cím
kifejezés:könyv
töredék:
—————————–
2) The Book of Eli
score: 4.826942606027416
Találati helyek:
The Book of Eli
score: 4.826942606027416
Hit Locations:
mező:cím
kifejezés:könyv
töredék:
mező:cím
kifejezés:könyv
töredék:
—————————–
3) The Book of Life
score: 4.826942606027416
Hit Locations:
The Book of Life
score: 4.826942606027416
Hit Locations:
—————————–
4) Black Book
score: 4.82694242606027416
Találati helyek:
Találati helyek: 1:
—————————–
5) The Jungle Book
score: 4.826942606027416
Hit Locations:
The Jungle Book
score: 4.826942606027416
Hit Locations:
mező:cím
kifejezés:könyv
töredék: A dzsungel könyve
mező:cím
kifejezés:könyv
töredék:
mező:cím
kifejezés:könyv
töredék: A könyvtolvaj
mező:cím
kifejezés:könyv
töredék:
—————————–
|
Alapértelmezés szerint a találatok nem érzékelik a nagy- és kisbetűket, de ezt a viselkedést könnyen megváltoztathatjuk, ha új indexeket hozunk létre különböző elemzőkkel.
Most adjunk a lekérdezésünkhöz egy fuzzy matching képességet, a fuzziness 1 (Levenshtein távolság 1) beállításával, ami azt jelenti, hogy a “book” és a “look” ugyanolyan relevanciájú lesz.
|
1
2
3
4
5
6
|
String indexName = “movies_index”;
MatchQuery query = SearchQuery.match(“könyv”).field(“cím”).fuzziness(1);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(6));
printResults(movies);
|
És itt a fuzzy keresés eredménye:
|
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
pontszám: 1.1012248063242538
találati helyek:
mező:cím
kifejezés:horog
töredék:
mező:cím
kifejezés:horog
töredék:
field:title
term:boom
fragment:
fragment:
—————————–
3) Look Who’s Talking Too
score: 0.7047266634351538
Hit Locations: 0.7047266634351538
Hit Locations: 0.7047266634351538
hit:
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.52288117537184
Hit Locations:
fragment:
—————————–
6) The Book of Eli
score: 0.52288117537184
Hit Locations:
mező:cím
kifejezés:könyv
fragmentum:
mező:cím
kifejezés:könyv
fragmentum:
—————————–
|
Most a “Hook” című film a legelső keresési eredmény, ami nem biztos, hogy pontosan az, amire a felhasználó a “Book” keresésnél számít.
Hogyan lehet minimalizálni a hamis pozitív eredményeket a fuzzy keresések során
Egy ideális világban a felhasználók soha nem tennének elírásokat keresés közben. Azonban nem ebben a világban élünk, és ha azt szeretnénk, hogy a felhasználóknak kellemes élményt nyújtson, akkor legalább az 1-es szerkesztési távolságot kezelni kell. Ezért az igazi kérdés az, hogy hogyan tudunk fuzzy stringillesztést végezni úgy, hogy közben minimalizáljuk a relevanciaveszteséget?
Kihasználhatjuk a legtöbb keresőmotor-keretrendszer egyik tulajdonságát: Az alacsonyabb szerkesztési távolsággal rendelkező egyezés általában magasabb pontszámot kap. Ez a tulajdonság lehetővé teszi számunkra, hogy a két különböző homályossági szintű lekérdezést egybe kombináljuk:
|
1
2
3
4
5
6
7
8
|
String indexName = “movies_index”;
String word = “Könyv”;
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);
|
Itt a fenti fuzzy lekérdezés eredménye:
|
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) A könyvtolvaj
pont: 2.398890092610849
találati helyek:
field:title
term:book
fragment:
fragment:
—————————–
field:title
term:book
fragment:
—————————–
2) The Book of Eli
score: 2.39888890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
3) The Book of Life
score: 2.39888890092610849
Hit Locations: 2.398890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) Black Book
score: 2.39888890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
5) The Jungle Book
score: 2.39888890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
6) The Jungle Book 2
score: 1.9586885557004688
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:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
9) Hook
score: 0.5052232518679681
Hit Locations:
field:title
term:hook
fragment:
fragment:
Hook:
—————————–
10) Here Comes the Boom
score: Here Comes the Boom
pontszám: 1: 0.357246781294941
Találati helyek:
field:title
term:tree
fragment:
—————————–
11) Look Who’s Talking Too
score: 0.3233166333301992025
Hit Locations: 0.32331663301992025
Hit Locations:
field:title
term:look
fragment:
—————————–
12) Look Who’s Talking
score: 0.3233166333301992025
Hit Locations:
field:title
term:look
fragment:
—————————–
|
Amint látható, ez az eredmény sokkal közelebb áll ahhoz, amire a felhasználó számíthat. Vegyük észre, hogy most a DisjunctionQuery nevű osztályt használjuk, a disjunctions az SQL “OR” operátorának megfelelője.
Mit tudnánk még javítani, hogy csökkentsük a fuzzy matching algoritmus negatív mellékhatását? Elemezzük újra a problémánkat, hogy megértsük, szükség van-e további javításra:
Azt már tudjuk, hogy a fuzzy keresések váratlan eredményeket produkálhatnak (pl. Book -> Look, Hook). Az egyszavas keresés azonban általában borzalmas lekérdezés, mivel alig ad támpontot arra, hogy a felhasználó pontosan mit akar elérni.
Még a Google sem tudja pontosan, hogy mit keresek, amikor az “asztal” kifejezésre keresek:
Szóval, mi a kulcsszavak átlagos hossza egy keresési lekérdezésben? A kérdés megválaszolásához mutatok egy grafikont Rand Fishkin 2016-os előadásából. (Ő a SEO világ egyik leghíresebb guruja)
A fenti grafikon szerint a keresési lekérdezések ~80%-a 2 vagy több kulcsszót tartalmaz, tehát próbáljunk meg a “Fekete könyv” című filmre keresni a fuzziness 1 segítségével:
|
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
pontszám: 0.6946442424065404
találati helyek:
—————————–
field:title
term:black
fragment:
—————————–
2) Hook
score: 0.40139742528039857
Hit Locations:
field:title
term:hook
fragment:
field:title
term:block
fragment:
fragment:
—————————–
4) Here Comes the Boom
score: 0.2838308308365090324
Hit Locations: 0.2838308365090324
Hit Locations:
—————————–
5) Look Who’s Talking Too
score: 0.2568734949813115684
Hit Locations: 0.25687349813115684
Hit Locations: 0.25687349813115684
1:
field:title
term:look
fragment:
—————————–
6) Look Who’s Talking
score: 0.2568734949813115684
Hit Locations:
field:title
term:look
fragment:
—————————–
7) Grosse Pointe Blank
score: 0.231717469073782136
Hit Locations:
—————————–
9) The Book of Eli
score: 0.19059065534780495
Hit Locations: The Book of Eli
0.19059065534780495
Hit Locations:
mező:cím
kifejezés:könyv
töredék:
mező:cím
kifejezés:könyv
töredék:
mező:cím
kifejezés:könyv
fragmentum:
mező:cím
kifejezés:könyv
fragmentum:
—————————–
|
Nem rossz. Első találatként megkaptuk a keresett filmet. Egy diszjunkciós lekérdezés azonban még mindig jobb eredményhalmazt hozna.
De mégis, úgy tűnik, van itt egy új szép tulajdonságunk; a homályos megfeleltetés mellékhatása a kulcsszavak számának növekedésével kissé csökken. A “Fekete könyv” keresés 1-es homályossággal még mindig hozhat olyan találatokat, mint a back look vagy a lack cook (egyes kombinációk 1-es szerkesztési távolsággal), de ezek valószínűleg nem valódi filmcímek.
A “book eli” keresés 2 homályossággal még mindig a harmadik találatként hozná:
|
1
2
3
4
5
6
|
String indexName = “movies_index”;
MatchQuery query = SearchQuery.match(“könyv eli”).field(“cím”).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.03072379393900031805
Találati helyek:
field:title
term:wood
fragment:
—————————–
field:title
term:ed
fragment:
—————————–
2) Man of Tai Chi
score: 0.027104276198262626
Hit Locations:
field:title
term:chi
fragment: Tai Chi
fragment:
—————————–
field:title
term:tai
fragment:
—————————–
3) The Book of Eli
score: 0.02608335441670756
Hit Locations:
mező:cím
kifejezés:eli
töredék:
mező:cím
kifejezés:eli
töredék:
—————————–
field:title
term:book
fragment:
—————————–
field:title
term:good
fragment:
—————————–
|
Mivel azonban az átlagos angol szó 5 betű hosszú, NEM javasolnám a 2-nél nagyobb szerkesztési távolság használatát, kivéve, ha a felhasználó hosszú, könnyen elírható szavakra keres, mint például a “Schwarzenegger” (legalábbis nem németek vagy nem osztrákok számára).
Következtetés
Ebben a cikkben tárgyaltuk a homályos megfeleltetést, és azt, hogy hogyan lehet leküzdeni a fő mellékhatását anélkül, hogy elrontanánk a relevanciáját. Ne feledje, a homályos megfeleltetés csak egy a sok funkció közül, amelyet érdemes kihasználni a releváns és felhasználóbarát keresés megvalósítása során. Ebben a sorozatban néhányat ezek közül fogunk tárgyalni: N-Gramok, Stopwords, Steeming, Shingle, Elision. stb.
Nézze meg a sorozat 1. és 2. részét is.
Eközben, ha bármilyen kérdése van, tweeteljen nekem a @deniswsrosa címen.
Author
- Denis Rosa, Developer Advocate, Couchbase –
