Histórico de uma solicitação

Imagine seu primeiro dia em um novo emprego. O escritório está localizado na área da estação de metrô Kurskaya completamente desconhecida. O almoço está chegando. Você abre o aplicativo de pesquisa, escreve "coma no Kursk" e obtém uma seleção de opções onde pode jantar.

O que está por trás do pedido "coma no Kursk" e como é processado para encontrar exatamente o que você precisa? No artigo, mostrarei como a equipe do 2GIS Search faz todo o possível para tornar a vida nas cidades mais conveniente e confortável para os usuários.

É importante entender que o texto da consulta de pesquisa é apenas a ponta do iceberg, uma pequena parte do que o usuário interage diretamente. A consulta de pesquisa em si, além do texto, contém muitos outros dados. Eles incluem informações personalizadas sobre a localização do usuário, a área do mapa que ele vê, um conjunto de registros de seus favoritos e informações sobre os modos de pesquisa. Por exemplo, uma pesquisa em um mapa ou em um edifício, ou talvez uma pesquisa por direções. Os dados são a chave para o sucesso de uma boa funcionalidade de pesquisa.

Prestamos muita atenção aos nossos dados e sua estrutura. Além disso, chamamos o algoritmo de pesquisa na pesquisa estrutural 2GIS, porque é aprimorado por uma pesquisa rápida e eficaz em nossos dados estruturados. Preparamos especificamente o índice de pesquisa e os dados a partir dos quais ele é construído. Não entrarei em detalhes, só posso dizer que os dados são organizados de maneira a serem simples o suficiente para serem processados, bem compactados e, o mais importante, nos permite processá-los rapidamente, mesmo em dispositivos móveis.

Além disso, a pesquisa pode funcionar offline e, portanto, exige demandas especiais sobre a velocidade e o volume do índice de pesquisa. Prestamos muita atenção a esse recurso - compactamos constantemente o índice de pesquisa, avaliamos o desempenho em todos os tipos de plataformas e agilizamos a funcionalidade em que casos de pesquisa específicos excedem o limite de tempo definido. A propósito, podemos nos gabar de que uma consulta de pesquisa comum no 2GIS em um dispositivo móvel é mais rápida do que o aplicativo desenha uma lista suspensa com base nos resultados.

Abaixo, revelarei o véu do segredo que cobre a magia de nossa busca. Como exemplo, tomamos o pedido mencionado "coma no Kursk" . Considere os estágios de seu processamento e o que acontece em cada um deles. Então vamos lá!

Etapa 1. Análise

Parâmetros de entrada: solicitação "eat on Kursk"

Primeiro de tudo, precisamos analisar o texto da solicitação. Isso é importante porque, após a análise, podemos trabalhar não com o texto da solicitação, mas com o conjunto de tokens dos quais ele consiste. Tokens são palavras de solicitação única. No nosso caso, receberemos um conjunto de três fichas: "eat" , "on" , "Kursk" . Parece que tudo é simples, mas o diabo está nos detalhes. E às vezes não é tão óbvio: por exemplo, em consultas "wi-fi" ou "2ª", precisamos entender que devemos lidar com essas combinações na sua totalidade.

Os próprios tokens contêm informações sobre o texto da palavra, sobre a posição na solicitação, sobre a presença de um separador após a palavra e algumas características da palavra - o registro de seus caracteres, se a palavra é um número, um número ordinal, número de telefone, endereço ou outros dados.

Etapa 2. Pesquisa no dicionário

Parâmetros de entrada: tokens "eat" , "on" , "Kursk"


Com uma lista pronta de tokens de solicitação, prosseguimos para o estágio de pesquisa no dicionário, ou seja, para o estágio em que, para cada token, encontramos uma lista de formas de palavras de nossos dados. Um formulário de palavra é uma informação codificada sobre a raiz de uma palavra e seu fim.

