sábado, 7 de julho de 2012

A fórmula no algoritmo do Google

A história do Google começou em 1996 quando Larry Page e Sergey Brin, ambos estudantes de Ciência da Computação na Universidade Stanford, deram início ao desenvolvimento de um mecanismo de busca para a Web. No ano seguinte este mecanismo recebeu o nome Google.

Ainda em Stanford, Larry e Sergey desenvolveram um método para graduar as ligações de um banco de dados de documentos, a World Wide Web ou qualquer outro banco de dados de hipertexto. Este método foi patenteado pela Universidade Stanford e posteriormente nomeado pelo Google como PageRank.

O sistema PageRank é usado pelo motor de busca Google para ajudar a determinar a relevância ou importância de uma página. O PageRank é a característica mais importante do algoritmo do Google.

O PageRank assina uma posição ou nota a cada resultado de busca. Quanto maior a nota, mais alta sua posição na lista de resultados. As notas são determinadas, em parte, pelo número de outras páginas de Web com links para a página visada. Nem todos os votos tem o mesmo valor. Os votos de páginas de alta popularidade na Web contam mais do que os votos de sites de baixa popularidade. Quanto mais links uma página de Web oferece, mais diluído seu poder de votação.

Esta estrutura de links da web usada para calcular a classificação de cada página fornece uma ajuda importante para produzir resultados precisos. Em um documento, apresentando o protótipo do mecanismo de busca Google, Sergey Brin e Larry Page descreveram o algoritmo do PageRank (PR). O PageRank é um algoritmo recursivo, pois a mudança do PR de uma página afeta os PRs das outras páginas. Uma mudança no PR de outra página também mudará o PR da página consequente e assim sucessivamente até que, inclusive, pode afetar o PR da página inicial.

Uma página A possui as páginas T1...Tn que apontam para ela. O parâmetro d é um fator de amortecimento que pode atribuir valor entre 0 e 1. Usualmente definido d para 0,85. E C(A) é definido como o número de links saindo da página A. O PageRank da página A é dado na fórmula PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)).



Note que os PageRanks formam uma distribuição de probabilidade sobre as páginas web, então a soma de todos os PageRanks das páginas Web será um.

Um PageRank ou PR(A) pode ser calculado usando um simples algoritmo iterativo. Um PageRank para 26 milhões de páginas web pode ser calculado em poucas horas em uma workstation de tamanho médio.

Saiba mais em:

The Anatomy of a Large-Scale Hypertextual Web Search Engine (http://infolab.stanford.edu/~backrub/google.html)

United States Patent 6,285,999 (http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=6285999.PN.&OS=PN/6285999&RS=PN/6285999)

Nenhum comentário:

Postar um comentário