Fuzzy matching permite que você identifique combinações não exatas do seu item alvo. É a pedra fundamental de muitas estruturas de motores de busca e uma das principais razões pelas quais pode obter resultados de pesquisa relevantes mesmo que tenha um erro de digitação na sua consulta ou um tempo verbal diferente.
Como você pode esperar, existem muitos algoritmos que podem ser usados para pesquisas difusas em texto, mas praticamente todos os frameworks de mecanismos de busca (incluindo bleve) usam principalmente a Distância Levenshtein para correspondência de strings difusas:
Distância Levenshtein
Também conhecida como Distância de edição, é o número de transformações (exclusões, inserções ou substituições) necessárias para transformar uma string de origem na de destino. Por exemplo, se o termo alvo for “livro” e o fonte estiver “de volta”, você precisará mudar o primeiro “o” para “a” e o segundo “o” para “c”, o que nos dará uma Distância Levenshtein de 2.Edit Distance é muito fácil de implementar, e é um desafio popular durante entrevistas de código (Você pode encontrar implementações Levenshtein em JavaScript, Kotlin, Java, e muitas outras aqui).
Adicionalmente, alguns frameworks também suportam a distância Damerau-Levenshtein:
Damerau-Levenshtein distance
É uma extensão da Distância Levenshtein, permitindo uma operação extra: Transposição de dois caracteres adjacentes:
Ex: TSAR para STAR
Damerau-Levenshtein distância = 1 (Trocar as posições S e T custa apenas uma operação)
Levenshtein distância = 2 (Substituir S por T e T por S)
Fuzzy correspondência e relevância
Fuzzy correspondência tem um grande efeito colateral; ele se confunde com a relevância. Embora Damerau-Levenshtein seja um algoritmo que considera a maioria dos erros de ortografia do usuário comum, ele também pode incluir um número significativo de falsos positivos, especialmente quando estamos usando uma linguagem com uma média de apenas 5 letras por palavra, como o inglês. É por isso que a maioria das estruturas dos motores de busca preferem ficar com a distância Levenshtein. Vamos ver um exemplo real:
Primeiro, vamos usar este conjunto de dados do catálogo de filmes. Recomendo-o vivamente se quiseres jogar com a pesquisa de texto completo. Depois, vamos pesquisar por filmes com “livro” no título. Um código simples seria parecido com o seguinte:
|
1
2
3
4
5
6
|
String indexName = “filmes_index”;
MatchQuery query = SearchQuery.match(“book”).field(“title”);
SearchQueryResultado = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(6));
printResults(movies);
|
O código acima trará os seguintes resultados:
|
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) O Ladrão do Livro
pontuação: 4.826942606027416
Hit Locations:
campo:título
termo:livro
fragmento:
—————————–
2) O Livro de Eli
pontuação: 4.826942606027416
Bater nos Locais:
campo:título
termo:livro
fragmento:
—————————–
3) O Livro da Vida
pontuação: 4.826942606027416
Acerta nos Locais:
campo:título
termo:livro
fragmento:
—————————–
4) Livro Preto
pontuação: 4.826942606027416
Hit Locations:
campo:título
termo:livro
fragmento:
—————————–
5) The Jungle Book
pontuação: 4.826942606027416
Hit Locations:
campo:título
termo:livro
fragmento:
—————————–
6) The Jungle Book 2
pontuação: 3.9411821308689627
Hit Locations:
campo:título
termo:livro
fragmento:
—————————–
|
Por defeito, os resultados são insensíveis a maiúsculas e minúsculas, mas pode facilmente alterar este comportamento criando novos índices com analisadores diferentes.
Agora, vamos adicionar uma capacidade de correspondência difusa à nossa consulta, definindo fuzziness como 1 (distância Levenshtein 1), o que significa que “livro” e “olhar” terão a mesma relevância.
|
1
2
3
4
5
6
|
String indexName = “filmes_index”;
MatchQuery query = SearchQuery.match(“book”).field(“title”).fuzziness(1);
SearchQueryResultado = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(6));
printResults(movies);
|
E aqui está o resultado da pesquisa 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) Gancho
pontuação: 1.1012248063242538
Locais de acerto:
campo:título
termo:gancho
fragmento:
—————————–
2) Here Comes the Boom
pontuação: 0,7786835148361213
Hit Locations:
campo:título
termo:boom
fragmento:
—————————–
3) Veja Quem Está Falando Também
pontuação: 0,7047266634351538
Acertar Locais:
campo:título
termo:olhar
fragmento:
—————————–
4) Olha quem fala
pontuação: 0,7047266634351538
Acerta nos locais:
campo:título
termo:olhar
fragmento:
—————————–
5) O Ladrão do Livro
pontuação: 0,52288117537184
Acerta nos Locais:
campo:título
termo:livro
fragmento:
—————————–
6) O Livro de Eli
pontuação: 0,52288117537184
Acerta nos locais:
campo:título
termo:livro
fragmento:
—————————–
|
Agora, o filme chamado “Hook” é o primeiro resultado de busca, que pode não ser exactamente o que o utilizador espera numa busca por “Livro”.
Como minimizar os falsos positivos durante as buscas difusas
Num mundo ideal, os utilizadores nunca fariam quaisquer erros de digitação enquanto procuravam algo. No entanto, esse não é o mundo em que vivemos, e se você quer que seus usuários tenham uma experiência agradável, você tem que lidar com pelo menos uma distância de edição de 1. Portanto, a verdadeira questão é: Como podemos fazer correspondência de strings difusas enquanto minimizamos a perda de relevância?
Podemos tirar vantagem de uma característica da maioria das estruturas de mecanismos de busca: Uma correspondência com uma distância de edição mais baixa normalmente terá uma pontuação mais alta. Essa característica nos permite combinar essas duas consultas com diferentes níveis de confusão em uma só:
|
1
2
3
4
5
6
8
|
String indexName = “filmes_index”;
Palavra da corda = “Livro”;
MatchQuery titleFuzzy = SearchQuery.match(word).fuzziness(1).field(“title”);
MatchQuery titleSimple = SearchQuery.match(word).field(“title”);
DisjunctionQuery ftsQuery = SearchQuery.disjuncts(titleSimple, titleFuzzy);
SearchQueryResultado resultado = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
novo SearchQuery(indexName, ftsQuery).highlight().limit(20)); printResults(result);
|
Aqui é o resultado da consulta fuzzy acima:
|
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) O Ladrão de Livros
pontuação: 2.398890092610849
Hit Locations:
campo:título
termo:livro
fragmento:
—————————–
campo:título
termo:livro
fragmento:
—————————–
2) O Livro de Eli
partitura: 2.398890092610849
Hit Locations:
campo:título
termo:livro
fragmento:
—————————–
campo:título
termo:livro
fragmento:
—————————–
3) O Livro da Vida
pontuação: 2.398890092610849
localizações:
campo:título
termo:livro
fragmento:
—————————–
campo:título
termo:livro
fragmento:
—————————–
4) Livro Preto
pontuação: 2.398890092610849
localizações de acerto:
campo:título
termo:livro
fragmento:
—————————–
campo:título
termo:livro
fragmento:
—————————–
5) The Jungle Book
partitura: 2.398890092610849
Hit Locations:
campo:título
termo:livro
fragmento:
—————————–
campo:título
termo:livro
fragmento:
—————————–
6) The Jungle Book 2
pontuação: 1.95868555557004688
localizações:
campo:título
termo:livro
fragmento:
—————————–
campo:título
termo:livro
fragmento:
—————————–
7) Tesouro Nacional: Livro dos Segredos
pontuação: 1.6962714808368062
localizações:
campo:título
termo:livro
fragmento:
—————————–
campo:título
termo:livro
fragmento:
—————————–
8) Torta Americana Presentes: O Livro do Amor
pontuação: 1.51719191317611584
acerta nos locais:
campo:título
termo:livro
fragmento:
—————————–
campo:título
termo:livro
fragmento:
—————————–
9) gancho
pontuação: 0.5052232518679681
localizações de acerto:
campo:título
termo:gancho
fragmento:
—————————–
10) Here Comes the Boom
pontuação: 0,357246781294941
Acertar nos locais:
campo:título
termo:árvore
fragmento:
—————————–
11) Veja Quem Está Falando Também
pontuação: 0,32331663301992025
Acertar Locais:
campo:título
termo:olhar
fragmento:
—————————–
12) Olha quem fala
pontuação: 0,32331663301992025
Acerta nos locais:
campo:título
termo:olhar
fragmento:
—————————–
|
Como pode ver, este resultado está muito mais próximo do que o utilizador poderia esperar. Note que estamos usando uma classe chamada DisjunctionQuery agora, disjunções são um equivalente ao operador “OR” em SQL.
O que mais poderíamos melhorar para reduzir o efeito colateral negativo de um algoritmo de correspondência fuzzy? Vamos reanalisar o nosso problema para entender se ele precisa de mais melhorias:
Já sabemos que as pesquisas fuzzy podem produzir alguns resultados inesperados (ex. Book -> Look, Hook). No entanto, uma pesquisa com um único termo é geralmente uma consulta terrível, pois mal nos dá uma dica do que exatamente o usuário está tentando realizar.
Even Google, que tem indiscutivelmente um dos algoritmos de pesquisa fuzzy mais desenvolvidos em uso, não sabe exatamente o que estou procurando quando procuro por “tabela”:
Então, qual é o comprimento médio das palavras-chave em uma consulta de pesquisa? Para responder a esta pergunta, vou mostrar um gráfico da apresentação de Rand Fishkin em 2016. (Ele é um dos gurus mais famosos do mundo SEO)
De acordo com o gráfico acima, ~80% das buscas têm 2 ou mais palavras-chave, então vamos tentar buscar o filme “Black Book” usando o fuzziness 1:
|
1
2
3
4
5
6
|
String indexName = “filmes_index”;
MatchQuery query = SearchQuery.match(“Black Book”).field(“title”).fuzziness(1);
SearchQueryResultado resultado = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(12));
printResults(movies);
|
Resultado:
|
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) Livro Preto
pontuação: 0.6946442424065404
Locais de acerto:
campo:título
termo:livro
fragmento:
—————————–
campo:título
termo:preto
fragmento:
—————————–
2) gancho
pontuação: 0.40139742528039857
localizações de acerto:
campo:título
termo:gancho
fragmento:
—————————–
3) Atacar o bloco
pontuação: 0,2838308365090324
Atacar os locais:
campo:título
termo:bloco
fragmento:
—————————–
4) Here Comes the Boom
pontuação: 0.2838308365090324
Hit Locations:
campo:título
termo:boom
fragmento:
—————————–
5) Olha quem também fala
pontuação: 0,25687349813115684
Hit Locations:
campo:título
termo:olhar
fragmento:
—————————–
6) Olha quem fala
pontuação: 0,25687349813115684
Acerta nos locais:
campo:título
termo:olhar
fragmento:
—————————–
7) Grosse Pointe Blank
pontuação: 0,2317469073782136
Acertar nos locais:
campo:título
termo:em branco
fragmento:
—————————–
8) The Book Thief
pontuação: 0.19059065534780495
Hit Locations:
campo:título
termo:livro
fragmento:
—————————–
9) O Livro de Eli
pontuação: 0.19059065534780495
Bater nos Locais:
campo:título
termo:livro
fragmento:
—————————–
10) O Livro da Vida
pontuação: 0.19059065534780495
Acerta nos Locais:
campo:título
termo:livro
fragmento:
—————————–
11) The Jungle Book
pontuação: 0.19059065534780495
Hit Locations:
campo:título
termo:livro
fragmento:
—————————–
12) De volta ao futuro
pontuação: 0.17061000968368
Hit Locations:
campo:título
termo:voltar
fragmento:
—————————–
|
Nada mau. Temos o filme que estávamos procurando como primeiro resultado. Entretanto, uma consulta de disjunção ainda traria um conjunto melhor de resultados.
Mas ainda assim, parece que temos uma nova propriedade agradável aqui; o efeito colateral de fuzziness matching diminui ligeiramente à medida que o número de palavras-chave aumenta. Uma pesquisa por “Black Book” com fuzziness 1 ainda pode trazer resultados como “back look” ou “lack cook” (algumas combinações com distância de edição 1), mas é improvável que estes sejam títulos reais de filmes.
Uma pesquisa por “livro eli” com fuzziness 2 ainda traria como o terceiro resultado:
|
1
2
3
4
5
6
|
String indexName = “filmes_index”;
MatchQuery query = SearchQuery.match(“book eli”).field(“title”).fuzziness(2);
SearchQueryResultado resultado = 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
pontuação: 0.030723793900031805
Hit Locations:
campo:título
termo:madeira
fragmento:
—————————–
campo:título
termo:ed
fragmento:
—————————–
2) Homem de Tai Chi
pontuação: 0,0271042761982626
localizações:
campo:título
termo:chi
fragmento:
—————————–
campo:título
termo:tai
fragmento:
—————————–
3) O Livro de Eli
pontuação: 0.02608335441670756
localizações:
campo:título
termo:eli
fragmento:
—————————–
campo:título
termo:livro
fragmento:
—————————–
4) A Boa Mentira
pontuação: 0,02439822770591834
acerta nos locais:
campo:título
termo:mentira
fragmento:
—————————–
campo:título
termo:bom
fragmento:
—————————–
|
No entanto, como a palavra média em inglês tem 5 letras, eu NÃO recomendaria usar uma distância de edição maior que 2, a menos que o usuário esteja procurando por palavras longas que sejam fáceis de digitar mal, como “Schwarzenegger” por exemplo (pelo menos para não alemães ou não austríacos).
Conclusão
Neste artigo, discutimos a correspondência de fuzziness e como superar seu maior efeito colateral sem mexer na sua relevância. Lembre-se, o fuzzy matching é apenas uma das muitas características que você deve aproveitar ao implementar uma pesquisa relevante e de fácil utilização. Nós vamos discutir algumas delas durante esta série: N-Grams, Stopwords, Steeming, Shingle, Elision. Etc.
Check out also the Part 1 and Part 2 of this series.
Entretanto, se você tiver alguma pergunta, tweet me at @deniswsrosa.
Author
- Denis Rosa, Developer Advocate, Couchbase –