Apresentamos a pesquisa de dicionário como um algoritmo para análise de um dicionário, apresentado na forma de um gráfico. Os nós nele são letras, ou melhor, símbolos. Um gráfico consiste em nós de símbolo e transições entre esses nós. O resultado de percorrer nosso gráfico de dicionário é um monte de formas de palavras que podemos obter com base nos tokens transferidos do estágio anterior. Por isso, tentamos encontrar em nosso dicionário uma sequência de caracteres que corresponda ao próximo token da solicitação. Ao mesmo tempo, como todos sabemos, os usuários cometem erros de digitação, perdem letras ou até cometem erros no layout do teclado. Portanto, ao percorrer o dicionário, aplicamos algumas manipulações para levar em conta um possível fator humano ou tentar adivinhar o que uma pessoa está ganhando agora. São usadas várias transformações da cadeia de caracteres: inserções, substituições, caracteres anexados e similares.

Como resultado, para cada token de solicitação do gráfico, extraímos um conjunto de formas de palavras com informações sobre a raiz e o final da palavra, informações sobre o número de caracteres na forma de palavras e uma estimativa dos encontrados. Estimativa de uma descoberta - uma avaliação que caracteriza a distância do vocabulário de uma sequência encontrada de caracteres até a sequência desejada. A avaliação caracteriza o quanto a cadeia de caracteres encontrada difere do token de solicitação.

Portanto, para os tokens, encontramos formas de palavras:

• 13 formas para "comer" : "comer", "comer", "paese", "payot", ...
• 3 formulários para "on" : "na", "nu", "on"
• 48 formulários para "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kurako", ...

Em seguida, as formas de palavras encontradas são filtradas, dependendo de sua avaliação. O melhor deles, ou seja, o mais próximo possível das palavras da consulta, se enquadra na lista de termos. Com o termo, entendemos a forma da palavra e a estimativa da descoberta. Além disso, além das formas de palavras encontradas, os termos adicionados usando as regras de morfologia são adicionados à lista. Um passo importante no processamento morfológico é a adição de uma avaliação morfológica. O fato é que nossa pesquisa utiliza um forte mecanismo de processamento morfológico que permite não apenas encontrar palavras semelhantes no dicionário, mas de acordo com as regras da linguagem natural, é mais preciso encontrar o que exatamente interessa ao usuário por significado, e não apenas por similaridade de palavras.

Portanto, para tokens, os termos serão criados:

• "Comer" : "comer", "comer", "comer", "comer", "comer"
• "On" : "on", "na", "nu"
• "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kursk"

Nesta fase, a pesquisa no dicionário termina. Processamos a solicitação e temos para cada token uma lista de termos que entram em processamento adicional. Esses termos contêm todas as informações sobre a palavra que eles representam e avaliam como cada um deles foi encontrado.

Etapa 3. Localizando entradas de dados

Entrada: um conjunto de termos para cada parte da solicitação

• "Comer" : "comer", "comer", "comer", "comer", "comer"
• "On" : "on", "na", "nu"
• "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kursk"

Tendo recebido do estágio anterior um conjunto de termos para cada uma das partes da solicitação, passamos a procurá-los pelo nosso índice. Cada documento nos dados possui muitos títulos e é gravado no índice reverso, para que possamos encontrar facilmente todas as referências ao termo desejado em documentos específicos que representam organizações, endereços ou quaisquer outros.

Para cada uma das partes da solicitação e para cada um desses termos, estamos procurando documentos que contenham palavras codificadas em termos. Portanto, para partes da solicitação, as entradas serão encontradas em todos os termos:

• "Comer" : 18 entradas
• Em : 4.304 entradas
• Kursk : 79 entradas

Obviamente, a preposição "on" ocorre muitas vezes e, portanto, se enquadra em muitos títulos de documentos - "café para viagem", "jogo no console", "registro da máquina". "Comer" e "Kursk" também são usados ​​repetidamente. A segunda palavra com seus termos é encontrada em nossos dados com muito mais frequência do que a primeira.


