Entendendo um motor de busca

De maneira geral, um sistema encarregado de fazer buscas em um conjunto de documentos (seja ele na Web ou não) consiste basicamente de 3 partes: coleta/armazenamento de documentos, indexação dos mesmos e processamento de consultas. Vamos explicar cada um deles:

Coleta e Armazenamento de documentos

Também chamada de Crawler, Spider ou Robô. A primeira parte do sistema é encarregada de varrer a base de documentos (no nosso caso a Web) e guardar várias informações como o conteúdo (já tirando o HTML) e a estrutura de links. Também é muito importante saber como o coletor irá "caminhar" pela Web, quais URLs irá passar e quais sites irá coletar. É nesta fase que são armazenadas localmente muitos detalhes de cada página que serão usadas posteriormente para saber quais páginas devem aparecer por primeiro nos resultados de uma consulta.

Indexação

Parte primordial do sistema. Nela faz-se uma varredura em cada documento da base de dados (conseguida através dos coletores) verificando as ocorrências de cada palavra. Armazenando estas informações num Índice Invertido uma estrutura de dados organizada desta forma:

Palavras: Lista de ocorrências da palavra

Neste exemplo, a palavra casa aparece no documento B 3 vezes e no documento C 12 vezes. Já a palavra blog aparece apenas no documento A.

Organizando a informação desta forma pode-se saber rapidamente em que páginas da Web uma palavra aparece, facilitando (e muito) na hora da consulta. Informação útil para calcular a relevância da página na hora de ordenar os resultados da consulta.

Processamento da consulta

Para cada consulta feita a máquina de busca varre o índice invertido de termos e vê onde eles aparecem. Através de algoritmos (Espaço vetorial, Language Models e outros) os documentos que contém as palavras da consulta são ordenados de acordo com critérios pré-definidos. Entre eles: importância de uma palavra ("cachorro" descreve algo melhor que a partícula "de"), número de vezes que um site é referenciado através de links, similaridade entre a consulta e o texto de um documento, entre outras coisas. A partir de todas essas informações (e outras) é feita uma ordenação no resultado da consulta. Apresentando primeiro as páginas consideradas mais relevantes.

Como funciona uma máquina de busca? - Crawlers/Spiders/Robôs/Coletores

Coletor, Spider, Crawler, Robôs

Sim, todos os termos acima se referem a mesma coisa: A parte da máquina de busca responsável por coletar os documentos da Web a serem indexados e consultados posteriormente. Mas como eles funcionam? Os coletores começam com um conjunto inicial de URLs para serem visitadas. O sistema então baixa estes documentos e deles extrai os links, conteúdo e outras informações. As URLs dos links extraídos são guardadas para que se possa acessá-las posteriormente. O processo é mostrado na figura abaixo:

Para que tudo isso funcione o processo todo é dividido em partes (componentes):

Coletores - Fazem a requisição de páginas aos servidores HTTP. Extraem os links das páginas recebidas e enviam ao escalonador. Requisitam do escalonador uma ou mais URLs a serem coletadas.

Servidor de Armazenamento - Recebem os documentos coletados e os armazena localmente. Fazem a extração (também chamado de parsing) do texto e conteúdo em outros formatos: PDF, Word, Powerpoint, etc.

Servidor de Nomes - Faz um controle das requisições DNS (Domain Name System) para que os coletores não façam requisições remotas. Em outras palavras não deixa o coletor procurar onde está um site se o Servidor de Nomes já tem guardado essa informação.

Escalonador - Responsável por decidir qual a próxima URL a ser coletada. Coordenando dessa forma a ação dos coletores. Deve garantir que não haverão coletas repetidas.

O escalonamento é um função crítica da coleta. É complicado coletar TODAS as páginas da Web. Por isso são utilizadas técnicas para tentar pegar apenas as "melhores" páginas. Alguns exemplos são:

Em Profundidade - Resulta em uma coleta “focada”, pois você caminha por todo um determinado site antes de ir para o próximo. Pode-se limitar o número de níveis.

Em Largura com sufixo de URL - Exemplo: *.terra.com.br. Garante cobertura balanceada entre sites. Técnica bastante utilizada.

Baseadas em Ranking de URLs - Pode ser baseada em conteúdo, em popularidade (número de acessos) ou em conectividade (número de referências).

Baseada em Conectividade - Pode ser de dois tipos:

Referências (Backlink count) - Quanto mais links apontando para uma página maior a "importância" dela.

Variações recursivas - Links vindos de páginas com maior "importância" tem maior peso. Esta é a técnica usada pelo algoritmo PageRank.

Existem algumas outras dificuldades e observações relativas aos coletores na Web. Como muitos sabem, os robôs das máquinas de busca devem seguir algumas restrições especificadas no arquivo robots.txt e em meta-tags. Além disso, é considerado ético não bombardear o servidor de um site com inúmeras requisições sequenciais.