Sua pesquisa retornou: implementação de pesquisa difusa

Todos cometemos erros: nesse caso, estamos falando de consultas de pesquisa. O número de sites para venda de bens e serviços está crescendo junto com as necessidades dos usuários, mas eles nem sempre conseguem encontrar o que estão procurando - apenas porque inserem incorretamente o nome do produto necessário. A solução para esse problema é alcançada através da implementação de uma pesquisa difusa, ou seja, usando o algoritmo para encontrar os valores mais próximos, levando em consideração possíveis erros ou erros de digitação do usuário. O escopo dessa pesquisa é amplo o suficiente - conseguimos trabalhar na pesquisa de uma grande loja on-line no segmento de varejo de alimentos.

Estado da pesquisa inicial

A loja online foi desenvolvida na plataforma 1C-Bitrix: Site Management. Para implementar a pesquisa, usamos o módulo de pesquisa bitrix padrão e o mecanismo de texto completo sphinxsearch. Na pesquisa sphinx, foi utilizado o tipo de índice Tempo Real (RT), que não requer uma fonte de dados estática, mas pode ser preenchido a qualquer momento em tempo real. Isso permite que você atualize com flexibilidade o índice de pesquisa sem reindexá-lo completamente. Como o índice RT utiliza apenas o SphinxQL como protocolo de consulta, a integração foi realizada por meio dele. O SphinxQL é um protocolo de consulta do tipo mysql que implementa a capacidade de conectar-se através de clientes mysql padrão, fornecendo sintaxe sql com algumas limitações e suas próprias peculiaridades. O módulo de pesquisa usa consultas de seleção / inserção / substituição / exclusão.

No sistema bitrix, foi realizado o processo de indexação dos dados de mercadorias, categorias e marcas. As informações sobre essas entidades foram transferidas para a esfinge, que por sua vez atualizou o índice RT. Quando os dados são atualizados na loja online, é acionado um evento que atualiza os dados no Sphinx. A consistência dos dados é realizada através do identificador da entidade na loja online.

Quando um usuário pesquisa em uma loja online, o sistema faz uma solicitação com uma frase de pesquisa no Sphinx e obtém identificadores de entidades, também seleciona as informações do banco de dados e forma uma página com os resultados dos resultados da pesquisa.
No momento em que a solução para o problema de pesquisa difusa começou, o esquema geral da arquitetura de pesquisa no projeto era o seguinte:

Seleção de tecnologia

Nossa tarefa era adivinhar a solicitação do usuário, que pode conter erros de digitação. Para fazer isso, precisamos analisar cada palavra na solicitação e decidir se o usuário a escreveu corretamente ou não. Em caso de erro, as opções mais adequadas devem ser selecionadas. Determinar a grafia correta das palavras é impossível sem um banco de dados de palavras e formas de palavras do idioma em que queremos adivinhar. Simplisticamente, esse banco de dados pode ser chamado de dicionário - era ele quem precisávamos.

Para selecionar opções de substituição de palavras digitadas com erro, foi escolhida a popular fórmula de cálculo de distância Damerau - Levenshtein. Esta fórmula é um algoritmo para comparar duas palavras. O resultado da comparação é o número de operações para converter uma palavra em outra. Inicialmente, a distância de Levenshtein envolve o uso de três operações:

• inserção
• exclusão
• substituição

A distância Damerau-Levenshtein é uma versão estendida da distância Levenshtein e acrescenta outra operação: transposição, isto é, uma permutação de dois caracteres adjacentes.

Assim, o número de operações recebidas se torna o número de erros cometidos pelo usuário ao escrever a palavra. Escolhemos a limitação de dois erros, pois um número maior não fazia sentido: nesse caso, temos muitas opções de substituição, o que aumenta a probabilidade de uma falha.

Para uma pesquisa mais relevante de variantes de palavras semelhantes no som, foi utilizada a função metafone - essa função converte uma palavra em sua forma fonética. Infelizmente, o metafone funciona apenas com as letras do alfabeto inglês; portanto, antes de calcular a forma fonética, transliteramos a palavra. O valor da forma fonética é armazenado no dicionário e também é calculado na solicitação do usuário. Os valores resultantes são comparados pela função de distância Damerau-Levenshtein.

O dicionário é armazenado no banco de dados MySQL. Para não carregar o dicionário na memória do aplicativo, foi decidido calcular a distância Damerau-Levenshtein no lado da base. A função definida pelo usuário para calcular a distância Damerau-Levenshtein , escrita com base na função C escrita por Linus Torvalds , atendeu totalmente aos nossos requisitos. Criado por Diego Torres.

