domingo, 21 de outubro de 2007

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

Veja as primeiras partes da série:

Primeira parte: Como funciona uma Máquina de Busca?
Segunda parte: Como funciona uma máquina de busca? - Crawlers/Spiders/Robôs/Coletores
Quarta parte: Como funciona uma Máquina de Busca? - Processador de Consultas

Neste terceiro artigo da série, vou explicar o funcionamento da parte de um motor de busca que nos permite procurar poucas palavras em bilhões de páginas na Web em um tempo aceitável. Sem o processo de indexação seria impossível encontrar todas as ocorrências de uma palavra e mostrá-las na tela de resultados para o usuário. Mas como isso tudo funciona?

Indexação

Esta etapa consiste basicamente em varrer toda a coleção de documentos (páginas, arquivos de texto, slides, pdfs...) coletados pelo Crawler e "indexar" todas as palavras e suas ocorrências. Mas o que isso significa?

Indexar uma palavra significa procurar todas as ocorrências da mesma e guardar essa informação de alguma forma. De forma análoga, indexar um texto é o mesmo que pegar todas as palavras que ocorrem nele e quantas vezes cada uma aparece. Muitas vezes é interessante também guardar a posição da ocorrência dos termos em relação ao documento. Veja o exemplo:

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.

A forma com que a ocorrência de um termo vai ser especificada no índice invertido (visto acima) é chamada de granularidade. As formas mais comuns são dizer em qual documento aquela palavra aparece (caso acima e mais básico), dizer em qual parágrafo, bloco, ou guardar até a posição exata dentro do documento. Com certeza as máquinas de busca atuais usam uma granularidade no mínimo por parágrafo. Só dessa forma pode-se achar rapidamente a parte da página onde ocorre os termos da consulta e então gerar aquela prévia que aparece em baixo de cada resultado:

Alguns detalhes!

As coisas não são simples assim. Analisando a estrutura de índice invertido, pense só na lista de ocorrências da palavra "a", ou de um "and". Gigantesco né? Imagine em quantos milhões de páginas estes termos ocorrem e quantas milhões de vezes. Este palavras são chamadas de stopwords. Como elas não acrescentam muito significado a uma consulta (mais ou menos) é comum excluir estas do processo de indexação, liberando uma quantidade grande de espaço em disco, além de diminuir o processamento na hora da consulta. As máquinas de buscas atuais não fazem isso. Eles tem como manter as listas de ocorrências gigantescas e o fazem pois as stopwords são úteis em muitos casos na hora de processar a consulta. Ainda mais com gente procurando: "Como fazer slaide no orkut e mandar scraps pros amigos". Além disso, uma palavra sem muito peso num idioma pode ser uma palavra muito usada em outra.

Outra coisa muito comum é o Stemming das palavras antes do armazenamento no índice. Consiste basicamente de uma operação que deixa a palavra no singular e tira alguns sufixos/prefixos, deixando-a mais "seca". Desta forma, se você procurar por algo no plural você vai achar resultados no singular e vice-versa. Este procedimento pode variar muito de uma máquina de busca para outra, mas é certo que manter uma lista de ocorrências para "carros" e outra para "carro" vai complicar na hora de processar a consulta. Se alguém procurar por "venda de carro", ele pode não achar a página com o título "Venda de Carros usados com 90% de desconto!". Coitado do cara que não achar esta página né?

Existem muitos outros detalhes. Pode-se, por exemplo, criar relações entre as palavras para aumentar as possibilidades na resposta à consulta. Na realidade cada máquina de busca implementa da sua forma. No geral, todas remetem ao básico que foi apresentado aqui neste artigo.

Para quem quiser se aprofundar, pode dar uma olhada no artigo da Wikipedia: Index (search engine). Achei também este pdf de uma aula que também tem alguns detalhes interessantes. Também podem dar uma olhada no artigo do Sergey Brin e Lawrence Page descrevendo o protótipo do Google. O Paulo Rodrigo Teixeira me mostrou este esquema animado explicando o funcionamento do Google, vale dar uma olhada.

Qualquer dúvida, sugestão ou dica é só deixar nos comentários. Próxima parada: "Como funciona uma Máquina de Busca? - Processador de Consultas".


Leia também a quarta parte da série: Como funciona uma Máquina de Busca? - Processador de Consultas

Nenhum comentário: