Todos cometemos errores: en este caso estamos hablando de consultas de búsqueda. El número de sitios para la venta de bienes y servicios está creciendo junto con las necesidades de los usuarios, pero no siempre pueden encontrar lo que están buscando, solo porque ingresan incorrectamente el nombre del producto necesario. La solución a este problema se logra implementando una búsqueda difusa, es decir, utilizando el algoritmo para encontrar los valores más cercanos, teniendo en cuenta los posibles errores o errores tipográficos del usuario. El alcance de dicha búsqueda es lo suficientemente amplio: logramos trabajar en la búsqueda de una gran tienda en línea en el segmento minorista de alimentos.
Estado de búsqueda inicial
La tienda en línea se desarrolló en la plataforma 1C-Bitrix: Site Management. Para implementar la búsqueda, utilizamos el módulo de búsqueda estándar bitrix y el motor de texto completo sphinxsearch. En sphinxsearch, se utilizó el tipo de índice Tiempo real (RT), que no requiere una fuente de datos estática, pero se puede completar en cualquier momento en tiempo real. Esto le permite actualizar de manera flexible el índice de búsqueda sin reindexarlo por completo. Dado que el índice RT usa solo SphinxQL como protocolo de consulta, la integración se llevó a cabo a través de él. SphinxQL es un protocolo de consulta similar a mysql que implementa la capacidad de conectarse a través de clientes mysql estándar, mientras proporciona sintaxis sql con algunas limitaciones y sus propias peculiaridades. El módulo de búsqueda utiliza consultas de selección / inserción / reemplazo / eliminación.
En el sistema bitrix, se llevó a cabo el proceso de indexación de estos productos, categorías y marcas. La información sobre estas entidades se transfirió a sphinx, que a su vez actualizó el índice RT. Cuando los datos se actualizan en la tienda en línea, se activa un evento que actualiza los datos en Sphinx. La coherencia de los datos se lleva a cabo a través del identificador de entidad en la tienda en línea.
Cuando un usuario busca en una tienda en línea, el sistema realiza una solicitud con una frase de búsqueda en Sphinx y obtiene identificadores de entidades, también selecciona de la información de la base de datos y forma una página con los resultados de los resultados de búsqueda.
En el momento en que comenzó la solución al problema de búsqueda difusa, el esquema general de la arquitectura de búsqueda en el proyecto era el siguiente:
Selección de tecnología
Nuestra tarea era adivinar la solicitud del usuario, que puede contener errores tipográficos. Para hacer esto, necesitamos analizar cada palabra en la solicitud y decidir si el usuario la escribió correctamente o no. En caso de error, se deben seleccionar las opciones más adecuadas. Es imposible determinar la ortografía correcta de las palabras sin una base de datos de palabras y formas de palabras del idioma en el que queremos adivinarlas. Simplísticamente, una base de datos de este tipo puede llamarse diccionario: era a él a quien necesitábamos.
Para seleccionar las opciones de sustitución de palabras ingresadas con un error, se eligió la popular fórmula de cálculo de distancia Damerau - Levenshtein. Esta fórmula es un algoritmo para comparar dos palabras. El resultado de la comparación es el número de operaciones para convertir una palabra en otra. Inicialmente, la distancia de Levenshtein implica el uso de 3 operaciones:
- inserción
- eliminación
- reemplazo
La distancia Damerau-Levenshtein es una versión extendida de la distancia Levenshtein y agrega otra operación: transposición, es decir, una permutación de dos caracteres adyacentes.
Por lo tanto, el número de operaciones recibidas se convierte en el número de errores cometidos por el usuario al escribir la palabra. Elegimos la limitación de dos errores, ya que un número mayor no tenía sentido: en este caso, tenemos demasiadas opciones para el reemplazo, lo que aumenta la probabilidad de una falla.
Para una búsqueda más relevante de variantes de palabras similares en sonido, se usó la función de megáfono: esta función convierte una palabra en su forma fonética. Desafortunadamente, el megáfono solo funciona con las letras del alfabeto inglés, así que antes de calcular la forma fonética, transcribimos la palabra. El valor de la forma fonética se almacena en el diccionario y también se calcula en la solicitud del usuario. Los valores resultantes se comparan con la función de distancia Damerau-Levenshtein.
El diccionario se almacena en la base de datos MySQL. Para no cargar el diccionario en la memoria de la aplicación, se decidió calcular la distancia Damerau-Levenshtein en el lado de la base.
La función definida por el usuario para calcular la distancia Damerau-Levenshtein , escrita sobre la base
de la función C escrita por Linus Torvalds , cumplió plenamente con nuestros requisitos. Creado por Diego Torres.
Después de calcular la distancia Damerau-Levenshtein, fue necesario ordenar los resultados por grado de similitud para seleccionar el más adecuado. Para hacer esto, utilizamos el algoritmo Oliver: calcular la similitud de dos líneas. En php, este algoritmo está representado por la función similar_texto. Los dos primeros parámetros de la función aceptan las líneas de entrada que deben compararse. El orden de comparación de cadenas es importante, ya que la función proporciona valores diferentes según el orden en que se pasan las líneas a la función. El tercer parámetro debe pasar la variable en la que se coloca el resultado de la comparación. Este será un número de 0 a 100, lo que significa el porcentaje de similitud entre las dos líneas. Después del cálculo, los resultados se ordenan en orden descendente de similitud, luego se seleccionan las opciones con los mejores valores.
Dado que el cálculo de la distancia Damerau-Levenshtein se realizó de acuerdo con la transcripción de la palabra, las palabras con significados no del todo relevantes cayeron en los resultados. En este sentido, limitamos la selección de opciones con un porcentaje de coincidencia de más del 70%.
Durante el proceso de desarrollo, notamos que nuestro algoritmo puede adivinar palabras en diferentes diseños. Por lo tanto, necesitábamos expandir el diccionario agregando el significado de las palabras en el diseño inverso. Los requisitos de búsqueda incluyeron solo dos diseños: ruso e inglés. Duplicamos cada palabra de la consulta de búsqueda del usuario en el diseño inverso y agregamos procesamiento para calcular la distancia Damerau-Levenshtein. Las opciones de diseño directo e inverso se procesan de forma independiente, se seleccionan las opciones con el mayor porcentaje de similitud. Solo para las opciones de diseño inverso, el valor en el diseño directo será el valor de la consulta de búsqueda corregida.
Algoritmo de búsqueda difusa
Así, se formó un algoritmo de acciones de 6 pasos principales. Durante las pruebas, descubrimos que no todas las palabras en las solicitudes de los usuarios deben procesarse en su forma original o procesarse en general. Para resolver estos casos, se introdujo un paso adicional, que llamamos convertidor o filtro. Como resultado, el algoritmo final consistió en 7 pasos:
- Divide la consulta en palabras separadas;
- Pase cada palabra a través del convertidor (al respecto);
- Para cada palabra, haga su forma en un diseño diferente;
- Componer una transcripción;
- Haga una consulta de búsqueda en la tabla del diccionario, comparando cada entrada a través de la distancia Damerau-Levenshtein;
- Deje solo registros con una distancia menor o igual a dos;
- A través del algoritmo Oliver, deje solo palabras con un porcentaje de similitud de más del 70%
Esquemáticamente, este algoritmo es el siguiente:
Conversión de palabras y funcionalidad de filtrado
Cuando comenzamos a probar el primer prototipo sin un convertidor, se hizo evidente que no era necesario tratar de adivinar todas las palabras en la solicitud del usuario. Se ha creado un convertidor para estas restricciones. Le permite convertir palabras a la forma que necesitamos y filtrar aquellas que, en nuestra opinión, no necesitan ser adivinadas.
Inicialmente, se decidió que la longitud mínima de palabra que se debería pasar a través del algoritmo debería ser de al menos dos caracteres. Después de todo, si el usuario ingresó un pretexto o una unión de un personaje, entonces la probabilidad de adivinar es prácticamente mínima. El segundo paso fue dividir la consulta en palabras. En primer lugar, elegimos un conjunto de caracteres que pueden contener palabras: letras, números, punto y guión (guión). Los espacios y otros caracteres son delimitadores de palabras.
Muy a menudo, los usuarios ingresan números para indicar volumen o cantidad. En este caso, será incorrecto corregir dicha solicitud. Por ejemplo, un usuario ingresó la consulta “agua 1.1 litros”. Si corregimos su solicitud por 1.5 o 1.0, será incorrecto. En tales casos, decidimos omitir palabras con un número. Ellos, sin pasar por nuestro algoritmo, se transfieren a la búsqueda de texto completo de Sphinx.
Otra conversión está asociada con puntos en las marcas, por ejemplo: Dr. Pepper o Mr.Proper. En los casos en que hay un símbolo de punto en el medio de la palabra, lo dividimos en dos, agregando un espacio. El segundo caso con un punto en el medio de la palabra: aquí recordamos las marcas abreviadas. Por ejemplo, la marca ROCS: en este caso, cortamos los puntos y obtenemos una sola palabra. Esta conversión funciona si solo hay una letra entre los puntos.
En los casos en que hay un guión (guión) en la palabra, debe dividir la palabra en varios e intentar adivinarlos individualmente, y luego pegar las mejores opciones.
Como resultado, se desarrolló un convertidor para el reconocimiento más preciso de la solicitud: este desarrollo en particular tomó la mayor parte del trabajo para configurar toda la funcionalidad. En gran parte gracias a él, se realiza el ajuste y ajuste de toda la búsqueda difusa. Repita brevemente las reglas mediante las cuales se realizan la detección y la conversión de palabras:
- la palabra debe tener más de 2 caracteres
- la palabra debe contener solo letras, un carácter de punto y un guión (guión)
- si el punto está en el medio de la palabra, se agrega un espacio después
- si es una abreviatura, los puntos se cortan y las letras se pegan
- no intentes adivinar la palabra si hay un número en ella
- si la palabra contiene un guión (guión), luego divídalo en varios, busque por separado y pegue al final
Compilación de diccionario
Como se mencionó anteriormente, para corregir la solicitud de un usuario, es necesario determinar qué palabras están mal escritas y cuáles no. Para esto, se creó un diccionario en el sistema donde deberían incluirse palabras con la ortografía correcta.
En la primera etapa, surgió la cuestión de llenar el diccionario; como resultado, decidimos usar el contenido del catálogo para compilarlo. Como la información sobre productos se importaba de vez en cuando desde un sistema externo e indexada para el sistema de búsqueda de texto completo Sphinx, se decidió agregar la funcionalidad de compilación del diccionario en esta etapa. Seguimos la siguiente lógica: si la palabra no está en el contenido de los productos, ¿por qué tratar de adivinarla?
La información del producto se combinó en un texto común y se realizó a través de un convertidor. El modo operativo del convertidor se modificó ligeramente: al separar las palabras a través de un guión (guión), cada una de las partes se guardaba en el diccionario por separado, al reemplazar los puntos en el diccionario, se agregan los datos originales y modificados. Y como al comparar palabras para calcular la distancia Damerau-Levenshtein, se usa la transcripción de la palabra, además del diccionario, se agrega la transcripción.
Hubo muchos errores tipográficos en el contenido de los productos, para este propósito se colocó una bandera en el diccionario, cuando se instaló la palabra ya no se usa en la búsqueda. El contenido de 35 mil productos permitió crear un diccionario de 100 mil palabras únicas, que al final no fue suficiente para algunas consultas de los usuarios. En este sentido, era necesario proporcionar una función de carga para su enriquecimiento. Se creó un comando de consola para cargar diccionarios. El formato de los archivos con los datos de los diccionarios debe corresponder a csv. Cada entrada contiene solo un campo con el campo del diccionario en sí. Para distinguir los datos descargados de los datos generados en función del contenido de los productos, se agregó una bandera especial.
Como resultado, la tabla del diccionario tiene el siguiente esquema:
| Nombre del campo | Tipo de campo |
|---|
| La palabra | cuerda |
| Transcripción | cuerda |
| Agregado manualmente | bool |
| No utilizar | bool |
Antes del desarrollo de la funcionalidad de búsqueda difusa, había campos en los productos que contenían un conjunto de palabras con errores tipográficos. En la primera ejecución de la generación del diccionario, entraron en su contenido. Como resultado, se obtuvo un diccionario con errores tipográficos, cuyo contenido no era adecuado para que el funcional funcionara correctamente. Por lo tanto, se agregó otro comando de consola que tenía la funcionalidad de generación inversa de diccionario. Utilizando el contenido de un campo de productos determinado, el equipo buscó palabras en el diccionario y las borró del diccionario. Después de la limpieza, dichos campos fueron excluidos de la indexación.
Integración de Bitrix
Para implementar la funcionalidad mínima requerida, se crearon tres clases:
- DictionaryTable: sistemas ORM de Bitrix para trabajar con un diccionario
- Diccionario - clase de generación de diccionario
- Buscar - clase de implementación de búsqueda
Para la integración en Bitrix, fue necesario realizar cambios en 2 componentes:
- bitrix: search.page
- bitrix.search.title
Antes de ejecutar la solicitud, se llama al método de procesamiento para detectar errores y seleccionar las opciones apropiadas:
Para compilar un diccionario, el módulo de búsqueda grabó un evento para indexar los elementos del bloque de información con bienes (búsqueda: BeforeIndex).
Planes futuros
Este enfoque no es ideal en términos de rendimiento. Con el aumento del tamaño del diccionario a 1M + palabras, el tiempo de respuesta de la base de datos puede aumentar significativamente. Si bien el diccionario es pequeño, el rendimiento nos conviene. Puede ser necesario implementar el algoritmo en el futuro a través de un autómata Levenshtein o un árbol de prefijos.
Conclusión
Por lo tanto, ningún motor de búsqueda se ahorra la aparición de consultas que violan las reglas de ortografía generalmente aceptadas, ya sea un error tipográfico aleatorio o una falta real de conocimiento de la ortografía de las palabras. Por lo tanto, sin siquiera recurrir a las clásicas opciones de búsqueda difusa Google o Yandex, puede crear la suya propia, gracias a la cual tanto el usuario como el propietario del sitio podrán obtener el resultado deseado.
El código de nuestra implementación se puede ver en el repositorio:
github.com/qsoft-dev/damlev-bitrix