Máquinas de busca
For geeks dezembro 20th, 2008
Bom, como minha área de pesquisa é essa, vai bem começar postando sobre o assunto.
Primeiramente, máquinas de buscas servem para pesquisar em vários documentos, os que são importantes a nossa indagação. Melhor exemplo: Google.
Você tem a web inteira, com trilhões de páginas sobre quaisquer assuntos imagináveis, mas num determinado momento pode decidir querer saber mais sobre a extinção do Diabo da Tasmânia. Como fazer? Procurar no google, claro. Mas como isso funciona? Olhando uma por uma não é. Pelo menos não durante a sua consulta. Existe uma infinidade de métodos a fim de fazer isso e é sobre isso que pretendo falar, de modo geral, aqui e agora.
As máquinas de busca, usadas para a web, sistemas de bibliotecas ou qualquer outro fim, se dividem basicamente em três partes: Coletor, Indexador e Processador de Consultas. A saber:
Usando a web como um clássico exemplo, o coletor é o responsável pela busca de cada página e guardá-la de algum jeito para que durante a consulta, ela possa ser encontrada.
Em geral, todo o html das páginas é guardado, e este é tratado posteriormente. Muitos outros fatores estão envolvidos. Para percorrer a web é preciso caminhar por ela, página por página, o que pode levar a web a ser considerada como um grafo,onde cada página é um nó e possui apontadores para as outras páginas e assim, esta vai sendo mapeada. Vale lembrar que os apontadores que levam uma página a outra são, basicamente os link que estas páginas possuem. Ainda assim, existe muito mais coisa envolvida, mas é melhor deixar para uma próxima oportunidade.
Depois de o coletor ter os documentos (as páginas) eles devem se organizar de modo a facilitar as consultas. Como fazer isso? Indexando!
O primeiro passo para indexar é analisar as palavras em cada página, gerando assim, um vocabulário de toda a base de documentos. Esse vocabulário deve relacionar as palavras de um modo em que cada termo faça surgir uma lista de documentos em que este termo aparece. Essa lista é conhecida como lista invertida ou arquivo invertido. Vale explicar o motivo deste nome: A idéia de fazer uma busca de documentos nos faria pensar em algo como: Para cada documento, qual é o conjunto de palavras que o contém? Isso deveria ajudar na busca, mas é exatamente o oposto.
Por que fazer isso? Imagine que uma consulta possua duas palavras, digamos Diabo e Tasmânia. É muito mais rápido procurar a partir de todos os documentos dos quais já sabemos de antemão que contêm essas palavras do que olhar cada documento em busca das palavras. Se você tem um vocabulário com 1 milhão de palavras, você consegue reduzir a busca em 2/1000000 (bom, não exatamente, mas é uma aproximação razoável).
ETendo as listas invertidas, sabemos quais páginas provavelmente estarão na resposta da pesquisa. Restam duas coisas: ter a certeza de que os documentos estarão mesmo na resposta e ordenar estas respostas pela relevância em relação à consulta. Este é o trabalho do processador de consultas.
E é aí que entra a parte matemática. Existem inúmeros métodos e fórmulas, que ajudam a realizar esta organização. O mais interessante, é o chamado modelo vetorial.
A idéia básica é relativamente simples: o documento e a consulta são tratados como vetores. Os vetores de documentos que ficarem mais próximos do vetor da consulta são os que têm maior relevância para ela. Pretendo explicar isso com mais detalhes futuramente.
Ainda tem muito mais coisa, claro. Você provavelmente já ouviu falar em page rank e outras métricas que ajudam nessa decisão de quais documentos devem estar entre as primeiras numa máquina de busca, mas elas envolvem algo mais avançado que vou tentar abordar futuramente. Tudo a seu tempo.
by offsFX
English 
Português 
dezembro 20th, 2008 at 07:34
Próximo artigo:
“O que é um grafo”