Como os mecanismos de busca funcionam por baixo dos panos

Todos nós já paramos pra imaginar como o Google funciona?, como ele consegue acessar tão rapidamente pesquisas e como consegue encontrar termos mesmo quando digitamos errado.

A resposta é que ele realiza uma série de mecanismos internos antes de te entregar o resultado.

Algumas formas de realizar a busca

Para realizar uma busca, depende muito do volume de dados, velocidade e outros atributos. Algumas formas são: operador LIKE, Full Text Search (FTS) e usando alguma ferramenta como o Elasticsearch.

O operador LIKE seria o pior caso de uso. Ele pode ser ineficiente com muitos dados, pois dependendo da consulta pode precisar percorrer muitas linhas da tabela. Além disso, possui baixa precisão, pois ele não entende idioma, relevância ou significado, apenas procura por uma sequência de caracteres.

O FTS já é um pouco melhor, pois resolve alguns desses problemas. Ele possui um ranking de relevância onde atribui pontos para trazer uma busca melhor e pode realizar stemming e outras etapas de processamento específicas para determinados idiomas. No PostgreSQL, por exemplo, podemos configurar o FTS para português. Ele também utiliza índices especializados, como o índice GIN (Generalized Inverted Index).

O Elasticsearch seria uma solução mais completa para determinados cenários, mas pode ser overengineering dependendo do tamanho e da necessidade do projeto. (Vou escrever um artigo dedicado somente ao Elasticsearch.)

Como funciona por baixo dos panos

Mas afinal, como realmente uma busca é realizada por baixo dos panos?

O processo inclui algumas etapas, com técnicas de pré-processamento, indexação e algoritmos de busca para tentar encontrar os resultados mais relevantes.

Pré-processamento

Inicialmente, o sistema faz um analyzer, onde isso inclui algumas etapas de pré-processamento.

O sistema realiza uma tokenização no termo buscado. Se o termo buscado for "como o google funciona", ele separa em tokens:

["como", "o", "google", "funciona"]

Ele pode fazer uma limpeza de stopwords, que são palavras muito comuns que geralmente possuem pouca importância para determinar o assunto do texto. Nesse caso, o "o" poderia ser removido.

Após isso, pode realizar stemming, processo que reduz palavras para uma forma comum através de regras. Por exemplo, palavras como "correr", "correndo" e "correu" podem ser reduzidas a uma forma semelhante, dependendo do idioma e do algoritmo utilizado.

Também existe a lemmatização, que é um processo mais linguístico e busca reduzir a palavra ao seu lema, utilizando informações de vocabulário e morfologia. Por exemplo, palavras como "went" e "going" podem ser relacionadas ao lema "go", dependendo da ferramenta utilizada.

Essas etapas são importantes porque permitem que diferentes formas de uma palavra possam ser relacionadas durante a busca.

Indexação

Agora entra uma ideia extremamente importante. A limpeza foi feita, mas como o sistema encontra os dados sem ter que buscar registro por registro e pesar quando a base de dados for gigante?

Aí entra o índice invertido.

Um índice invertido, como o próprio nome já diz, funciona de forma diferente de um índice tradicional. Ele foca no conteúdo das palavras e é responsável por mapear onde os termos aparecem, em vez de simplesmente listar o conteúdo dentro de cada documento.

Exemplo:

• Documento 1: Gato gosta de peixe
• Documento 2: Cachorro gosta de carne

O índice, ao invés de dizer:

documento → palavras

faz:

palavra → documentos

Ficaria mais ou menos assim:

Gato     → [Documento 1]
Gosta    → [Documento 1, Documento 2]
Cachorro → [Documento 2]
Carne    → [Documento 2]
Peixe    → [Documento 1]

Assim, quando o usuário pesquisa por uma palavra, o sistema consegue consultar diretamente a estrutura de índice associada àquele termo, em vez de precisar analisar todos os documentos individualmente.

Claro que os mecanismos reais são mais complexos que esse exemplo, mas essa é a ideia principal por trás de um índice invertido.

Algoritmos

Até agora, foram realizados algoritmos que rodam em sistemas básicos de busca, como o Full Text Search. Isso já trouxe uma grande melhoria, mas como classificar os termos buscados de forma mais inteligente para o usuário?

