👎🏻 🎼 🖖 Algoritmo de búsqueda difusa TextRadar. Artefactos (Parte 2) 👩🏾‍✈️ 👴🏿 ♎️

En una publicación anterior, el Algoritmo de búsqueda difusa de TextRadar. Los enfoques principales (Parte 1) se consideran los enfoques principales. Al resolver problemas prácticos, se identificaron situaciones en las que el uso de solo la metodología básica no proporciona la calidad requerida de la búsqueda. Como resultado, se crearon complementos (opciones de algoritmo), que se discutirán.

Los fragmentos de una palabra de una cadena de búsqueda se encuentran en varias palabras de una cadena de datos

Deje que la cadena de búsqueda sea ABCD y la cadena de datos sea ABCE DFG.

imagen

La aplicación del algoritmo básico dará el siguiente resultado:

imagen

Cuando ocurren tales colisiones, se eliminan grupos adicionales. La elección de grupos para eliminar es una pregunta compleja y separada. Como resultado, los grupos más significativos deberían permanecer. En el caso del ejemplo anterior, la respuesta es obvia: el grupo más pequeño debe eliminarse.

imagen

El fragmento de inicio de la palabra de cadena de búsqueda se encuentra dentro de la palabra de cadena de datos

Considere el ejemplo de encontrar la cadena ABC en la cadena XYZAB.

imagen

El algoritmo básico producirá lo siguiente:

imagen

Como regla, dicho resultado no tiene valor práctico y debe descartarse.

Cobertura insuficiente de una palabra en una fila de datos con fragmentos encontrados

Si buscamos en la línea ABCDEF la palabra ABXYZ

imagen

obtenemos:

imagen

Este resultado tampoco tiene valor y debe descartarse.

Sobregrupos

Dada la cadena de búsqueda ABCXEF y la cadena de datos ABCEF ABCDEF.

imagen

Desde el punto de vista del algoritmo básico, ambas palabras de la cadena de datos son equivalentes, pero la primera tendrá prioridad (si, ceteris paribus, se selecciona la primera palabra que se encuentra) y luego el resultado de la búsqueda será el siguiente:

imagen

Si presentamos el concepto de un supergrupo como una unión de grupos de palabras ubicados en la misma diagonal (o desplazamiento, consulte la publicación anterior, que analiza los conceptos básicos del algoritmo) y aumentamos la prioridad de los grupos incluidos en el supergrupo a través del parámetro del tamaño del supergrupo calculado para cada uno de los grupos y asumimos que si el grupo no es parte del supergrupo, entonces el tamaño del supergrupo para él será igual al tamaño del grupo mismo; para nuestro ejemplo, obtenemos el siguiente resultado:

imagen

Palabras largas exageradas

Al buscar una frase que contenga una palabra larga y corta, los fragmentos encontrados de una palabra larga pueden "oscurecer" los fragmentos de una palabra corta. Esto se debe al uso de una función cuadrática en el cálculo del coeficiente de relevancia.

imagen

Además, desde el punto de vista de la calidad de búsqueda, una palabra más larga no siempre es más significativa.

Considera un ejemplo. Suponga que necesita encontrar la cadena ABCDEFG XYZ en un texto que consta de dos páginas:

1. ABCDEFG ... QWE

imagen

2. ABCDEFO ... XYZ

imagen

El numerador del coeficiente de composición del grupo (el denominador no tiene un efecto cualitativo en el resultado, consulte la fórmula anterior) para la primera página es 49, para el segundo - 36 + 9 = 45. Es decir, si omitimos la influencia en el resultado del factor de longitud, el resultado de búsqueda en la primera página será de mayor relevancia, lo que no cumple con las expectativas; en algunos casos, el resultado de la búsqueda en la página 2 será más valioso.

Una de las soluciones puede ser introducir restricciones en la longitud máxima de los grupos . En nuestro ejemplo, si la longitud máxima del grupo se limita a 6, por ejemplo, obtenemos 36 para la primera página y 45 para la segunda, lo que proporcionará el resultado que esperamos: la relevancia de la segunda página será mayor que la primera.