Após o cálculo da distância Damerau-Levenshtein, foi necessário classificar os resultados por grau de similaridade para selecionar o mais adequado. Para fazer isso, usamos o algoritmo Oliver: calculando a semelhança de duas linhas. No php, esse algoritmo é representado pela função similar_text. Os dois primeiros parâmetros da função aceitam as linhas de entrada que precisam ser comparadas.A ordem de comparação das strings é importante, pois a função fornece valores diferentes, dependendo da ordem em que as linhas são passadas para a função. O terceiro parâmetro deve receber a variável na qual o resultado da comparação é colocado. Este será um número de 0 a 100, o que significa a porcentagem de similaridade entre as duas linhas. Após o cálculo, os resultados são classificados em ordem decrescente de similaridade e, em seguida, as opções com os melhores valores são selecionadas.

Como o cálculo da distância Damerau-Levenshtein foi realizado de acordo com a transcrição da palavra, as palavras com significados não inteiramente relevantes caíram nos resultados. Nesse sentido, limitamos a seleção de opções com uma porcentagem de correspondência superior a 70%.

Durante o processo de desenvolvimento, percebemos que nosso algoritmo pode adivinhar palavras em diferentes layouts. Portanto, precisávamos expandir o dicionário adicionando o significado das palavras no layout reverso. Os requisitos de pesquisa apresentavam apenas dois layouts: russo e inglês. Duplicamos cada palavra da consulta de pesquisa do usuário no layout reverso e adicionamos processamento para calcular a distância Damerau-Levenshtein. As opções de layout direto e reverso são processadas independentemente uma da outra, opções com a maior porcentagem de similaridade são selecionadas. Somente para opções de layout reverso, o valor no layout direto será o valor da consulta de pesquisa corrigida.

Algoritmo de pesquisa difusa

Assim, um algoritmo de ações de 6 etapas principais foi formado. Durante o teste, descobrimos que nem todas as palavras nas solicitações do usuário precisam ser processadas em sua forma original ou processadas em geral. Para resolver esses casos, uma etapa adicional foi introduzida, que chamamos de conversor ou filtro. Como resultado, o algoritmo final consistiu em 7 etapas:

1. Divida a consulta em palavras separadas;
2. Passe cada palavra pelo conversor (mais adiante);
3. Para cada palavra, faça sua forma em um layout diferente;
4. Componha uma transcrição;
5. Faça uma consulta de pesquisa na tabela do dicionário, comparando cada entrada pela distância Damerau-Levenshtein;
6. Deixe apenas registros com uma distância menor ou igual a dois;
7. Através do algoritmo Oliver, deixe apenas palavras com uma porcentagem de similaridade superior a 70%

Esquematicamente, esse algoritmo é o seguinte:

Funcionalidade de conversão e filtragem de palavras

Quando começamos a testar o primeiro protótipo sem um conversor, ficou óbvio que não havia necessidade de tentar adivinhar todas as palavras na solicitação do usuário. Um conversor foi criado para essas restrições. Permite converter palavras para a forma que precisamos e filtrar aquelas que, em nossa opinião, não precisam ser adivinhadas.

Inicialmente, foi decidido que o comprimento mínimo da palavra que deveria ser passado pelo algoritmo deveria ter pelo menos dois caracteres. Afinal, se o usuário digitar um pretexto ou uma união de um caractere, a probabilidade de adivinhar é praticamente mínima. O segundo passo foi dividir a consulta em palavras. Primeiro, escolhemos um conjunto de caracteres que podem conter palavras: letras, números, ponto final e hífen (traço). Espaços e outros caracteres são delimitadores de palavras.

Muitas vezes, os usuários inserem números para indicar volume ou quantidade. Nesse caso, será incorreto corrigir essa solicitação. Por exemplo, um usuário inseriu a consulta "água 1,1 litros". Se corrigirmos sua solicitação em 1,5 ou 1,0, estará errado. Nesses casos, decidimos pular palavras com um número. Eles, ignorando nosso algoritmo, são transferidos para a pesquisa Sphinx de texto completo.

Outra conversão está associada a pontos nos nomes de marcas - por exemplo: Dr. Pepper ou Mr.Proper. Nos casos em que existe um símbolo de ponto no meio da palavra, dividimos em dois, adicionando um espaço. O segundo caso com um ponto no meio da palavra - aqui lembramos as marcas de abreviação. Por exemplo, a marca ROCS - nesse caso, cortamos os pontos e obtemos uma única palavra. Essa conversão funciona se houver apenas uma letra entre os pontos.

Nos casos em que um hífen (traço) está presente na palavra, você deve dividi-la em várias e tentar adivinhar individualmente e, em seguida, colar as melhores opções.

Como resultado, um conversor foi desenvolvido para o reconhecimento mais preciso da solicitação - a maior parte do trabalho de configuração de toda a funcionalidade foi realizada por esse desenvolvimento em particular. Em grande parte graças a ele, é realizado o ajuste e a sintonia de toda a pesquisa difusa. Repita brevemente as regras pelas quais a triagem e a conversão de palavras são realizadas:

