Dopasowanie rozmyte pozwala na identyfikację niedokładnych dopasowań elementu docelowego. Jest to kamień węgielny wielu frameworków wyszukiwarek i jeden z głównych powodów, dla których można uzyskać odpowiednie wyniki wyszukiwania, nawet jeśli masz literówkę w zapytaniu lub inny czasownik.
Jak można się spodziewać, istnieje wiele algorytmów, które mogą być użyte do wyszukiwania rozmytego w tekście, ale praktycznie wszystkie wyszukiwarki (w tym bleve) używają głównie Dystansu Levenshteina do rozmytego dopasowywania łańcuchów znaków:
Odległość Levenshteina
Znana również jako Odległość Edycji, jest to liczba transformacji (usunięć, wstawek lub substytucji) wymaganych do przekształcenia łańcucha źródłowego w docelowy. Na przykład, jeśli terminem docelowym jest „książka”, a źródłem jest „z powrotem”, będziesz musiał zmienić pierwsze „o” na „a” i drugie „o” na „c”, co da nam odległość Levenshtein Distance równą 2.Edit Distance jest bardzo łatwy do wdrożenia i jest popularnym wyzwaniem podczas wywiadów z kodem (Możesz znaleźć implementacje Levenshtein w JavaScript, Kotlin, Java i wiele innych tutaj).
Dodatkowo, niektóre frameworki obsługują również odległość Damerau-Levenshtein:
Damerau-Levenshtein distance
Jest to rozszerzenie do Levenshtein Distance, pozwalające na jedną dodatkową operację: Transpozycja dwóch sąsiednich znaków:
Ex: TSAR to STAR
Damerau-Levenshtein distance = 1 (Zamiana pozycji S i T kosztuje tylko jedną operację)
Levenshtein distance = 2 (Zamień S na T i T na S)
Fuzzy matching and relevance
Fuzzy matching has one big side effect; it messes up with relevance. Chociaż Damerau-Levenshtein jest algorytm, który bierze pod uwagę większość wspólnych użytkowników błędnej pisowni, może również zawierać znaczną liczbę fałszywych pozytywów, zwłaszcza gdy używamy języka ze średnią tylko 5 liter na słowo, takich jak angielski. Dlatego też większość frameworków wyszukiwarek woli trzymać się odległości Levenshteina. Zobaczmy tego prawdziwy przykład:
Po pierwsze, użyjemy tego zestawu danych katalogu filmowego. Gorąco polecam, jeśli chcesz się pobawić wyszukiwaniem pełnotekstowym. Następnie, wyszukajmy filmy z „książką” w tytule. Prosty kod wyglądałby następująco:
|
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);
|
Powyższy kod przyniesie następujące wyniki:
|
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
score: 4.826942606027416
Lokalizacje trafień:
pole:tytuł
termin:książka
fragment:
—————————–
2) The Book of Eli
score: 4.826942606027416
Hit Locations:
pole:tytuł
termin:książka
fragment:
—————————–
3) The Book of Life
score: 4.826942606027416
Hit Locations:
pole:tytuł
termin:książka
fragment:
—————————–
4) Black Book
score: 4.826942606027416
Hit Locations:
pole:tytuł
termin:książka
fragment:
—————————–
5) The Jungle Book
score: 4.826942606027416
Hit Locations:
pole:tytuł
termin:książka
fragment:
—————————–
6) The Jungle Book 2
score: 3.9411821308689627
Hit Locations:
pole:tytuł
termin:książka
fragment:
—————————–
|
Domyślnie wyniki nie uwzględniają wielkości liter, ale można łatwo zmienić to zachowanie, tworząc nowe indeksy z różnymi analizatorami.
Teraz dodajmy do naszego zapytania możliwość dopasowania rozmytego, ustawiając rozmycie jako 1 (odległość Levenshteina 1), co oznacza, że „książka” i „wygląd” będą miały taką samą trafność.
|
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 oto wynik wyszukiwania rozmytego:
|
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) Hak
punktacja: 1.1012248063242538
Lokalizacje trafień:
pole:tytuł
termin:hak
fragment:
—————————–
2) Here Comes the Boom
score: 0.7786835148361213
Hit Locations:
field:title
term:boom
fragment:
—————————–
3) Look Who’s Talking Too
score: 0.7047266634351538
Hit Locations:
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:
pole:tytuł
termin:książka
fragment:
—————————–
6) The Book of Eli
score: 0.52288117537184
Hit Locations:
pole:tytuł
termin:książka
fragment:
—————————–
|
Teraz, film o nazwie „Hook” jest pierwszym wynikiem wyszukiwania, który może nie być dokładnie tym, czego oczekuje użytkownik szukający „książki”.
Jak zminimalizować fałszywe wyniki podczas wyszukiwania rozmytego
W idealnym świecie użytkownicy nigdy nie popełnialiby literówek podczas wyszukiwania. Jednak nie jest to świat, w którym żyjemy i jeśli chcesz, aby użytkownicy mieli przyjemne doświadczenie, musisz obsługiwać przynajmniej odległość edycyjną równą 1. Dlatego prawdziwe pytanie brzmi: Jak możemy dokonać rozmytego dopasowania ciągów znaków przy jednoczesnym zminimalizowaniu utraty trafności? Dopasowanie z mniejszą odległością edycyjną będzie zazwyczaj wyżej punktowane. Ta cecha pozwala nam połączyć te dwa zapytania o różnych poziomach rozmytości w jedno:
|
1
2
3
4
5
6
7
8
|
String indexName = „movies_index”;
String word = „Książka”;
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);
|
Tutaj znajduje się wynik powyższego zapytania rozmytego:
|
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
score: 2.398890092610849
Lokalizacje trafień:
pole:tytuł
termin:książka
fragment:
—————————–
field:title
term:book
fragment:
—————————–
2) The Book of Eli
score: 2.398890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
3) The Book of Life
score: 2.398890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) Black Book
score: 2.398890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
5) The Jungle Book
score: 2.398890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
6) The Jungle Book 2
score: 1.958685557004688
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: The Book of Love
score: 1.517191317611584
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
9) Hook
score: 0.5052232518679681
Hit Locations:
pole:tytuł
termin:hak
fragment:
—————————–
10) Here Comes the Boom
wynik: 0.357246781294941
Hit Locations:
field:title
term:tree
fragment:
—————————–
11) Look Who’s Talking Too
score: 0.32331663301992025
Hit Locations:
field:title
term:look
fragment:
—————————–
12) Look Who’s Talking
score: 0.32331663301992025
Hit Locations:
field:title
term:look
fragment:
—————————–
|
Jak widać, wynik ten jest znacznie bliższy temu, czego może oczekiwać użytkownik. Zauważ, że używamy teraz klasy zwanej DisjunctionQuery, disjunctions są odpowiednikiem operatora „OR” w SQL.
Co jeszcze moglibyśmy poprawić, aby zmniejszyć negatywny efekt uboczny algorytmu dopasowania rozmytego? Przeanalizujmy ponownie nasz problem, aby zrozumieć, czy wymaga on dalszych ulepszeń:
Wiemy już, że wyszukiwania rozmyte mogą dawać pewne nieoczekiwane wyniki (np. Książka -> Szukaj, Hook). Jednak wyszukiwanie pojedynczego terminu jest zazwyczaj okropnym zapytaniem, ponieważ ledwie daje nam wskazówkę, co dokładnie użytkownik próbuje osiągnąć.
Nawet Google, który ma prawdopodobnie jeden z najbardziej rozwiniętych algorytmów wyszukiwania rozmytego w użyciu, nie wie dokładnie, czego szukam, gdy wyszukuję „stół”:
Więc, jaka jest średnia długość słów kluczowych w zapytaniu wyszukiwania? Aby odpowiedzieć na to pytanie, pokażę wykres z prezentacji Randa Fishkina z 2016 roku. (Jest on jednym z najbardziej znanych guru w świecie SEO)
Według powyższego wykresu, ~80% zapytań wyszukiwania ma 2 lub więcej słów kluczowych, więc spróbujmy wyszukać film „Black Book” używając rozmycia 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) Czarna księga
punktacja: 0.6946442424065404
Lokalizacje trafień:
pole:tytuł
termin:książka
fragment:
—————————–
field:title
term:black
fragment:
—————————–
2) Hook
score: 0.40139742528039857
Hit Locations:
pole:tytuł
termin:hak
fragment:
—————————–
3) Attack the Block
score: 0.2838308365090324
Hit Locations:
pole:tytuł
termin:blok
fragment:
—————————–
4) Here Comes the Boom
score: 0.2838308365090324
Hit Locations:
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
score: 0.25687349813115684
Hit Locations:
field:title
term:look
fragment:
—————————–
7) Grosse Pointe Blank
score: 0.2317469073782136
Hit Locations:
field:title
term:blank
fragment:
—————————–
8) The Book Thief
score: 0.19059065534780495
Hit Locations:
pole:tytuł
termin:książka
fragment:
—————————–
9) The Book of Eli
score: 0.19059065534780495
Hit Locations:
pole:tytuł
termin:książka
fragment:
—————————–
10) The Book of Life
score: 0.19059065534780495
Hit Locations:
field:title
term:book
fragment:
—————————–
11) The Jungle Book
score: 0.19059065534780495
Hit Locations:
field:title
term:book
fragment:
—————————–
12) Back to the Future
score: 0.17061000968368
Hit Locations:
pole:title
termin:back
fragment:
—————————–
|
Nieźle. Otrzymaliśmy film, którego szukaliśmy jako pierwszy wynik. Jednak zapytanie typu disjunction nadal przyniosłoby lepszy zestaw wyników.
Ale nadal, wygląda na to, że mamy tutaj nową fajną właściwość; efekt uboczny dopasowania rozmytości nieznacznie maleje wraz ze wzrostem liczby słów kluczowych. Wyszukiwanie „Black Book” z fuzziness 1 może nadal przynieść wyniki takie jak back look lub lack cook (niektóre kombinacje z edit distance 1), ale są one mało prawdopodobne, aby być prawdziwe tytuły filmów.
A search for „book eli” with fuzziness 2 would still bring it as the third result:
|
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
score: 0.030723793900031805
Lokalizacje trafień:
field:title
term:wood
fragment:
—————————–
field:title
term:ed
fragment:
—————————–
2) Man of Tai Chi
score: 0.0271042761982626
Hit Locations:
pole:tytuł
termin:chi
fragment:
—————————–
field:title
term:tai
fragm:
—————————–
3) The Book of Eli
score: 0.02608335441670756
Hit Locations:
field:title
term:eli
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) The Good Lie
score: 0.02439822770591834
Hit Locations:
pole:tytuł
termin:kłamstwo
fragment:
—————————–
field:title
term:good
fragment:
—————————–
|
Jednakże, ponieważ przeciętne angielskie słowo ma długość 5 liter, NIE zalecałbym używania odległości edycyjnej większej niż 2, chyba że użytkownik szuka długich słów, które łatwo jest błędnie przeliterować, jak na przykład „Schwarzenegger” (przynajmniej dla nie-Niemców lub nie-Austriaków).
Podsumowanie
W tym artykule, omówiliśmy dopasowanie rozmyte i jak przezwyciężyć jego główny efekt uboczny, nie psując jego trafności. Należy pamiętać, że dopasowanie rozmyte jest tylko jedną z wielu funkcji, które należy wykorzystać podczas wdrażania trafnego i przyjaznego dla użytkownika wyszukiwania. W tej serii omówimy kilka z nich: N-Gramy, Stopwords, Steeming, Shingle, Elision. Etc.
Sprawdź również Część 1 i Część 2 tej serii.
W międzyczasie, jeśli masz jakieś pytania, tweetnij do mnie na @deniswsrosa.
Autor
- Denis Rosa, Developer Advocate, Couchbase –
.