O que é Fuzzy Matching e como usá-lo corretamente

Você já se perguntou: "O que é fuzzy matching?" A correspondência difusa permite que você identifique correspondências não exatas do seu item de destino. É a pedra fundamental de muitas estruturas de mecanismos de pesquisa e um dos principais motivos pelos quais você pode obter resultados de pesquisa relevantes mesmo que tenha um erro de digitação na consulta ou um tempo verbal diferente.

Como era de se esperar, há muitos algoritmos de busca difusa que podem ser usados para texto, mas praticamente todas as estruturas de mecanismos de busca (incluindo sangrar) usam principalmente a distância Levenshtein para correspondência de strings difusas:

Distância de Levenshtein

Também conhecido como Editar distânciaé o número de transformações (exclusões, inserções ou substituições) necessárias para transformar uma cadeia de caracteres de origem na cadeia de caracteres de destino. Para um exemplo de pesquisa difusa, se o termo de destino for "book" e a fonte for "back", você precisará alterar o primeiro "o" para "a" e o segundo "o" para "c", o que nos dará uma distância de Levenshtein de 2.Você pode encontrar implementações de Levenshtein em JavaScript, Kotlin, Java e muitos outros aqui).

Além disso, algumas estruturas também suportam a distância Damerau-Levenshtein:

Distância Damerau-Levenshtein

É uma extensão da distância de Levenshtein, permitindo uma operação extra: Transposição de dois caracteres adjacentes:

Ex: TSAR para STAR

Distância Damerau-Levenshtein = 1 (A troca das posições S e T custa apenas uma operação)

Distância de Levenshtein = 2  (Substituir S por T e T por S)

Correspondência e relevância difusa

A correspondência difusa tem um grande efeito colateral: ela prejudica a relevância. Embora Damerau-Levenshtein seja um algoritmo de correspondência difusa que considera a maioria dos erros ortográficos comuns do usuário, ele também pode incluir um número significativo de falsos positivosespecialmente quando estamos usando uma linguagem com um média de apenas 5 letras por palavracomo o inglês. É por isso que a maioria das estruturas dos mecanismos de busca prefere usar a distância de Levenshtein. Vamos ver um exemplo real de correspondência fuzzy:

Primeiro, vamos usar esse conjunto de dados do catálogo de filmes. Eu o recomendo muito se você quiser brincar com a pesquisa de texto completo. Em seguida, vamos pesquisar filmes com "livro" no título. Um código simples seria parecido com o seguinte:

O código acima produzirá os seguintes resultados:

Por padrão, os resultados não diferenciam maiúsculas de minúsculas, mas você pode alterar facilmente esse comportamento criando novos índices com analisadores diferentes.

Agora, vamos adicionar um recurso de correspondência difusa à nossa consulta, definindo a imprecisão como 1 (distância de Levenshtein 1), o que significa que "livro" e "olhar" terá a mesma relevância.

E aqui está o resultado da pesquisa difusa:

Agora, o filme chamado "Gancho" é o primeiro resultado da pesquisa, que pode não ser exatamente o que o usuário está esperando em uma pesquisa por "Livro".

Como minimizar os falsos positivos durante as pesquisas difusas

 Em um mundo ideal, os usuários nunca cometeriam erros de digitação ao pesquisar algo. No entanto, esse não é o mundo em que vivemos e, se você quiser que seus usuários tenham uma experiência agradável, terá de lidar com pelo menos uma distância de edição de 1. Portanto, a verdadeira questão é: como podemos fazer a correspondência de strings fuzzy minimizando a perda de relevância?

Podemos tirar proveito de uma característica da maioria das estruturas de mecanismos de pesquisa: Uma correspondência com uma distância de edição menor geralmente terá uma pontuação mais alta. Essa característica nos permite combinar essas duas consultas com diferentes níveis de imprecisão em uma só:

Aqui está o resultado da consulta fuzzy acima:

Como você pode ver, esse resultado está muito mais próximo do que o usuário poderia esperar. Observe que estamos usando uma classe chamada DisjunctionQuery agora, pois as disjunções são equivalentes a "OU" no SQL.

O que mais poderíamos melhorar para reduzir o efeito colateral negativo de um algoritmo de correspondência difusa? Vamos reanalisar nosso problema para entender se ele precisa de mais melhorias:

Já sabemos que as pesquisas difusas podem produzir alguns resultados inesperados (por exemplo, Book -> Look, Hook). No entanto, uma pesquisa de termo único geralmente é uma consulta terrível, pois mal nos dá uma dica do que exatamente o usuário está tentando realizar.

Mesmo o Google, que tem um dos algoritmos de pesquisa difusa mais desenvolvidos em uso, não sabe exatamente o que estou procurando quando pesquiso "tabela":

Então, qual é o tamanho médio das palavras-chave em uma consulta de pesquisa? Para responder a essa pergunta, mostrarei um gráfico de Apresentação de Rand Fishkin em 2016. (Ele é um dos gurus mais famosos do mundo de SEO)

De acordo com o gráfico acima, ~80% das consultas de pesquisa têm 2 ou mais palavras-chave, portanto, vamos tentar pesquisar o filme "Black Book" usando a fuzziness 1:

Resultado:

Nada mal. Obtivemos o filme que estávamos procurando como o primeiro resultado. No entanto, uma consulta de disjunção ainda traria um conjunto melhor de resultados.

Mas, ainda assim, parece que temos uma nova propriedade interessante aqui; o efeito colateral da correspondência de imprecisão diminui ligeiramente à medida que o número de palavras-chave aumenta. Uma busca por "Livro preto" com imprecisão 1 ainda pode trazer resultados como back look ou lack cook (algumas combinações com edit distance 1), mas é improvável que esses sejam títulos de filmes reais.

Uma busca por "livro eli" com a imprecisão 2 ainda o traria como o terceiro resultado:

Entretanto, como a palavra média em inglês tem 5 letras, eu NÃO recomendamos o uso de uma distância de edição maior que 2, a menos que o usuário esteja pesquisando palavras longas e fáceis de serem escritas incorretamente, como "Schwarzenegger", por exemplo (pelo menos para quem não é alemão ou austríaco).

Conclusão

Neste artigo, discutimos a correspondência difusa e como superar seu principal efeito colateral sem prejudicar sua relevância. Lembre-se de que a correspondência difusa é apenas um dos muitos recursos que você deve aproveitar ao implementar uma pesquisa relevante e fácil de usar. Vamos discutir alguns deles durante esta série: N-Gramas, Stopwords, Steeming, Shingle, Elision. Etc.

Confira também o Parte 1 e Parte 2 desta série.

Enquanto isso, se você tiver alguma dúvida, envie-me um tweet para @deniswsrosa.