• a palavra deve ter mais de 2 caracteres
• a palavra deve conter apenas letras, um caractere de ponto e um hífen (traço)
• se o ponto estiver no meio da palavra, um espaço será adicionado depois
• se for uma abreviação, os pontos são cortados e as letras são coladas
• não tente adivinhar a palavra se houver um número nela
• se a palavra contiver um hífen (traço), divida-o em vários, pesquise separadamente e cole no final

Compilação de Dicionário

Como mencionado anteriormente, para corrigir a solicitação de um usuário, é necessário determinar quais palavras estão escritas incorretamente e quais não. Para isso, foi criado um dicionário no sistema em que as palavras com a grafia correta devem estar contidas.

Na primeira etapa, surgiu a questão de preencher o dicionário - como resultado, decidimos usar o conteúdo do catálogo para compilá-lo. Como as informações sobre mercadorias eram importadas periodicamente de um sistema externo e indexadas para o sistema de pesquisa de texto completo do Sphinx, decidiu-se adicionar a funcionalidade de compilação do dicionário nesse estágio. Seguimos a seguinte lógica: se a palavra não está no conteúdo dos produtos, por que tentar adivinhar?
As informações do produto foram combinadas em um texto comum e conduzidas através de um conversor. O modo de operação do conversor foi ligeiramente modificado: ao quebrar palavras através de um hífen (traço), cada parte foi salva no dicionário separadamente, ao substituir pontos no dicionário, os dados originais e alterados são adicionados. E como na comparação de palavras para calcular a distância Damerau-Levenshtein, a transcrição de palavras é usada, além do dicionário, a transcrição é adicionada.

Houve muitos erros de digitação no conteúdo dos produtos; para esse efeito, uma bandeira foi colocada no dicionário, quando instalada, a palavra não é mais usada na pesquisa. O conteúdo de 35 mil produtos permitiu criar um dicionário de 100 mil palavras únicas, o que, no final, não foi suficiente para algumas consultas dos usuários. Nesse sentido, era necessário fornecer uma função de carregamento para seu enriquecimento. Um comando do console foi criado para carregar dicionários. O formato dos arquivos com os dados dos dicionários deve corresponder ao csv. Cada entrada contém apenas um campo com o próprio campo de dicionário. Para distinguir os dados baixados dos dados gerados com base no conteúdo das mercadorias, foi adicionada uma bandeira especial.
Como resultado, a tabela de dicionário possui o seguinte esquema:

Nome do campo	Tipo de campo
A palavra	corda
Transcrição	corda
Adicionado manualmente	bool
Não use	bool

Antes do desenvolvimento da funcionalidade de pesquisa difusa, havia campos nos produtos que continham um conjunto de palavras com erros de digitação. Na primeira etapa da geração do dicionário, eles entraram no seu conteúdo. Como resultado, foi obtido um dicionário com erros de digitação, cujo conteúdo não era adequado para o funcionamento funcional. Portanto, foi adicionado outro comando do console que tinha a funcionalidade de geração inversa de dicionário. Usando o conteúdo de um determinado campo de mercadorias, a equipe procurou por palavras no dicionário e as limpou do dicionário. Após a limpeza, esses campos foram excluídos da indexação.

Integração Bitrix

Para implementar a funcionalidade mínima exigida, três classes foram criadas:

• DictionaryTable - sistemas Bitrix ORM para trabalhar com um dicionário
• Dicionário - classe de geração de dicionário
• Pesquisa - classe de implementação de pesquisa

Para integração no Bitrix, foi necessário fazer alterações em 2 componentes:

• bitrix: search.page
• bitrix.search.title

Antes de executar a solicitação, o método de processamento é chamado para detectar erros e selecionar as opções apropriadas:



Para compilar um dicionário, um evento foi registrado para indexação pelo módulo de pesquisa dos elementos do bloco de informações com mercadorias (search: BeforeIndex).

Planos futuros

Essa abordagem não é ideal em termos de desempenho. Com o aumento do tamanho do dicionário para mais de 1 milhão de palavras, o tempo de resposta do banco de dados pode aumentar significativamente. Embora o dicionário seja pequeno, o desempenho nos convém. Pode ser necessário implementar o algoritmo no futuro através de um autômato de Levenshtein ou de uma árvore de prefixos.

Conclusão

Portanto, nenhum mecanismo de pesquisa é poupado da aparência de consultas que violam as regras de ortografia geralmente aceitas - seja um erro de digitação aleatório ou uma falta real de conhecimento da ortografia das palavras. Portanto, sem nem mesmo recorrer às opções clássicas de pesquisa difusa Google ou Yandex, você pode criar as suas próprias, graças às quais o usuário e o proprietário do site poderão obter o resultado desejado.

O código de nossa implementação pode ser visualizado no repositório: github.com/qsoft-dev/damlev-bitrix