⚜️ 👇🏽 🤲🏾 Algoritmo de pesquisa difusa do TextRadar. Artefatos (Parte 2) 🥒 🦈 📸

Em uma publicação anterior, o Algoritmo de Pesquisa Difusa do TextRadar. As principais abordagens (Parte 1) são consideradas as principais abordagens. Ao resolver problemas práticos, foram identificadas situações em que o uso apenas da metodologia básica não fornece a qualidade exigida da pesquisa. Como resultado, foram criados complementos (opções de algoritmo), que serão discutidos.

Fragmentos de uma palavra de uma sequência de pesquisa estão localizados em várias palavras de uma sequência de dados

Deixe a cadeia de pesquisa ser ABCD e a cadeia de dados ser ABCE DFG.

imagem

A aplicação do algoritmo básico dará o seguinte resultado:

imagem

Quando tais colisões ocorrem, grupos extras são excluídos. A escolha dos grupos a serem excluídos é uma questão separada e complexa. Como resultado, os grupos mais significativos devem permanecer. No caso do exemplo acima, a resposta é óbvia - o menor dos grupos deve ser excluído.

imagem

O fragmento inicial da palavra da cadeia de pesquisa está localizado dentro da palavra da cadeia de dados

Considere o exemplo de localização da cadeia ABC na cadeia XYZAB.

imagem

O algoritmo básico produzirá o seguinte:

imagem

Como regra, esse resultado não tem valor prático e deve ser descartado.

Cobertura insuficiente de uma palavra em uma linha de dados com fragmentos encontrados

Se procurarmos na palavra ABCDEF pela palavra ABXYZ

imagem

, obtemos:

imagem

Este resultado também não tem valor e deve ser descartado.

Overgroups

Dada a sequência de pesquisa ABCXEF e a sequência de dados ABCEF ABCDEF.

imagem

Do ponto de vista do algoritmo básico, ambas as palavras da sequência de dados são equivalentes, mas a primeira delas terá prioridade (se, ceteris paribus, a primeira palavra encontrada for selecionada) e, em seguida, o resultado da pesquisa será o seguinte:

imagem

Se introduzirmos o conceito de um supergrupo como uma união de grupos de palavras localizados na mesma diagonal (ou turno, consulte a publicação anterior, que discute os conceitos básicos do algoritmo) e aumentar a prioridade dos grupos incluídos no supergrupo por meio do parâmetro tamanho do supergrupo calculado para cada grupo e supor que se o grupo não fizer parte do supergrupo, o tamanho do supergrupo será igual ao tamanho do próprio grupo - no nosso exemplo, obtemos o seguinte resultado:

imagem

Palavras longas exageradas

Ao procurar uma frase que contenha uma palavra longa e curta, fragmentos encontrados de uma palavra longa podem "obscurecer" fragmentos de uma palavra curta. Isso se deve ao uso de uma função quadrática no cálculo do coeficiente de relevância.

imagem

Além disso, do ponto de vista da qualidade da pesquisa, uma palavra mais longa nem sempre é mais significativa.

Considere um exemplo. Suponha que você precise encontrar a sequência ABCDEFG XYZ em um texto que consiste em duas páginas:

1. ABCDEFG ... QWE

imagem

2. ABCDEFO ... XYZ

imagem

O numerador do coeficiente de composição do grupo (o denominador não tem efeito qualitativo no resultado, veja a fórmula acima) para a primeira página é 49, para a segunda - 36 + 9 = 45. Ou seja, se omitirmos a influência no resultado do fator de comprimento, o resultado da pesquisa na primeira página terá maior relevância, o que não atenderá às expectativas - em alguns casos, o resultado da pesquisa na página 2 será mais valioso.

Uma das soluções pode ser a introdução de restrições no tamanho máximo dos grupos . No nosso exemplo, se o tamanho máximo do grupo for limitado a 6, por exemplo, obteremos 36 na primeira página e 45 na segunda, o que fornecerá o resultado esperado - a relevância da segunda página será maior que a primeira.

Outra maneira de resolver o problema da inconsistência da significância das palavras da frase de pesquisa no resultado geral de seu comprimento é calcular a relevância da frase de pesquisa como a média da relevância das palavras incluídas nela , calculadas independentemente. Mas aqui surge o problema oposto - a necessidade de reduzir o significado de palavras curtas, que podem ser resolvidas de maneira semelhante - definindo o valor limite para o comprimento das palavras envolvidas na formação da relevância geral, mas já para o valor mínimo.

Repetições repetidas dos fragmentos desejados

Como segue a declaração, a tarefa é procurar a sequência de pesquisa mais relevante para um conjunto de fragmentos, portanto, o fato da repetição repetida dos fragmentos desejados no texto não afeta o resultado - o primeiro fragmento adequado será usado como resultado da pesquisa, o restante será descartado durante o processamento. Considere um exemplo de localização da cadeia ABC na cadeia ABCD ABCE ABCF ABCG.

imagem

A aplicação do algoritmo básico dará o seguinte resultado:

imagem

Do ponto de vista da pesquisa da página mais relevante, isso está correto, mas ao formar uma apresentação detalhada dos resultados da pesquisa, é necessário encontrar e selecionar todos os fragmentos adequados. Para fazer isso, você pode usar várias repetições do procedimento de pesquisa na página exibida com um desligamento seqüencial dos fragmentos encontrados nas iterações anteriores. Em nosso exemplo, isso nos permitirá encontrar todas as ocorrências adequadas da string desejada.

imagem

Velocidade de processamento de dados

O processamento de dados em tempo real possui alguns requisitos de velocidade - a pesquisa não deve demorar muito.

Limitando o tamanho mínimo dos grupos processados, desativando as opções de pesquisa

Para aumentar a velocidade da pesquisa, você pode limitar o tamanho mínimo dos grupos processados.

Na prática, a seguinte abordagem é aplicada - primeiro, a primeira passagem "aproximada" é feita com uma restrição ao tamanho mínimo do grupo e desativando algumas opções de toda a matriz de dados de pesquisa e identificando a primeira porção de dados (o tamanho da porção ideal de dados é determinada a partir do contexto do problema que está sendo resolvido) e, em seguida, a segunda, mais completa ignorando apenas as páginas desta parte, já sem limitação no tamanho dos grupos e com a inclusão de todas as opções necessárias.

Processamento de dados paralelo

Outra maneira de aumentar a velocidade da pesquisa é o processamento de dados paralelo. Como resultado, com um grande banco de dados de pesquisa, é possível obter um tempo total de processamento aceitável aumentando o número de processos paralelos, o que naturalmente exigirá o aumento da capacidade do equipamento.

resultados

A aplicação das abordagens descritas nos permitiu melhorar significativamente a qualidade da pesquisa, reduzir a dependência de seus resultados em vários tipos de erros de digitação - caracteres supérfluos, ausentes, permutações etc. e, mais importante, não importa onde esses erros estejam localizados - na própria barra de pesquisa ou no texto, que está sendo pesquisado.

Os resultados da aplicação das abordagens descritas podem ser vistos no estande de demonstração implementado no site textradar.ru . No exemplo de uma pesquisa no texto do romance L.N. "Guerra e Paz" de Tolstoi pode comparar os resultados da pesquisa usando as versões básica e avançada do algoritmo.

imagem

Baixe ou assista ao projeto de demonstração com funcionalidade avançada (C # ASP.NET MVC) aqui .

Algoritmo de pesquisa difusa do TextRadar. Artefatos (Parte 2)