Otra forma de resolver el problema de la inconsistencia de la importancia de las palabras de la frase de búsqueda en el resultado general de su longitud es calcular la relevancia de la frase de búsqueda como el promedio de la relevancia de las palabras incluidas en ella , calculado de forma independiente. Pero aquí surge el problema opuesto: la necesidad de reducir la importancia de las palabras cortas, que se pueden resolver de manera similar, al establecer el valor umbral a la longitud de las palabras involucradas en la formación de la relevancia general, pero ya al valor mínimo.

Repeticiones repetidas de los fragmentos deseados.

Como se desprende de la declaración, la tarea es buscar la cadena de búsqueda más relevante para un conjunto de fragmentos, por lo tanto, el hecho de la repetición repetida de los fragmentos deseados en el texto no afecta el resultado: el primer fragmento adecuado se usará como resultado de la búsqueda, el resto se descartará durante el procesamiento. Considere un ejemplo de encontrar la cadena ABC en la cadena ABCD ABCE ABCF ABCG.

imagen

La aplicación del algoritmo básico dará el siguiente resultado:

imagen

Desde el punto de vista de la búsqueda de la página más relevante, esto es correcto, pero cuando se forma una presentación detallada de los resultados de la búsqueda, es necesario encontrar y seleccionar todos los fragmentos adecuados. Para hacer esto, puede usar la repetición múltiple del procedimiento de búsqueda en la página mostrada con un cierre secuencial de los fragmentos encontrados en las iteraciones anteriores. En nuestro ejemplo, esto nos permitirá encontrar todas las ocurrencias adecuadas de la cadena deseada.

imagen

Velocidad de procesamiento de datos

El procesamiento de datos sobre la marcha tiene ciertos requisitos de velocidad: la búsqueda no debería llevar demasiado tiempo.

Limitar el tamaño mínimo de los grupos procesados, deshabilitar las opciones de búsqueda

Para aumentar la velocidad de búsqueda, puede limitar la longitud mínima de los grupos procesados.

En la práctica, se aplica el siguiente enfoque: primero se realiza el primer pase “aproximado” con una restricción en el tamaño mínimo del grupo e inhabilita algunas opciones de toda la matriz de datos de búsqueda e identifica la primera porción de datos (el tamaño de la porción de datos óptima se determina a partir del contexto del problema que se está resolviendo), y luego el segundo, más completo omitiendo solo las páginas de esta parte, ya sin limitación en cuanto al tamaño de los grupos y con la inclusión de todas las opciones necesarias.

Procesamiento de datos en paralelo.

Otra forma de aumentar la velocidad de búsqueda es el procesamiento paralelo de datos. Como resultado, con una gran base de datos de búsqueda, se puede lograr un tiempo de procesamiento total aceptable aumentando el número de procesos paralelos, lo que naturalmente requerirá aumentar la capacidad del equipo.

resultados

La aplicación de los enfoques descritos nos permitió mejorar significativamente la calidad de la búsqueda, reducir la dependencia de sus resultados en varios tipos de errores tipográficos: caracteres extra, faltantes, permutaciones, etc. y, lo que es más importante, sin importar dónde se encuentren estos errores tipográficos, en la barra de búsqueda o en el texto, que está siendo buscado

Los resultados de la aplicación de los enfoques descritos se pueden ver en el soporte de demostración implementado en el sitio web textradar.ru . Sobre el ejemplo de una búsqueda en el texto de la novela L.N. "Guerra y paz" de Tolstoi puede comparar los resultados de búsqueda utilizando las versiones básicas y avanzadas del algoritmo.

imagen

Descargue o vea el proyecto de demostración con funcionalidad avanzada (C # ASP.NET MVC) aquí .

Algoritmo de búsqueda difusa TextRadar. Artefactos (Parte 2)