Como usar buscas difusas no Elasticsearch

Introdução

Buscar em linguagem natural é inerentemente impreciso. Como os computadores não compreendem linguagem natural, existem várias abordagens de busca, cada uma com suas vantagens e desvantagens. Lucene, a tecnologia que fundamenta o Elasticsearch, é um canivete suíço composto por muitas ferramentas de processamento de texto. Cada ferramenta é uma heurística, um atalho algorítmico em vez de uma verdadeira compreensão linguística. Algumas dessas ferramentas, como o stemmer Snowball e o analisador fonético Metaphone, são bastante sofisticadas, imitando aspectos gramaticais e fonéticos da compreensão da linguagem, respectivamente. Outras são mais básicas, como o tipo de consulta prefixo, que simplesmente corresponde às letras iniciais das palavras. Consultas fuzzy ficam em um nível intermediário de sofisticação; elas encontram palavras que precisam de no máximo um certo número de modificações de caracteres, chamadas de 'edits', para corresponder à consulta. Por exemplo, uma busca fuzzy por 'ax' corresponderia à palavra 'axe', pois basta uma exclusão, removendo o 'e', para que as duas palavras coincidam.

Uma combinação simples fuzzy

Consultas fuzzy podem ser feitas facilmente adicionando argumentos ao tipo de consulta match, como no exemplo abaixo. No exemplo, a busca por 'vaacuum', com um A extra, ainda deve retornar o produto 'Vacuum'. O parâmetro fuzziness especifica que os resultados devem corresponder com uma distância máxima de edição de 2. Note que fuzziness deve ser usado apenas com valores 1 ou 2, ou seja, no máximo 2 edições entre a consulta e um termo no documento são permitidas. Diferenças maiores são muito mais custosas para computar e não são processadas pelo Lucene. A documentação oficial ainda menciona valores decimais para fuzziness, como 0,5, mas esses valores estão obsoletos e são mais difíceis de interpretar.

# Crie o índice
PUT /fuzzy_products
# Crie o mapeamento do produto
PUT /fuzzy_products/product/_mapping
{
  "product": {
    "propriedades": {
      "name": {
        "type": "string",
        "analyzer": "simple"
      }
    }
  }
}
# Carregar alguns documentos
PUT /fuzzy_products/product/1
{"name": "Vacuum Cleaner"}
PUT /fuzzy_products/product/2
{"name": "Turkey Baster"}
# Faça uma busca fuzzy!
POST /fuzzy_products/product/_search
{
  "query": {
    "match": {
      "name": {
        "query": "Vacuummm",
        "fuzziness": 2,
        "prefix_length": 1
      }
    }
  }
}

Determinando a distância de edição

A métrica usada pelas consultas fuzzy para determinar uma correspondência é a fórmula da distância de Damerau-Levenshtein. Simplificando, a distância de Damerau-Levenshtein entre dois textos é o número de inserções, deleções, substituições e transposições necessárias para que uma string coincida com a outra. Por exemplo, a distância de Levenshtein entre as palavras “ax” e “axe” é 1, devido à única deleção necessária.

A fórmula de Damerau-Levenshtein é uma modificação da fórmula clássica de Levenshtein, adicionando a transposição como operação válida. Ambas são suportadas, sendo Damerau-Levenshtein o padrão, e Levenshtein clássico selecionável definindo transpositions como false na consulta. A utilidade das transposições fica clara ao comparar as strings 'aex' e 'axe'. Usando a fórmula clássica, 'aex' está a duas edições de distância; o 'e' deve ser excluído e depois inserido no lugar correto. Já em Damerau-Levenshtein, uma única operação de troca entre 'e' e 'x' basta. Isso mostra por que Damerau-Levenshtein faz mais sentido na maioria dos casos.

Ao lidar com buscas fuzzy, é importante entender que no Elasticsearch o texto é primeiro processado por um analisador antes de ser disponibilizado para busca. Os dados indexados são transformados em 'termos', as unidades pesquisáveis no banco. São os termos analisados (explicados em Elasticsearch de Baixo para Cima), não os documentos armazenados, que são buscados. Isso significa que o texto da consulta pode ser comparado a termos inesperados devido à análise, gerando resultados confusos. Se sinônimos estiverem ativados, eles podem ser correspondidos mesmo que a palavra não apareça no texto original. Por exemplo, consultas fuzzy em campos analisados por ngrams podem gerar resultados estranhos, pois ngrams dividem palavras em muitas combinações pequenas de letras, muitas a uma ou duas edições de distância, embora as palavras sejam diferentes. Usar um analisador snowball faz com que uma busca fuzzy por 'running' seja reduzida a 'run', mas não corresponderá a 'runninga', pois 'run' está a mais de 2 edições de 'runninga'. Por isso, muitas vezes é melhor usar o analisador simples para textos com consultas fuzzy, possivelmente desativando sinônimos. Abaixo há um diagrama mostrando uma consulta fuzzy contra um documento analisado por snowball.

Os diferentes tipos de buscas fuzzy

O Elasticsearch suporta vários tipos de buscas fuzzy, e as diferenças podem ser confusas. A lista abaixo tenta esclarecer esses tipos.

