Como funciona nosso mecanismo de busca construído com Elasticsearch?

A Gupy possui milhares de vagas publicadas, com isso nossos candidatos começaram a precisar de um local centralizado para procurar aquelas que mais se adequam ao seu perfil. Daí nasceu nosso Portal de Vagas! Uma das funcionalidades mais importantes do portal é de permitir com que o usuário possa fazer uma busca textual e encontrar as vagas desejadas. Mas como foi possível construir essa funcionalidade?

Nesse artigo vamos apresentar:

1. o que é o Elasticsearch e porquê ele é adequado para construir mecanismos de busca.
2. como ele se organiza internamente para salvar os dados de uma forma que facilite a busca.
3. como ocorre o processo de busca e ranqueamento de resultados. 

O que é Elastic Search?

Elasticsearch é um banco de dados de código aberto, altamente distribuído e orientado a documentos. Ser orientado a documentos significa que ao invés de possuir conceitos de tabelas e registros, como comumente vemos em bancos relacionais, ele trabalha com índices e documentos. Não vamos entrar em detalhes do que isso significa aqui, mas basta entender que índice é equivalente a uma tabela e o documento é equivalente a um registro, só que ao invés de estar no formato de linhas e colunas ele se parece mais como um objeto json.

Uma das características importantes dele é que foi pensado para ser distribuído por design, ou seja, desde o início de sua concepção todas as funcionalidades já foram desenvolvidas para esse tipo de ambiente. Existe uma complexa arquitetura de nós e índices que permitem que ele seja muito rápido para realizar buscas.

Outro ponto relevante do ElasticSearch é que ele possui diversos mecanismos para acelerar buscas textuais e permitir a construção de regras para ranquear os resultados. Boa parte disso se deve ao fato de ele utilizar um mecanismo chamado de índice invertido. O índice invertido nada mais é do que uma tabela em que a chave é o valor do dado e o resultado são identificadores do dado que possuem aquele valor, ao contrário do que geralmente ocorre. 

Na figura acima podemos ver claramente a diferença entre um índice e um índice invertido. No índice estamos interessados em buscar um dado a partir de seu identificador, enquanto no índice invertido estamos interessados em achar os identificadores que possuem determinado valor. Em breve vamos entender melhor como isso ajuda a buscas e ranquear bases de dados textuais.

Devido a sua alta performance de busca e mecanismos de tratamento textual, o ElasticSearch se torna uma excelente ferramenta para criar mecanismos de busca.

O que acontece quando criamos uma nova vaga?

Antes de tudo precisamos definir um mapeamento para nossos dados. No caso vamos definir que uma vaga de emprego é composta apenas das seguintes informações: nome, nome da empresa e cidade. A definição do que é uma vaga no ElasticSearch é algo do tipo:

obs: o tipo keyword define um valor textual que não sofrerá nenhum tipo de processamento

Após definir o nosso mapeamento podemos então seguir no entendimento de como funciona a inserção de um novo dado. A imagem abaixo ilustra um esquema do que acontece com cada campo do documento. Campos que não são do tipo text são inseridos diretamente, já campos do tipo text passam por uma etapa de pré-processamento e outra de atualização do índice invertido antes de serem inseridos. A seguir vamos entender melhor o funcionamento dessas etapas supondo a inserção de um nome de vaga.

O pré-processamento é o primeiro passo da inserção de um dado tipo text, ele ainda pode ser subdividido em três passos: (a) Char filter; (b) Tokenizer; (c) Token Filters. Essas etapas são definidas através de um analyzer, no exemplo a seguir vamos utilizar o analyzer padrão para português brasileiro.

Fonte: https://www.elastic.co/guide/en/elasticsearch/reference/current/analyzer.html

(a) Char-Filters: etapa que permite remoção ou alteração de caracteres. Dentre as operações comuns estão a remoção de tags HTML, transformação ou remoção de caracteres de diferentes alfabetos. 

(b) Tokenization: procedimento que transforma uma string em uma lista de ‘tokens’. O comportamento padrão consiste em remover as pontuações e fazer a separação através dos espaços.

(c) Token Filters: Apesar do nome, aplica operações de adição, remoção ou alteração à nível de token. Exemplos de uso:

• Stop words: remove palavras com baixo valor semântico.
• Lowercase e asciifolding: coloca todos caracteres em minúsculo e remove acentuação.
• Stemming: remove sufixo dos tokens.

O próximo passo da inserção é a atualização do índice invertido. Vamos supor que o novo dado a ser inserido é uma lista de tokens [‘analist’, ‘produca’]. Repare que o já existe um registro de id 1 que possui o termo ‘produca’, dessa forma é atualizado o índice invertido desse token, inserindo o id 2 na lista de documentos e aumentando a frequência. O token ‘analist’ ainda não existe no índice invertido, então vamos criar esse registro, definindo sua frequência como 1 e adicionando o id 2 na lista de documentos.

obs: Inserimos o dado de frequência na tabela para facilitar a visualização do processo de busca.

