Sumean täsmäytyksen avulla voit tunnistaa kohdekohteen epätarkat vastineet. Se on monien hakukoneiden kehysten peruskivi ja yksi tärkeimmistä syistä siihen, että voit saada relevantteja hakutuloksia, vaikka kyselyssäsi olisi kirjoitusvirhe tai erilainen verbaalinen aikamuoto.
Kuten arvata saattaa, on olemassa monia algoritmeja, joita voidaan käyttää tekstin sumeaan hakuun, mutta lähes kaikki hakukoneiden kehykset (bleve mukaan lukien) käyttävät sumeaan merkkijonojen täsmäytykseen ensisijaisesti Levenshteinin etäisyyttä:
Levenshteinin etäisyys
Tunnetaan myös nimellä muokkausetäisyys, ja se on muunnosten (poistojen, lisäysten tai korvausten) määrä, joka tarvitaan lähde-merkkijonon muuttamiseksi kohde-merkkijonoksi. Jos esimerkiksi tavoitetermi on ”kirja” ja lähde on ”selkä”, sinun on muutettava ensimmäinen ”o” muotoon ”a” ja toinen ”o” muotoon ”c”, jolloin Levenshteinin etäisyys on 2. Edit Distance on erittäin helppo toteuttaa, ja se on suosittu haaste koodihaastatteluissa (Levenshtein-toteutuksia JavaScriptissä, Kotlinissa, Javassa ja monissa muissa kielissä löydät täältä).
Lisäksi jotkut kehykset tukevat myös Damerau-Levenshteinin etäisyyttä:
Damerau-Levenshteinin etäisyys
Se on Levenshteinin etäisyyden laajennus, joka sallii yhden lisäoperaation: Kahden vierekkäisen merkin transponointi:
Esim: TSAR:sta STAR:ksi
Damerau-Levenshteinin etäisyys = 1 (S:n ja T:n paikkojen vaihtaminen maksaa vain yhden operaation)
Levenshteinin etäisyys = 2 (S:n korvaaminen T:llä ja T:n korvaaminen S:llä)
Sumea täsmäytys (Fuzzy Matching) ja relevanssi (Relevance)
Sumea täsmäys (Fuzzy Matching) tuo mukanaan erään ison sivuvaikutuksen; se sotkee relevanssin kanssa. Vaikka Damerau-Levenshtein on algoritmi, joka ottaa huomioon suurimman osan tavallisten käyttäjien kirjoitusvirheistä, se voi sisältää myös huomattavan määrän vääriä positiivisia tuloksia, varsinkin kun käytetään kieltä, jossa on keskimäärin vain viisi kirjainta sanaa kohti, kuten englantia. Siksi useimmat hakukoneiden kehykset käyttävät mieluummin Levenshteinin etäisyyttä. Katsotaanpa todellinen esimerkki siitä:
Aluksi käytämme tätä elokuvaluettelotietokantaa. Suosittelen sitä lämpimästi, jos haluat leikkiä kokotekstihaun kanssa. Etsitään sitten elokuvia, joiden otsikossa on ”kirja”. Yksinkertainen koodi näyttäisi seuraavalta:
|
1
2
3
4
5
6
|
String indexName = ”movies_index”;
MatchQuery query = SearchQuery.match(”kirja”).field(”title”);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(6));
printResults(movies);
|
Yllä oleva koodi tuo seuraavat tulokset:
|
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
47
|
1) The Book Thief
pisteet: 4.826942606027416
osumapaikat:
osumapaikat:
field:title
term:book
fragment:
—————————–
2) The Book of Eli
score: 4.826942606027416
Hit Locations:
field:title
term:book
fragment:
field:title
term:book
fragment:
—————————–
4) Musta kirja
pisteet: 4.826942606027416
osumapaikat:
osumapaikat:
field:title
term:book
fragment:
field:title
term:book
fragment:
field:title
term:book
fragment:
—————————–
|
Oletusarvoisesti tulokset ovat isojen ja pienten kirjainten suhteen tuntemattomia, mutta voit helposti muuttaa tätä käyttäytymistä luomalla uusia indeksejä, joissa on eri analysaattorit.
Lisätään nyt kyselyymme sumea täsmäytysominaisuus asettamalla fuzziness-arvoksi 1 (Levenshteinin etäisyys 1), mikä tarkoittaa sitä, että sanoilla ”kirjalla” ja ”ulkoasun katsominen” on sama relevanssi.
|
1
2
3
4
5
6
|
String indexName = ”movies_index”;
MatchQuery query = SearchQuery.match(”kirja”).field(”title”).fuzziness(1);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(6));
printResults(movies);
|
Ja tässä on sumea hakutulos:
|
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) Koukku
pisteet: 1.1012248063242538
osumapaikat: 1012248063242538
osumapaikat:
kenttä:otsikko
termi:koukku
fragmentti:
—————————–
2) Here Comes the Boom
pisteet: 0.7786835148361213
osumapaikat:
kenttä:otsikko
termi:puomi
fragmentti:
—————————–
3) Look Who’s Talking Too
score: 0.7047266634351538
Hit Locations:
kenttä:otsikko
termi:katso
fragmentti:
—————————–
4) Look Who’s Talking
pisteet: 0.7047266634351538
osumapaikat:
field:title
term:look
fragment:
—————————–
5) The Book Thief
pisteet: 0.52288117537184
osumapaikat:
field:title
term:book
fragment:
—————————–
6) The Book of Eli
pisteet: 0.52288117537184
osumapaikat:
field:title
term:book
fragment:
—————————–
|
Nyt elokuva nimeltä ”Koukku” on aivan ensimmäinen hakutulos, joka ei ehkä ole aivan sitä, mitä käyttäjä odottaa hakusanalla ”Kirja”.
Miten minimoidaan vääriä positiivisia tuloksia sumeiden hakujen aikana
Ihanteellisessa maailmassa käyttäjät eivät koskaan tekisi kirjoitusvirheitä hakiessaan jotakin. Se ei kuitenkaan ole maailma, jossa elämme, ja jos haluat käyttäjillesi miellyttävän kokemuksen, sinun on käsiteltävä vähintään muokkausetäisyyttä 1. Siksi varsinainen kysymys kuuluu: Miten voimme tehdä sumean merkkijonon täsmäytyksen ja samalla minimoida relevanssihäviön?
Voimme hyödyntää useimpien hakukoneiden kehysten yhtä ominaisuutta: Vastaavuus, jolla on pienempi muokkausetäisyys, saa yleensä korkeamman pistemäärän. Tämän ominaisuuden avulla voimme yhdistää nämä kaksi kyselyä, joilla on eri sumeusasteet, yhdeksi:
|
1
2
3
4
5
6
7
8
|
String indexName = ”movies_index”;
String word = ”Kirja”;
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);
|
Tässä on yllä olevan sumean kyselyn tulos:
|
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) Kirjavaras
pisteet: 2.398890092610849
osumapaikat: 398890092610849
osumapaikat:
field:title
term:book
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:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) Musta kirja
pisteet: 2.39888890092610849
osumapaikat:
osumapaikat:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
5) Viidakkokirja
pisteet: 2.39888890092610849
osumapaikat:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
6) Viidakkokirja 2
pisteet: 1.958685557004688
osumapaikat:
osumapaikat:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
7) National Treasure: Book of Secrets
pisteet: 1.6962714808368062
osumapaikat:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
8) American Pie Presents: The Book of Love
pisteet: 1.51719191317611584
osumapaikat:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
9) Hook
score: 0.5052232532518679681
Hit Locations:
field:title
term:hook
fragment:
—————————–
10) Here Comes the Boom
pisteet: 0.357246781294941
Osumapaikat:
field:title
term:tree
fragment:
—————————–
11) Look Who’s Talking Too
pisteet: 0.3233166333301992025
osumapaikat:
field:title
term:look
fragment:
—————————–
12) Look Who’s Talking
pisteet: 0.3233166333301992025
osumapaikat:
field:title
term:look
fragment:
—————————–
|
Kuten näet, tämä tulos on paljon lähempänä sitä, mitä käyttäjä saattaa odottaa. Huomaa, että käytämme nyt luokkaa nimeltä DisjunctionQuery, disjunktiot vastaavat SQL:n ”OR”-operaattoria.
Mitä muuta voisimme parantaa vähentämään sumean yhteensovittamisalgoritmin negatiivista sivuvaikutusta? Analysoidaanpa ongelmamme uudelleen ymmärtääkseen, tarvitseeko se lisäparannuksia:
Tiedämme jo, että sumeat hakutoiminnot voivat tuottaa joitakin odottamattomia tuloksia (esim. Book -> Look, Hook). Yhden termin haku on kuitenkin yleensä kauhea kysely, sillä se antaa meille tuskin vihjettä siitä, mitä käyttäjä tarkalleen ottaen yrittää saavuttaa.
Jopa Google, jolla on kiistatta yksi kehittyneimmistä käytössä olevista sumeista hakualgoritmeista, ei tiedä tarkalleen, mitä etsin, kun haen sanaa ”pöytä”:
Millainen on siis avainsanojen keskipituus hakukyselyssä? Vastatakseni tähän kysymykseen näytän kuvaajan Rand Fishkinin vuoden 2016 esityksestä. (Hän on yksi SEO-maailman tunnetuimmista guruista)
Yllä olevan kuvaajan mukaan ~80 %:ssa hakukyselyistä on 2 tai useampia avainsanoja, joten yritetään hakea elokuvaa ”Musta kirja” käyttämällä sumeutta 1:
|
1
2
3
4
5
6
|
String indexName = ”movies_index”;
MatchQuery query = SearchQuery.match(”Musta kirja”).field(”title”).fuzziness(1);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(12));
printResults(movies);
|
Result:
Ei huono. Saimme ensimmäisenä tuloksena etsimämme elokuvan. Disjunktiokysely toisi kuitenkin vielä paremmat tulokset.
Mutta silti, näyttää siltä, että meillä on tässä uusi mukava ominaisuus; epätarkkuuden yhteensovittamisen sivuvaikutus vähenee hieman avainsanojen määrän kasvaessa. Haku ”Black Book” hakusanalla fuzziness 1 voi edelleen tuoda tuloksia kuten back look tai lack cook (joitakin yhdistelmiä edit distance 1:llä), mutta nämä eivät todennäköisesti ole oikeita elokuvanimikkeitä.
Haku ”book eli” hakusanalla fuzziness 2 toisi sen edelleen kolmantena tuloksena:
|
1
2
3
4
5
6
|
String indexName = ”movies_index”;
MatchQuery query = SearchQuery.match(”kirja 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
pisteet: 0.030723793900031805
Osuma-paikat:
field:title
term:wood
fragment:
—————————–
field:title
term:ed
fragment:
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) The Good Lie
pisteet: 0.02439822770591834
osumapaikat:
osumapaikat:
field:title
term:lie
fragment:
—————————–
field:title
term:good
fragment:
—————————–
|
Koska keskimääräinen englanninkielinen sana on kuitenkin viiden kirjaimen pituinen, en suosittele käyttämään suurempaa kuin kahden kirjaimen muokkausetäisyyttä, ellei käyttäjä etsi pitkiä sanoja, jotka on helppo kirjoittaa väärin, kuten vaikkapa ”Schwarzenegger” (ainakaan ei-saksalaisille tai ei-itävaltalaisille).
Johtopäätös
Tässä artikkelissa käsiteltiin epätarkkuuden täsmäytystä ja sitä, miten sen merkittävästä sivuvaikutuksesta päästään eroon sotkematta sen relevanssia. Muista, että sumea täsmäytys on vain yksi monista ominaisuuksista, joita kannattaa hyödyntää, kun toteutat relevanttia ja käyttäjäystävällistä hakua. Käsittelemme tässä sarjassa joitakin niistä: N-Grams, Stopwords, Steeming, Shingle, Elision. Etc.
Lue myös tämän sarjan osa 1 ja osa 2.
Jos sinulla on kysyttävää, twiittaa minulle @deniswsrosa.
Author
- Denis Rosa, Developer Advocate, Couchbase –
