sexta-feira, 12 de outubro de 2007

Como funciona uma Máquina de Busca?

Nesta série de artigos vou mostrar os componentes básicos das máquinas de busca (Google, Yahoo, Live Search e afins). Vou primeiramente explicar de maneira geral e depois entrar em detalhes em como funciona o coletor, a indexação e finalmente o processador de consultas. No último artigo da série vou comentar algumas soluções open-source que qualquer um pode pegar e tentar começar sua própria máquina de busca, né Bruno?

Primeiramente, gostaria que vocês esquecessem um pouco de SEO. Até por que eu não vou comentar especificamente aspectos para otimização. Mas, de forma geral, entender o funcionamento das máquinas de busca pode te fazer enxergar o contexto das buscas e das técnicas usadas em SEO.

Tive a idéia de fazer essa série de artigos por que estou fazendo a matéria de Recuperação de Informação (information retrieval em inglês, ou só RI) na faculdade. Esta é a área da computação responsável pela coleta, filtragem ou busca de informação utilizando uma base de dados. A área de RI apesar de já existir a algumas décadas ficou mais conhecida e visada devido as pesquisas envolvendo máquinas de busca para a Web. Vale lembrar que existem também sistemas para procurar documentos dentro do seu computador (Google Desktop e similares) ou dentro dos arquivos de uma empresa ou instituição e estes utilizam as mesmas técnicas para achar uma página na Web.

Entendendo uma máquina 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. Vou 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

casa -> (B, 3) (C, 12)
carro -> (A, 10) (B, 6) (C, 12)
web -> (A, 2) (B, 3)
blog -> (A, 3)

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. Se você procurar por "web blog" na nossa base de dados de exemplo, pode ver que estes termos aparecem nos documentos A e B, além de saber quantas vezes a palavra se repete, 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.

Por enquanto é só. No próximo artigo vou explicar como funciona os Coletores das máquinas de busca.


UPDATE:

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

Terceira parte: Como funciona a Indexação em uma máquina de busca?

Quarta parte: Como funciona uma Máquina de Busca? - Processador de Consultas

6 comentários:

Anônimo disse...

Achei muito interessante este artigo e gostaria de conhecer mais sobre o assunto.
Vc tem links ou livros que possa indicar pra me aprofundar mais no tema?

Paulo Rodrigo Teixeira disse...

Legal e bem escrito.

parabéns.

Felipe Hummel disse...

Obrigado pelos comentários.
Em relação a links ou livros, durante os próximos artigos dessa série, onde vou explorar cada parte da maquina de busca individualmente, vou tentar colocar referencias pro pessoal se aprofundar.
Por enquanto um link interessante seria o How Stuff Works:
http://computer.howstuffworks.com/search-engine.htm
Pena que é em inglês e não aborda tudo que eu vou abordar aqui nos artigos, mas é uma boa leitura.
Se alguém tiver alguma dica de link ou livro fique a vontade.
Abraço!

Guido disse...

Olá Felipe,

muito bom esse artigo, amanhã irei ler o restante da série.

No começo desse artigo, você disse que estava estudando RI, essa matéria é de algum curso de faculdade? se sim, qual?

Abraços.

Felipe Hummel disse...

Opa Guido.
Faço Ciência da Computação na UFAM.
RI é uma matéria optativa que é oferecida. Muito interessante. O professor dessa matéria trabalhou no processador de consultas da Akwan a empresa de MG que foi comprada pelo Google uns tempos atrás.


Abraço!

Professor Augusto disse...

Muito bom meu garoto,
faço pós graduação em Educaçõa e Tecnologias e este artigo me ajudou muito em uma disciplina que estou estudando.
parabéns pela escrita e muito obrigado pela ajuda.