Após todo esse processo o dado é finalmente inserido no documento. Então podemos seguir para o próximo passo: como acontece a busca de um dado no banco?

O que acontece quando realizamos uma busca?

Quando é realizada uma busca no nosso portal de vagas acontecem três passos para que o dado possa ser retornado da melhor forma possível: (a) pré-processamento dos dados de busca; (b) execução de filters e queries; (c) ordenação dos resultados por relevância.

(a) Pré-processamento: os dados de entrada são pré-processados de acordo com o mapeamento definido no documento. No nosso exemplo temos que o nome e a empresa estão definidas com o analyzer de português brasileiro, enquanto a cidade é definida como keyword, por isso não acontece nada nessa etapa para esse campo.

(b) Avaliação de condições: para compreender como é possível filtrar e ranquear dados é necessário entender alguns conceitos: query vs filter; should vs must.

• Filter: significa que a avaliação a ser realizada retorna sempre um valor 0 ou 1, não existe meio termo. A negativa em um filter significa que o dado não será retornado.
• Query: significa que a avaliação a ser realizada pode retornar um valor entre 0 e 1. A negativa em uma query não necessariamente significa que o documento não será retornado, isso depende se ele está em uma cláusula must ou should. Esse tipo de operação é útil, por exemplo, quando é necessário calcular a similaridade entre um texto de busca e o nome de vaga. Pode fazer sentido retornar uma vaga que seja similar, mas não igual, ao texto buscado.
• Must: significa que a condição deve resultar em um valor maior do que zero, caso contrário o documento não é retornado.
• Should: significa que uma condição pode resultar em um valor maior do que zero, caso contrário aquele documento será retornado, porém com uma relevância menor.

Vamos supor que temos a seguinte condição de avaliação de busca:

Para entendermos o funcionamento deste filtro vamos considerar a seguinte entrada de dados:

Além disso, vamos considerar que na base de dados existem apenas os documentos da figura abaixo. O documento (I) não será retornado porque o campo cidade está dentro do filter e os valores são diferentes. O documento (II) também não será retornado porque o campo nome está dentro da cláusula must dentro da query, e não existe nenhum termo comum entre a busca e o documento. O documento (III) será retornado, porque ele tem match perfeito em todos os campos. O documento (IV) também será retornado, como a empresa está dentro de uma cláusula should, o fato de não bater os valores não impede que o documento seja retornado, significa apenas que esse registro será pior ranqueado.

(c) Ordenação dos resultados: como apresentado no exemplo anterior, cláusulas should contribuem para aumento do score de relevância de um documento. Então no nosso exemplo anterior temos que o primeiro documento vai ter um score maior, porque existe match na empresa, o que não ocorre no segundo documento.

Mas, como são calculados esses scores para cada campo? O cálculo se baseia numa técnica estatística chamada de TF-IDF (Term Frequency - Inverse Document Frequency). A ideia básica consiste em beneficiar resultados que exibam o maior número de matchs com termos buscados (Term Frequency), balanceado com o quão raro é aquele termo no universo conhecido (Inverse Document Frequency). A ideia geral é de que palavras menos comuns entre os diferentes documentos possuem maior peso semântico.

Vamos pensar que você quer buscar uma vaga de “Analista Financeiro”, mas infelizmente não tem nenhuma vaga exatamente com esse título. Provavelmente faz mais sentido ter melhor ranqueada uma vaga de “Assistente Financeiro” do que outra de “Analista de RH” e, graças ao TF-IDF, é isso que acontece. Ainda que ambas vagas possuam match com apenas um dos termos pesquisados, a palavra “Financeiro” é provavelmente menos comum no universo de todas as vagas do que a palavra “Analista”, dessa forma, o match com “Financeiro” beneficia mais a nota de relevância. O TF-IDF não vai acertar em 100% dos casos, mas estatisticamente ele é considerado uma solução razoável para ranquear resultados.

Vamos supor que o cálculo que o ElasticSearch faz é de considerar a frequência no documento dividido pela frequência em todos documentos*. Supondo que foi buscado o termo [‘analist’, ‘produt’] e o índice invertido está no estado como descrito na imagem abaixo. Para avaliar a nota do documento com id 1 começamos calculando a nota do termo ‘analist’, ele está presente uma vez no documento e tem frequência global igual a 2, dessa forma seu score será algo próximo a 0,5. De forma análoga o termo ‘produt’ vai ter score de 1.

*o cálculo exato realizado pela ferramenta é diferente, mas a ideia é a mesma. Para ver mais detalhes clique aqui.

Nesse artigo tivemos uma breve introdução do que é o ElasticSearch e porque ele é adequado para construir um mecanismo de busca. Além disso, vimos em detalhes como acontece a inserção de um documento novo e como é realizada a busca na base de dados utilizando como exemplo nosso Portal de vagas. 

Quer fazer parte do nosso time? Encontre a vaga perfeita para você na nossa página de carreiras!