Como saber que, quando o usuário pesquisa por "bolo de chocolate", determinados documentos são mais relevantes do que outros?

Aí entram os algoritmos de ranking.

TF-IDF

TF-IDF significa Term Frequency – Inverse Document Frequency. É uma medida estatística usada para indicar a importância de uma palavra em um documento em relação a uma coleção de documentos.

Term Frequency (TF): mede quantas vezes um termo ocorre em um documento. Como os documentos variam em extensão, a frequência pode ser normalizada para evitar que documentos maiores tenham vantagem apenas por possuírem mais palavras.

Inverse Document Frequency (IDF): mede o quão rara ou comum é a palavra em todo o conjunto de documentos. Palavras que aparecem em muitos documentos recebem peso baixo, enquanto palavras mais raras e informativas recebem peso alto.

O IDF olha para documentos diferentes, então se aparecer:

FERRARI
FERRARI
FERRARI

no mesmo documento, isso não faz o IDF aumentar. O IDF está relacionado à quantidade de documentos diferentes em que o termo aparece.

O resultado final combina esses valores, normalmente através de TF × IDF. Ele reduz a influência de termos genéricos e destaca palavras que realmente ajudam a definir o conteúdo daquele texto.

Pegue a seguinte lista de documentos:

• Documento 1: Carro é encontrado após procura policial
• Documento 2: Carro top 1 da Chevrolet está em promoção
• Documento 3: Colisão entre carros da Chevrolet causa trânsito

Se a pesquisa do usuário for:

Carro promoção

o Documento 2 tende a ser mais relevante, pois contém os termos da busca de maneira mais relacionada.

Se fosse:

Carro Chevrolet

o Documento 2 e o Documento 3 provavelmente seriam mais relevantes que o Documento 1, pois possuem "Chevrolet" além de termos relacionados a "carro".

O objetivo do ranking é justamente tentar ordenar os documentos de acordo com sua relevância para aquela consulta.

BM25

O BM25 (Best Match 25) é um modelo de recuperação de informação derivado das ideias do TF-IDF. Ambos tentam responder:

“Quão relevante esse documento é para essa consulta?”

Porém, o BM25 faz isso de uma maneira diferente e mais sofisticada.

Ele leva em consideração o comprimento do documento e aplica uma saturação na frequência dos termos. Atualmente, ele é utilizado como algoritmo de similaridade padrão em sistemas como o Elasticsearch para determinados campos de texto.

Ele possui duas características importantes:

• Saturação da frequência do termo
• Normalização do comprimento do documento

Saturação do termo (k₁):

Em um modelo baseado apenas em frequência, se a palavra "computador" aparece 100 vezes em um artigo, ela poderia ganhar um peso muito maior do que em um artigo onde aparece 5 vezes.

O BM25 aplica uma função que achata esse crescimento.

Ele entende que a diferença entre 0 e 1 aparição é muito relevante, mas a diferença entre 20 e 21 aparições é muito menor.

Ou seja, repetir uma palavra muitas vezes não faz um documento se tornar infinitamente mais relevante.

Normalização do comprimento (b):

Documentos longos naturalmente possuem mais palavras e, consequentemente, maior chance de repetir determinados termos.

O BM25 ajusta o score comparando o comprimento do documento atual com o comprimento médio dos documentos da coleção.

Se o texto for muito longo, o peso dos seus termos pode ser reduzido, dando mais chance para documentos menores e mais diretos quando eles forem mais relevantes para a consulta.

Conclusão

Essa seria uma forma resumida de como os fundamentos dos mecanismos de busca funcionam internamente.

Claro que o Google é muito mais complexo que isso. Ele possui diversas outras camadas, como correção ortográfica, compreensão semântica, sinais de popularidade, localização, personalização, machine learning e diversos outros mecanismos.

Mas essa é uma boa base para entender como muitos sistemas de busca textual funcionam.

A ideia principal é que o sistema não precisa simplesmente sair procurando palavra por palavra em todos os documentos.

Ele pode:

Pré-processar
      ↓
Indexar
      ↓
Encontrar candidatos
      ↓
Calcular relevância
      ↓
Ordenar os resultados
      ↓
Entregar a resposta

E é justamente essa combinação de pré-processamento + índice invertido + ranking de relevância que permite construir sistemas de busca muito mais eficientes e relevantes.