sexta-feira, 23 de novembro de 2007

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

Veja as primeiras partes da série:

Como funciona uma Máquina de Busca?
Como funciona uma Máquina de Busca? - Crawlers/Spiders/Robôs/Coletores
Como funciona a Indexação em uma Máquina de Busca?

Nesta parte da série, vou explorar nas máquinas de busca o componente mais próximo dos usuários e com o qual interagimos diretamente. O processador de consultas é responsável por receber as palavras-chave que você coloca na "caixinha do Google" e transformá-las no conjunto de respostas relevantes que você está acostumado a ver.

Por trás da imagem acima existe o processador de consultas a parte da máquina de busca responsável por calcular a relevância de cada página de acordo com a sua consulta. Como isso é feito?

Primeiramente, o elemento primordial para processar uma consulta é o índice invertido (explicado no último artigo). É através dele que logo depois de você clicar em "Pesquisar" o sistema consegue encontrar todos os documentos os quais possuem os termos que você quer procurar. Ainda no exemplo da figura acima, procura-se no índice invertido as palavras "blog" e "hummel". Em relação a partícula "do", não há consenso entre indexar ou não stopwords (preposições, artigos e outros) já que elas são extremamente frequentes em textos, criando listas invertidas gigantes. Apesar de elas oferecerem pouco significado a consulta (por isso nem sempre precisam ser indexadas) é provável que os grandes buscadores da Web indexem estes pequenos termos assim mesmo (por que eles podem arcar com os custos).

Certo, sabe-se quais páginas possuem as palavras que eu busquei. E agora?

Precisamos entender as medidas TF-IDF, muito usadas nos modelos de Recuperação de Informação. TF significa Term Frequency, ou frequência do termo, e IDF Inverse Document Frequency, ou frequência inversa do documento. A primeira é basicamente quantas vezes uma palavara aparece num documento, ou seja, para cada página Web uma dada palavra tem um TF específico. Já o IDF é um único valor para cada palavra do índice, e mede o "quão importante" ela é naquele conjunto de documentos (no caso, a Web). Em miúdos, quanto mais rara a palavra for, maior seu IDF.

Dada uma página, verifica-se o TF de cada termo da consulta. A relevância de cada documento que contém um destes termos é calculada juntando-se TF-IDF das palavras-chave. No final do processo cada página possui um score (um grau de relevância). É com este score que são ordenados os resultados que vão aparecer na tela.

Notem que não mencionei as MUITAS outras técnicas que ajudam no rankeamento dos resultados, muitas delas conhecidas pelo pessoal de SEO. O PageRank das páginas influencia. Se a consulta se parece muito com uma frase da página ou título da mesma (consulta: "blog do hummel", por exemplo). Entre outros ajustes que as máquinas de buscas venham a fazer (não são poucos e é difícil de falar de todos).

Preferi omitir estes ajustes para poder explicar o modelo Espaço Vetorial puro, que é a base para a maioria dos sistemas de busca (tanto na Web quanto em outros ambientes). Apesar de existirem outros modelos para a construção de sistemas de Recuperação de Informação, como o BM25 e outros métodos probabílisticos, o modelo Vetorial ainda é o mais consolidado pelo sua facilidade de implementação e resultados muito bons que dificilmente são superados por outros modelos.

Para quem quiser ler um pouco mais sobre o assunto vale dar uma lida:

O Futuro das Máquinas de Busca.
Information Retrieval

6 comentários:

Teclado de computador disse...

Muito bom esse artigo.

brazz disse...

Olá,

Eu também escrevi algumas páginas sobre esse tema:
http://www.sites-de-busca.com/basico/

É bom ver que alguém mais se interessa por esse assunto.

Abraço,

Felipe Hummel disse...

Com certeza! Máquinas de busca é um assunto bem interessante, vale a pena abordá-lo e esclarecer as coisas!

Abraço!

cilene disse...

Achei seu post bem interessante. nao entendo desse assunto. Mas acho o sistema do google meio falho. A gente nunca encontra direito o que realmente estå procurando

Felipe Hummel disse...

O sistema do Google é bom, provavelmente o melhor sistema de busca na Web. Algumas vezes não sabemos tirar o máximo de proveito. Ou simplesmente não sabemos como buscar.

Se eu não acho algo que procuro no Google é provavelmente por aquela coisa "não existe" daquela forma como estou procurando. Por exemplo:

Se eu buscar por "como pegar e salvar imagem em Java".

Pra mim, isso pode fazer todo o sentido, mas pode ser que ninguém na Web toda tenha escrito o mesmo problema desta mesma forma. Mas talvez procurando de outra forma:

"salvando imagem Java"

Provavelmente alguém vai ter escrito desta forma em algum lugar da Web.
hehehue

É tudo uma questão de saber procurar o que outras pessoas já escreveram.

Abraço!

Philipe disse...

MT bom cara adorei a dica vou usar
Blog Do Philipe