Fuzzy matching umožňuje identifikovat nepřesné shody cílové položky. Je základním kamenem mnoha rámců vyhledávačů a jedním z hlavních důvodů, proč můžete získat relevantní výsledky vyhledávání, i když máte v dotazu překlep nebo jiný slovosled.
Jak se dalo očekávat, existuje mnoho algoritmů, které lze použít pro fuzzy vyhledávání v textu, ale prakticky všechny rámce vyhledávačů (včetně bleve) používají pro fuzzy porovnávání řetězců především Levenshteinovu vzdálenost:
Levenshteinova vzdálenost
Známá také jako editační vzdálenost, je to počet transformací (vymazání, vložení nebo nahrazení) potřebných k transformaci zdrojového řetězce na cílový. Pokud je například cílový výraz „book“ a zdrojový „back“, bude třeba změnit první „o“ na „a“ a druhé „o“ na „c“, čímž získáme Levenshteinovu vzdálenost 2. Edit Distance se velmi snadno implementuje a je oblíbenou výzvou při pohovorech o kódu (Implementace Levenshteinovy vzdálenosti v jazycích JavaScript, Kotlin, Java a mnoha dalších najdete zde).
Dále některé frameworky podporují také Damerauovu-Levenshteinovu vzdálenost:
Damerauova-Levenshteinova vzdálenost
Jedná se o rozšíření Levenshteinovy vzdálenosti, které umožňuje jednu operaci navíc:
Příklad: TSAR na STAR
Damerau-Levenshteinova vzdálenost = 1 (Prohození pozic S a T stojí jen jednu operaci)
Levenshteinova vzdálenost = 2 (Nahradit S za T a T za S)
Fuzzy porovnávání má jeden velký vedlejší efekt: zamotává se s relevancí. Přestože Damerau-Levenshteinův algoritmus zohledňuje většinu běžných uživatelských překlepů, může zahrnovat i značné množství falešně pozitivních výsledků, zejména pokud používáme jazyk s průměrem pouhých 5 písmen na slovo, jako je angličtina. Proto se většina rámců vyhledávačů raději drží Levenshteinovy vzdálenosti. Podívejme se na reálný příklad:
Nejprve použijeme tuto sadu dat z filmového katalogu. Vřele ho doporučuji, pokud si chcete pohrát s fulltextovým vyhledáváním. Poté vyhledáme filmy, které mají v názvu slovo „kniha“. Jednoduchý kód by vypadal následovně:
|
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);
|
Výše uvedený kód přinese následující výsledky:
|
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) Zlodějka knih
skóre: 4.826942606027416
Místa zásahu:
pole:název
termín:kniha
fragment:
pole:název
termín:kniha
fragment:
pole:název
termín:kniha
fragment:
pole:název
termín:kniha
fragment:
pole:název
termín:kniha
fragment:
pole:název
termín:kniha
fragment:
—————————–
|
Ve výchozím nastavení výsledky nerozlišují velká a malá písmena, ale toto chování můžete snadno změnit vytvořením nových indexů s různými analyzátory.
Nyní přidáme do našeho dotazu možnost fuzzy párování nastavením fuzzy na hodnotu 1 (Levenshteinova vzdálenost 1), což znamená, že „book“ a „look“ budou mít stejnou relevanci.
|
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);
|
A zde je výsledek fuzzy vyhledávání:
|
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) Hák
skóre: 1.1012248063242538
Místa zásahu:
pole:název
termín:háček
fragment:
—————————–
2) Here Comes the Boom
skóre: 0.7786835148361213
místa zásahu:
místo zásahu:
místo zásahu
pole:název
termín:boom
fragment:
—————————–
3) Podívejte se, kdo taky mluví
skóre: 0.7047266634351538
Místa zásahu:
field:title
term:look
fragment:
—————————–
4) Podívejte se, kdo mluví
skóre: 0.7047266634351538
Místa zásahu:
field:title
term:look
fragment:
—————————–
5) Zlodějka knih
skóre: 0.52288117537184
Místa zásahu:
pole:název
termín:kniha
fragment:
—————————–
6) Kniha Eli
skóre: 0.52288117537184
Místa zásahu:
pole:název
termín:kniha
fragment:
—————————–
|
Nyní je film s názvem „Hook“ úplně prvním výsledkem hledání, což nemusí být přesně to, co uživatel při hledání „Book“ očekává.
Jak minimalizovat falešně pozitivní výsledky při fuzzy vyhledávání
V ideálním světě by uživatelé při hledání nikdy neudělali žádný překlep. V takovém světě však nežijeme, a pokud chcete, aby uživatelé měli příjemný zážitek, musíte zvládnout alespoň editační vzdálenost 1. Proto skutečná otázka zní: Jak můžeme provést fuzzy porovnávání řetězců a zároveň minimalizovat ztrátu relevance?
Můžeme využít jednu vlastnost většiny vyhledávacích rámců: Shoda s nižší editační vzdáleností obvykle získá vyšší skóre. Tato vlastnost nám umožňuje spojit tyto dva dotazy s různou úrovní fuzzy do jednoho:
|
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);
|
Tady je výsledek výše uvedeného fuzzy dotazu:
|
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) Zlodějka knih
skóre: 2.398890092610849
Místa zásahu:
pole:název
termín:kniha
fragment:
—————————–
pole:název
termín:kniha
fragment:
—————————–
2) The Book of Eli
skóre: 2.398890092610849
místa zásahu:
pole:název
termín:kniha
fragment:
—————————–
pole:název
termín:kniha
fragment:
—————————–
3) Kniha života
skóre: 2.398890092610849
Místa zásahu:
pole:název
termín:kniha
fragment:
—————————–
pole:název
termín:kniha
fragment:
—————————–
4) Černá kniha
skóre: 2.398890092610849
místa zásahu:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
5) Kniha džunglí
skóre: 2.398890092610849
místa zásahu:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
6) Kniha džunglí 2
skóre: 1.958685557004688
místa zásahu:
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: The Book of Love
skóre: 1.517191317611584
Místa zásahu:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
9) Háček
skóre: 0.5052232518679681
Místa zásahu:
pole:název
termín:háček
fragment:
—————————–
10) Here Comes the Boom
skóre: 0.357246781294941
Místa zásahu:
field:title
term:tree
fragment:
—————————–
11) Podívejte se, kdo taky mluví
skóre: 0.32331663301992025
Místa zásahu:
field:title
term:look
fragment:
—————————–
12) Podívejme se, kdo mluví
skóre: 0.32331663301992025
Místa zásahu:
field:title
term:look
fragment:
—————————–
|
Jak vidíte, tento výsledek je mnohem bližší tomu, co by uživatel mohl očekávat. Všimněte si, že nyní používáme třídu DisjunctionQuery, disjunkce jsou ekvivalentem operátoru „OR“ v SQL.
Co bychom ještě mohli zlepšit, abychom omezili negativní vedlejší efekt algoritmu fuzzy porovnávání? Znovu analyzujme náš problém, abychom pochopili, zda potřebuje další vylepšení:
Již víme, že fuzzy vyhledávání může přinést některé neočekávané výsledky (např. Book -> Look, Hook). Vyhledávání jediného výrazu je však obvykle hrozný dotaz, protože nám sotva napoví, čeho přesně se uživatel snaží dosáhnout.
Až Google, který má pravděpodobně jeden z nejpropracovanějších používaných fuzzy vyhledávacích algoritmů, neví přesně, co hledám, když hledám „tabulka“:
Jaká je tedy průměrná délka klíčových slov ve vyhledávacím dotazu? Pro zodpovězení této otázky uvedu graf z prezentace Randa Fishkina z roku 2016. (Je to jeden z nejznámějších guruů ve světě SEO)
Podle výše uvedeného grafu má ~80 % vyhledávacích dotazů 2 a více klíčových slov, zkusme tedy vyhledat film „Černá kniha“ pomocí 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) Černá kniha
skóre: 0.6946442424065404
Místa zásahu:
pole:název
termín:kniha
fragment:
—————————–
field:title
term:black
fragment:
—————————–
2) Háček
skóre: 0.40139742528039857
místa zásahu:
pole:název
termín:háček
fragment:
—————————–
3) Útok na blok
skóre: 0.2838308365090324
Místa zásahu:
pole:název
termín:blok
fragment:
—————————–
4) Here Comes the Boom
skóre: 0.2838308365090324
Místa zásahu:
pole:název
termín:boom
fragment:
—————————–
5) Podívejte se, kdo to taky mluví
skóre: 0.25687349813115684
Místa zásahu:
field:title
term:look
fragment:
—————————–
6) Podívejme se, kdo mluví
skóre: 0.25687349813115684
Místa zásahu:
Podívejme se, kdo mluví:
field:title
term:look
fragment:
pole:název
termín:prázdný
fragment:
pole:název
termín:kniha
fragment:
pole:název
termín:kniha
fragment:
pole:název
termín:kniha
fragment:
pole:název
termín:kniha
fragment:
pole:název
termín:zpět
fragment:
—————————–
|
Není špatné. Jako první výsledek se nám zobrazil hledaný film. Disjunkční dotaz by však stále přinesl lepší sadu výsledků.
Ale i tak to vypadá, že tu máme novou pěknou vlastnost; vedlejší efekt fuzziness matching mírně klesá s rostoucím počtem klíčových slov. Hledání „Black Book“ s fuzziness 1 může stále přinést výsledky jako back look nebo lack cook (některé kombinace s editační vzdáleností 1), ale ty pravděpodobně nebudou skutečnými názvy filmů.
Vyhledání výrazu „book eli“ s fuzziness 2 by stále přineslo tento výraz jako třetí výsledek:
|
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
skóre: 0.030723793900031805
Místa zásahu:
pole:název
termín:wood
fragment:
—————————–
field:title
term:ed
fragment:
—————————–
2) Man of Tai Chi
skóre: 0.0271042761982626
místa zásahu:
pole:název
termín:chi
fragment:
—————————–
field:title
term:tai
fragment:
—————————–
3) Kniha Eli
skóre: 0.02608335441670756
místa zásahu:
pole:název
termín:eli
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) Dobrá lež
skóre: 0.02439822770591834
Místa zásahu:
pole:název
termín:lež
fragment:
—————————–
field:title
term:good
fragment:
—————————–
|
Jelikož však průměrné anglické slovo má 5 písmen, NEDOPORUČUJI používat editační vzdálenost větší než 2, pokud uživatel nehledá dlouhá slova, která se snadno překlepnou, jako například „Schwarzenegger“ (alespoň pro neněmecké nebo nerakouské uživatele).
Závěr
V tomto článku jsme se zabývali porovnáváním rozmazanosti a tím, jak překonat jeho hlavní vedlejší efekt, aniž bychom narušili jeho relevanci. Připomínáme, že fuzzy matching je jen jednou z mnoha funkcí, které byste měli využít při implementaci relevantního a uživatelsky přívětivého vyhledávání. Některé z nich probereme v průběhu tohoto seriálu: N-gramy, Stopwords, Steeming, Shingle, Elision. Atd.
Podívejte se také na 1. a 2. díl tohoto seriálu.
Pokud máte nějaké dotazy, napište mi na Twitter @deniswsrosa.
Autor
- Denis Rosa, Developer Advocate, Couchbase –
.