Por acerto, consideramos a correspondência de uma palavra de uma consulta de pesquisa com uma palavra de um documento específico. Essas ocorrências são salvas na lista, que será analisada na próxima etapa. Ao adicionar uma ocorrência, não apenas copiamos dados sobre a palavra no documento do termo, mas também calculamos a melhor estimativa de como a palavra pode ser encontrada. Em outras palavras, escolhemos uma avaliação morfológica do termo ou uma avaliação de como o termo foi encontrado no dicionário, dependendo de qual das classificações está mais próxima do token de solicitação.

Este estágio é um prelúdio para o início da pesquisa em si. Preparamos um conjunto de ocorrências em documentos específicos, com base nos quais o algoritmo a seguir selecionará e avaliará o que precisa ser fornecido ao usuário como resultado.

Etapa 4. O coração da pesquisa

Entrada: lista de ocorrências

• "Comer" : 18 entradas
• Em : 4.304 entradas
• Kursk : 79 entradas

De fato, a lista de ocorrências em nossa implementação é um contêiner bastante complicado. É importante entender que, ao adicionar ocorrências, são criados nós especiais onde as ocorrências são registradas e um link para o documento no qual essas ocorrências ocorreram.

Portanto, será mais correto exibir os dados de entrada da seguinte maneira:
Entrada: contêiner de nós do documento

• document1: {hits, ...}
• document2: {hits, ...}
• document3: {hits, ...}
• document4: {hits, ...}
• ...

Primeiro, a pesquisa começa ignorando a árvore de documentos e cada nó a envia para o analisador, que avalia se o documento desse nó é adequado para ser o resultado da entrada na saída. Para entender com quais volumes o analisador precisa trabalhar, direi que no início o contêiner contém mais de 3000 nós! Mas nós podem ser adicionados durante o processo de rastreamento, portanto, na verdade, é processado ainda mais. Não é exagero dizer que a análise é a parte mais cara da pesquisa e, ao mesmo tempo, uma das funções mais complexas e amplas do projeto. No entanto, ele roda extremamente rápido, mesmo em dispositivos móveis.

Etapa 5. Análise

Entrada: nó do documento: {hits, ...}


A análise começa obtendo uma lista de títulos do nó. O título é um título e uma lista de ocorrências que se enquadram nesse título do documento. Esses títulos serão avaliados na primeira etapa. É importante descobrirmos a utilidade de cada título. A utilidade pode ser boa, fraca e inútil.

Para cada um dos títulos, os melhores da cadeia de hits são selecionados - os melhores em tamanho e pontuação de vocabulário, compostos pela semelhança de hits. Com base na melhor cadeia, o título será avaliado quanto à utilidade. Para determinar a utilidade da cadeia, também usamos um mecanismo baseado na frequência de palavras nos documentos. Grosso modo, quanto mais frequentemente uma palavra aparece em um documento, mais importante é ( TF-IDF ). Portanto, se a cadeia contiver uma palavra importante do título do documento sem grandes diferenças morfológicas, por exemplo, um excelente número ou gênero, consideramos o título útil. Um título também pode ser útil se seus hits cobrirem completamente as palavras do título do documento.

Usando o utilitário, todos os títulos formam uma máscara de utilitário para o nó. Essa máscara nos dá uma idéia dos tokens de solicitação cobertos pelo nó analisado. E com sua ajuda, determinamos em grande parte se analisamos melhor o nó.

Como resultado, não temos apenas um documento do índice, mas um conjunto de dados estruturais que representam um resultado potencial com informações sobre como eles podem ser encontrados.

Etapa 6. Avaliação

Entrada: nó do documento: {hits, ...}


Dependendo da máscara do utilitário, processaremos o nó ou avançaremos imediatamente para o próximo. Dos muitos nós processados, acumulamos várias informações sobre sua totalidade. Por exemplo, muitos títulos de nó, relações entre nós e alguns outros dados.

