Imagina tu primer día en un nuevo trabajo. La oficina está ubicada en el área de la estación de metro Kurskaya completamente desconocida. El almuerzo se acerca. Abre la aplicación de búsqueda, escribe
"comer en Kursk" y obtiene una selección de opciones donde puede cenar.
¿Qué hay detrás de la solicitud
"comer en Kursk" y cómo se procesa para encontrar exactamente lo que necesita? En el artículo, le diré cómo el equipo de búsqueda de 2GIS hace todo lo posible para que la vida en las ciudades sea más conveniente y cómoda para los usuarios.
Es importante comprender que el texto de la consulta de búsqueda es solo la punta del iceberg, una pequeña parte de lo que el usuario interactúa directamente. La consulta de búsqueda en sí, además del texto, contiene muchos otros datos. Incluyen información personalizada sobre la ubicación del usuario, el área del mapa que ve, un conjunto de registros de sus favoritos e información sobre los modos de búsqueda. Por ejemplo, una búsqueda en un mapa o en un edificio, o tal vez una búsqueda de direcciones. Los datos son la clave del éxito de una buena funcionalidad de búsqueda.
Prestamos mucha atención a nuestros datos y su estructura. Además, llamamos al algoritmo de búsqueda en búsqueda estructural 2GIS, porque se agudiza mediante una búsqueda efectiva y rápida en nuestros datos estructurados. Preparamos específicamente el índice de búsqueda y los datos a partir de los cuales está construido. No entraré en detalles, solo puedo decir que los datos están organizados de manera que sean lo suficientemente simples para procesarlos, están bien comprimidos y, lo más importante, nos permiten procesarlos rápidamente incluso en dispositivos móviles.
Además, la búsqueda puede funcionar sin conexión y, por lo tanto, exige especialmente la velocidad y el volumen del índice de búsqueda. Prestamos mucha atención a esta característica: comprimimos constantemente el índice de búsqueda, evaluamos el rendimiento en todo tipo de plataformas y aceleramos la funcionalidad donde los casos de búsqueda específicos exceden el límite de tiempo establecido. Por cierto, podemos presumir de que una consulta de búsqueda ordinaria en 2GIS en un dispositivo móvil es más rápida que la aplicación dibuja una lista desplegable basada en los resultados.
A continuación, desvelaré el velo del secreto que cubre la magia de nuestra búsqueda. Como ejemplo, tomamos la solicitud mencionada
"comer en Kursk" . Considere las etapas de su procesamiento y lo que sucede en cada una de ellas. ¡Entonces vamos!
Etapa 1. Análisis
Parámetros de entrada: solicitud
"comer en Kursk"En primer lugar, debemos analizar el texto de la solicitud. Esto es importante, porque después del análisis podemos trabajar no con el texto de la solicitud, sino con el conjunto de tokens que lo componen. Los tokens son palabras de solicitud única. En nuestro caso, recibiremos un conjunto de tres fichas:
"comer" ,
"encendido" ,
"Kursk" . Parece que todo es simple, pero el diablo está en los detalles. Y a veces no es tan obvio: por ejemplo, en consultas "wi-fi" o "2da", debemos entender que debemos manejar tales combinaciones en su totalidad.
Los tokens contienen información sobre el texto de la palabra, sobre la posición en la solicitud, sobre la presencia de un separador que sigue a la palabra y algunas características de la palabra: el registro de sus caracteres, ya sea que la palabra sea un número, un número ordinal, un número de teléfono, una dirección u otros datos.
Etapa 2. Búsqueda de diccionario
Parámetros de entrada: tokens
"eat" ,
"on" ,
"Kursk"Con una lista lista de tokens de solicitud, pasamos a la etapa de búsqueda de diccionario, es decir, a la etapa en la que para cada token encontramos una lista de formas de palabras a partir de nuestros datos. Una forma de palabra es información codificada sobre la raíz de una palabra y su final.
Presentamos la búsqueda de diccionario como un algoritmo para analizar un diccionario, presentado en forma de gráfico. Los nodos en él son letras, o más bien, símbolos. Un gráfico consta de nodos de símbolos y transiciones entre estos nodos. El resultado de recorrer nuestro gráfico del diccionario es una gran cantidad de formas de palabras que podemos obtener en función de los tokens transferidos de la etapa anterior. Por lo tanto, tratamos de encontrar en nuestro diccionario una secuencia de caracteres que coincida con el siguiente token de la solicitud. Al mismo tiempo, como todos sabemos, los usuarios hacen errores tipográficos, faltan letras o incluso cometen errores en la distribución del teclado. Por lo tanto, al recorrer el diccionario, aplicamos algunas manipulaciones para tener en cuenta un posible factor humano o tratar de adivinar lo que una persona está ganando en este momento. Se utilizan varias transformaciones de la cadena de caracteres: inserciones, reemplazos, anexar caracteres y similares.
Como resultado, para cada token de solicitud del gráfico, extraemos un conjunto de formularios de palabras con información sobre la raíz y el final de la palabra, información sobre el número de caracteres en el formulario de palabras y una estimación de lo encontrado. Estimación de un hallazgo: una evaluación que caracteriza la distancia de vocabulario de una secuencia de caracteres encontrada a la secuencia deseada. La evaluación caracteriza cuánto difiere la cadena de caracteres encontrada del token de solicitud.
Entonces, para los tokens encontramos formas de palabras:
- 13 formas para "comer" : "comer", "comer", "paese", "payot", ...
- 3 formas para "on" : "na", "nu", "on"
- 48 formularios para "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kurako", ...
A continuación, los formularios de palabras encontrados se filtran según su evaluación. Lo mejor de ellos, es decir, lo más cerca posible de las palabras de la consulta, cae en la lista de términos. Por el término entendemos la forma de la palabra y la estimación del hallazgo. Además, además de las formas de palabras encontradas, los términos agregados usando las reglas de morfología se agregan a la lista. Un paso importante en el procesamiento morfológico es la adición de una evaluación morfológica. El hecho es que nuestra búsqueda utiliza un fuerte mecanismo de procesamiento morfológico que nos permite no solo encontrar palabras similares en el diccionario, sino que de acuerdo con las reglas del lenguaje natural, es más preciso encontrar exactamente lo que le interesa al usuario por el significado, y no solo por la similitud de las palabras.
Entonces, para los tokens, se crearán los términos:
- "Comer" : "comer", "comer", "comer", "comer", "comer"
- "On" : "on", "na", "nu"
- "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kursk"
En esta etapa, finaliza la búsqueda del diccionario. Hemos procesado la solicitud y tenemos para cada token una lista de términos que entran en el procesamiento posterior. Estos términos contienen toda la información sobre la palabra que representan y tienen una evaluación de cómo se encontró cada uno de ellos.
Paso 3. Encontrar entradas de datos
Entrada: un conjunto de términos para cada parte de la solicitud
- "Comer" : "comer", "comer", "comer", "comer", "comer"
- "On" : "on", "na", "nu"
- "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kursk"
Después de recibir de la etapa anterior un conjunto de términos para cada una de las partes de la solicitud, procedemos a buscarlos por nuestro índice. Cada documento en los datos tiene muchos encabezados y está escrito en el
índice inverso para que podamos encontrar fácilmente todas las referencias al término deseado en documentos específicos que representan organizaciones, direcciones o cualquier otro.
Para cada una de las partes de la solicitud y para cada uno de los términos de estas partes, estamos buscando documentos que contengan palabras codificadas en términos. Entonces, para partes de la solicitud, las entradas se encontrarán en todos los términos:
- "Eat" : 18 entradas
- En : 4,304 entradas
- Kursk : 79 entradas
Obviamente, la preposición
"on" ocurre muchas veces y, por lo tanto, cae en muchos títulos de documentos: "café para llevar", "jugar
en la consola", "registro de la máquina".
"Comer" y
"Kursk" también se usan repetidamente. La segunda palabra con sus términos se encuentra en nuestros datos con mucha más frecuencia que la primera.
Por golpe, consideramos la coincidencia de una palabra de una consulta de búsqueda con una palabra de un documento específico. Estos resultados se guardan en la lista, que se analizará en el siguiente paso. Al agregar un hit, no solo copiamos datos sobre la palabra en el documento del término, sino que también calculamos la mejor estimación de cómo se puede encontrar la palabra. En otras palabras, elegimos una evaluación morfológica del término, o una evaluación de cómo se encontró el término en el diccionario, dependiendo de cuál de las calificaciones esté más cerca del token de solicitud.
Esta etapa es un preludio al comienzo de la búsqueda misma. Hemos preparado un conjunto de resultados en documentos específicos, sobre la base de los cuales el siguiente algoritmo seleccionará y evaluará lo que se debe dar al usuario como resultado.
Etapa 4. El corazón de la búsqueda.
Entrada: lista de resultados
- "Eat" : 18 entradas
- En : 4,304 entradas
- Kursk : 79 entradas
De hecho, la lista de resultados en nuestra implementación es un contenedor bastante complicado. Es importante comprender que cuando se le agregan hits, se crean nodos especiales donde se registran los hits en sí mismos y un enlace al documento en el que cayeron estos hits.
Por lo tanto, será más correcto mostrar los datos de entrada de la siguiente manera:
Entrada: contenedor de nodos de documentos
- document1: {hits, ...}
- document2: {hits, ...}
- document3: {hits, ...}
- document4: {hits, ...}
- ...
En primer lugar, la búsqueda comienza pasando por alto el árbol de documentos y cada nodo lo envía al analizador, que evalúa si el documento de este nodo es adecuado para ser el resultado para ingresar a la salida. Para comprender con qué volúmenes tiene que trabajar el analizador, ¡diré que al principio el contenedor contiene más de 3000 nodos! Pero los nodos se pueden agregar durante el proceso de rastreo, por lo tanto, en realidad se procesa aún más. No es exagerado decir que el análisis es la parte más costosa de la búsqueda y, al mismo tiempo, una de las funciones más complejas y grandes del proyecto. Sin embargo, funciona extremadamente rápido incluso en dispositivos móviles.
Etapa 5. Análisis
Entrada: nodo del
documento: {hits, ...}El análisis comienza obteniendo una lista de títulos del nodo. El título es un título y una lista de resultados que se incluyen en este título del documento. Estos títulos se evaluarán en la primera etapa. Es importante para nosotros descubrir la utilidad de cada título. La utilidad puede ser buena, débil y basura.
Para cada uno de los títulos, se seleccionan los mejores de la cadena de éxitos: la mejor puntuación de longitud y vocabulario, compuesta por la similitud de los éxitos. Basado en la mejor cadena, se evaluará la utilidad del título. Para determinar la utilidad de la cadena, también utilizamos un mecanismo basado en la frecuencia de las palabras en los documentos. En términos generales, cuanto más a menudo aparece una palabra en un documento, más importante es (
TF-IDF ). Entonces, si la cadena contiene una palabra importante del título del documento sin fuertes diferencias morfológicas, por ejemplo, un número o género excelente, consideramos que el título es útil. Un título también puede ser útil si sus aciertos cubren completamente las palabras del título del documento.
Con la utilidad, todos los títulos forman una máscara de utilidad para el nodo. Esta máscara nos da una idea de los tokens de solicitud cubiertos por el nodo analizado. Y con su ayuda, determinamos en gran medida si analizar más el nodo.
Como resultado, no solo tenemos un documento del índice, sino un conjunto de datos estructurales que representan un resultado potencial con información sobre cómo se puede encontrar.
Paso 6. Evaluación
Entrada: nodo del
documento: {hits, ...}Dependiendo de la máscara de utilidad, procesaremos el nodo o procederemos inmediatamente al siguiente. De los muchos nodos procesados, acumulamos diversa información sobre su totalidad. Por ejemplo, muchos títulos de nodos, relaciones entre nodos y algunos otros datos.
Luego comienza el análisis de los títulos de los nodos interconectados entre sí. De hecho, muchos nodos se combinan en un gráfico de nodos, que evaluamos.
De los nodos de los nodos del gráfico obtenemos una lista de títulos clasificados. En pocas palabras, a partir de una variedad de nodos, componimos una lista única de títulos, en la que para cada elemento también agregamos una estimación y un conjunto de factores a partir de los resultados de los títulos de todos los nodos participantes.
Evaluación: una estructura con información sobre el número de palabras involucradas en un título de una consulta y muchos otros factores sobre cómo se encontró y procesó la palabra, comenzando desde la etapa de búsqueda del diccionario. Es importante que estas calificaciones del título clasificado participen en la selección de las mejores calificaciones. Algunos de ellos se marcarán como seleccionados y contribuirán a la evaluación final del resultado que ve el usuario.
La evaluación general proporciona información sobre el resultado que será crucial para clasificar todo el resultado. Contiene factores como, por ejemplo, palabras faltantes de una consulta. Esta medida caracteriza el número de palabras que no estaban cubiertas por un nodo con su información estructural.
Según la información sobre la utilidad de los títulos, se determina la claridad del resultado. La claridad puede ser buena, débil y mala. Y se calcula con la participación de todos los títulos seleccionados para el nodo procesado. Todos estos datos tienen un efecto dramático sobre el destino de los resultados y el orden en que se emiten.
Gradualmente, nos estamos acercando al final del análisis del nodo. Antes de que el nodo finalmente salga del analizador y se convierta en un resultado potencial, llevamos a cabo algunas manipulaciones más específicas. Por ejemplo, la compatibilidad de los títulos de documentos seleccionados.
Un nodo que ha pasado todos los círculos del analizador forma un resultado que contiene información sobre los encabezados seleccionados y un documento. El resultado, que ofrece una buena cobertura de la consulta de búsqueda, se envía al procesamiento posterior.
Paso 7. Postprocesamiento
Entrada: resultado construido a partir del nodo
El analizador filtra muchos registros del índice antes de que se conviertan en resultados. Sin embargo, durante el análisis, muchos resultados potenciales pueden evaluarse y enviarse para su procesamiento. Para mostrar al usuario solo los más útiles en orden de relevancia, necesitamos cortar las peores opciones encontradas por el analizador.
En el paso anterior, se mencionó una evaluación general del resultado. Una evaluación general nos permite cortar los peores resultados en la etapa posterior al procesamiento. La gradación es la siguiente. Los resultados que no cubren ningún token de solicitud son obviamente peores que los que cubren completamente la solicitud del usuario. Los resultados con peor claridad son obviamente menos deseables que los resultados con buena claridad. El postprocesador acumula información sobre los resultados entrantes y elimina los que obviamente son peores. El resto se agrega a la lista.
Antes de dar información al usuario hambriento sobre el café, llevamos a cabo el procesamiento final, ordenado por relevancia. La ordenación implica muchos factores, calculados y agregados en diferentes etapas de la búsqueda. Y en última instancia, los resultados de búsqueda para
"comer en Kursk" son más de 500 resultados. Muchos de ellos se encontraron de la misma manera y, por lo tanto, tienen la misma calificación. Se ordenarán según la popularidad del usuario.
Conclusión
Recibimos la extradición con muchos cafés y restaurantes y, alegremente, vamos a cenar. Obtuvimos todos los resultados en una fracción de segundo. Ni siquiera necesitamos una conexión a internet.
La aplicación almacena índices de búsqueda en el dispositivo. Tal esquema nos proporciona tareas no triviales para optimizar la compresión de datos y la velocidad de procesamiento; después de todo, ¡la búsqueda debería funcionar rápidamente en una amplia variedad de dispositivos móviles! Sin embargo, esta es una historia completamente diferente.
Hoy intenté abrir el capó de nuestro motor de búsqueda y mostrar cómo ayudamos a los usuarios a encontrar lo que necesitan en la ciudad, y hacerlo de manera rápida y conveniente. Espero que haya sido informativo.