• Consulta match + opção fuzziness: Adicionar o parâmetro fuzziness a uma consulta match transforma-a em uma consulta fuzzy. O texto da consulta é analisado antes da busca.
• Consulta fuzzy: Geralmente deve ser evitada. Funciona como uma consulta de termo e não analisa o texto da consulta.
• fuzzy_like_this / fuzzy_like_this_field: Uma consulta more_like_this que suporta fuzziness e possui algoritmo de pontuação ajustado para lidar melhor com resultados fuzzy.*
• Sugestores: Não são um tipo de consulta, mas uma operação separada (baseada em consultas fuzzy) que pode ser executada junto com uma consulta ou independentemente. São ótimos para funcionalidades do tipo 'você quis dizer'.

A consulta match com fuzziness é a mais versátil. A consulta fuzzy tem o mesmo comportamento, mas não permite análise do texto, sendo um subconjunto da match, o que a torna menos útil.

Consultas fuzzy_like_this (FLT) são úteis para recomendações baseadas em textos grandes que podem conter erros ortográficos ou imprecisões. Existem duas consultas: fuzzy_like_this e fuzzy_like_this_field, que simplifica a sintaxe para um único campo. Elas usam o parâmetro like_text, um texto grande, e tentam encontrar documentos 'semelhantes'. Os termos são ponderados pela frequência no like_text, com ajustes especiais para combinar termos. FLT funciona melhor quando há muitos erros ortográficos; caso contrário, more_like_this padrão tem melhor desempenho. Mais detalhes na documentação oficial.

Sugestores são úteis quando o usuário digita 'New Yrok' querendo dizer 'New York'. Aplicativos podem mostrar uma caixa 'você quis dizer' recomendando correção. Para buscas com digitação antecipada, a API de completação oferece melhor desempenho devido à sensibilidade à latência. Mais informações na página de sugestores.

Considerações de desempenho

Embora a implementação da distância de Levenshtein do Lucene seja avançada e rápida, ainda é muito mais lenta que uma consulta match simples. O tempo cresce com o número de termos únicos no índice. Ou seja, o critério principal para buscas fuzzy é quantos termos únicos existem nos campos pesquisados, não quantos documentos são retornados. Por exemplo, 100 documentos com 10.000 palavras únicas cada resultam em busca mais lenta que 10.000 documentos com 100 palavras únicas.

Isso ocorre porque a consulta match verifica rapidamente o índice de termos, uma estrutura interna do Lucene, usando busca binária, que é rápida mesmo para dicionários grandes. Consultas fuzzy usam um algoritmo mais avançado com um DFA que processa muitos termos, sendo sempre mais lento. Por exemplo, uma busca fuzzy na Wikipédia em inglês leva cerca de 320ms para o termo “history” com min_similarity 2, enquanto uma busca match simples leva 35ms. Com min_similarity 1, a busca fuzzy leva 150ms. Esses testes não são estatisticamente rigorosos e podem variar conforme a aplicação. A Wikipédia tem muitos mais termos que muitos casos de uso comuns.

O desempenho melhora muito exigindo que as correspondências tenham prefixos exatos com a consulta, reduzindo o espaço de busca, mas não encontrando palavras com erro no início. Quanto maior o prefixo, maior a velocidade. Especificar prefix_length 1 reduz a busca de 320ms para 104ms. Aumentar esse valor traz ganhos adicionais. Geralmente, recomenda-se exigir prefixo para grandes conjuntos de dados para evitar lentidão, que pode chegar a centenas de milissegundos.

A configuração max_expansions, que limita o número máximo de termos que a consulta fuzzy pode corresponder antes de parar, também afeta o desempenho. Reduzir esse número pode impedir que resultados válidos sejam encontrados devido à parada precoce. Esse limite funciona no nível do shard, então mesmo com valor 1, múltiplos termos podem coincidir em shards diferentes, o que pode dar a impressão de que max_expansions não está ativo. Contar termos únicos retornados não é forma válida de verificar o funcionamento.

Alternativas ao correspondimento fuzzy

O correspondimento fuzzy nem sempre é a melhor ferramenta; correspondências imprecisas podem ser encontradas por outras técnicas. O plugin de análise fonética oferece ferramentas interessantes para aproximação, como o analisador Metaphone, que encontra palavras com sons semelhantes. Por exemplo, para garantir que palavras como run e ran sejam consideradas equivalentes, um analisador inteligente como o Snowball é preferível. Alternativamente, para verificar erros ortográficos, a análise N-grama, conforme descrito neste tutorial, pode ser mais rápida no momento da consulta, dependendo do conjunto de dados. No entanto, N-grams aumentam o uso de armazenamento/memória, exigem mais processamento no índice e geram muitos falsos positivos após bons resultados.

Mais leitura

• Para uma análise mais profunda do desempenho das consultas fuzzy no Elasticsearch, Mike McCandless, colaborador núcleo do Lucene, escreveu um post fascinante no post do blog. Há também um vídeo, Finite State Automata in Lucene and Solr, de uma apresentação de Dawid Weiss que aborda Levenshtein e outros autômatos no Lucene.
• Se quiser saber mais sobre Levenshtein Automata, Nick Johnson tem um ótimo post chamado Damn Cool Algorithms: Levenshtein Automata.