A seguir, começa a análise dos títulos dos nós interconectados. De fato, muitos nós são combinados em um gráfico de nós, que avaliamos.

Dos nós dos nós do gráfico, obtemos uma lista de títulos classificados. Simplificando, a partir de uma variedade de nós, compomos uma única lista de títulos, na qual para cada elemento também adicionamos uma estimativa e uma combinação de fatores das ocorrências dos títulos de todos os nós participantes.

Avaliação - uma estrutura com informações sobre o número de palavras envolvidas em um título de uma consulta e muitos outros fatores sobre como a palavra foi encontrada e processada - a partir do estágio de pesquisa no dicionário. É importante que essas notas do título classificado participem da seleção das melhores notas. Alguns deles serão marcados como selecionados e contribuirão para a avaliação final do resultado que o usuário vê.

A avaliação geral fornece as informações do resultado que serão cruciais na classificação de toda a produção. Ele contém fatores como, por exemplo, palavras ausentes de uma consulta. Essa medida caracteriza o número de palavras que não foram cobertas por um nó com suas informações estruturais.

Com base nas informações sobre a utilidade dos títulos, a clareza do resultado é determinada. A clareza pode ser boa, fraca e ruim. E é calculado com a participação de todos os títulos selecionados para o nó processado. Todos esses dados têm um efeito dramático no destino dos resultados e na ordem em que são emitidos.

Gradualmente, estamos nos aproximando do final da análise do nó. Antes que o nó finalmente saia do analisador e se torne um resultado potencial, realizamos mais algumas manipulações de especificação. Por exemplo, a compatibilidade dos títulos de documentos selecionados.

Um nó que passou por todos os círculos do analisador forma um resultado que contém informações sobre os cabeçalhos selecionados e um documento. O resultado, que oferece uma boa cobertura da consulta de pesquisa, é enviado para o pós-processamento.

Etapa 7. Pós-processamento

Entrada: resultado construído a partir do nó


O analisador filtra muitos registros do índice antes que eles se tornem resultados. No entanto, durante a análise, muitos resultados potenciais podem ser avaliados e enviados para processamento. Para mostrar ao usuário apenas os mais úteis em ordem de relevância, precisamos eliminar as piores opções encontradas pelo analisador.

Na etapa anterior, uma avaliação geral do resultado foi mencionada. Uma avaliação geral permite eliminar os piores resultados no estágio de pós-processamento. A gradação é a seguinte. Os resultados que não cobrem nenhum token de solicitação são obviamente piores do que aqueles que cobrem totalmente a solicitação do usuário. Resultados com pior clareza são obviamente menos desejáveis ​​do que resultados com boa clareza. O pós-processador acumula informações sobre os resultados recebidos e elimina aqueles que são obviamente piores. O restante é adicionado à lista.

Antes de fornecer ao usuário faminto informações sobre o café, realizamos o processamento final - classifique por relevância. A classificação envolve muitos fatores, calculados e agregados em diferentes estágios da pesquisa. E, finalmente, os resultados de pesquisa para "coma no Kursk" são mais de 500 resultados. Muitos deles foram encontrados da mesma maneira e, portanto, têm a mesma classificação. Eles serão classificados por popularidade do usuário.

Conclusão

Recebemos a extradição com muitos cafés e restaurantes e, alegremente, vamos jantar. Obtivemos todos os resultados em uma fração de segundo. Nem precisamos de uma conexão à Internet.

O aplicativo armazena índices de pesquisa no dispositivo. Esse esquema nos fornece tarefas não triviais de otimizar a compactação de dados e a velocidade de processamento - afinal, a pesquisa deve funcionar rapidamente em uma ampla variedade de dispositivos móveis! No entanto, esta é uma história completamente diferente.

Hoje, tentei abrir o capô do nosso mecanismo de pesquisa e mostrar como ajudamos os usuários a encontrar o que precisam na cidade e fazê-lo de maneira rápida e conveniente. Espero que tenha sido informativo.