Sistemas de RI na Web
Bruno Almeida Pimentel (bap)
Mariane Mariz Vieira (mmv)
Renato Parente (rp2)
Roteiro
•
•
•
•
•
•
•
•
•
•
Introdução
Arquitetura
Indexação e Análise
Rankeamento
Crawlers
Browsing
Sistemas de Buscas
Metabuscadores
Conclusão
Referências
Introdução
• Evolução da Web
▫ 1969 - ARPANET (Telnet, FTP, e-mail, ...)
▫ 1989 – Nasce a Web (Tim Berners-Lee)
▫ 1990...
 1º Browser
 HTTP
 HTML
Introdução
• Evolução da Web
• 1995 – 60.374 sites
• 2010 – 206.026.787 sites
Fonte: http://news.netcraft.com/archives/category/web-server-survey/
Introdução
• Desafios
▫ Gigantesco banco de dados com estrutura
indefinida
▫ Formatos variados
▫ Páginas estáticas e dinâmicas
Introdução
• Desafios
Introdução
• Evolução dos engenhos de busca
▫ 1990 – Archie (indexava os diretórios)
▫ 1993 - W3Catalog (indexava o conteúdos das
páginas) – coleta manual
▫ 1993 – Wandex (1º web crawler)
▫ 1994 – WebCrawler (1º full text)
▫ ... – AltaVista, Yahoo!
▫ 1998 – Google (PageRank)
Arquitetura
• Crawler-Indexer centralizada
Indexação e Análise
•
•
•
•
•
Indexação full-text
Base de índices invertidos / Forward Index
Análise do Formato
Reconhecimento de Idioma
Processamento de Texto
▫ Eliminação de stopwords
▫ Operações de normalização
 Pontuação, espaços, uppercase,...
• Tokenization
• Reconhecimento da Seção
• Indexação de Meta Tag
Page Rank
• Algoritmos que atribuem pesos a páginas da
Internet hiperligadas
• Mede a importância da página usada em
motores de busca
Page Rank
• O nome “PageRank” é uma marca comercial da
Google
• A patente é atribuída à Universidade de Stanford
(Larry Page)
• Google tem direitos sobre a licença exclusiva da
patente
• Comprada pelo equivalente a US$ 336 milhões
em ações em 2005
Page Rank
• Usa o conceito de votação como parte do
algoritmo
• Um link entre páginas é como um voto
▫ Se há um link da página A para a B, então B recebe
um voto
• Analisa a página que recebeu o voto
▫ Votos dados por páginas importantes pesam mais
Page Rank
• Algoritmo usa distribuição de probabilidade
▫ Chance de uma pessoa clicar no link
aleatoriamente e chegar na página
• O peso da página A é chamado de PageRank de
A ou PR(A)
1 d
PRv 
PRu  
d
N
vBu Lv 
Page Rank
• Exemplo:
A
C
B
D
• L(B)=2 L(C)=1 L(D)=3
• d=1
• Inicialmente, PR(A) =
PR(B) = PR(C) = PR(D) =
1/4 = 0,25
• PR(A) = 0,25/2 + 0,25/1
+ 0,25/3 = 0,4583
Crawlers
• Web crawler é um programa que navega de
forma autônoma na Internet
• Também chamado de Spiders, Bots ou Robots
• São usados para guardar informações de páginas
visitadas
▫ Usadas em indexadores
▫ Manutenção
▫ Sites de tema específico
Crawlers
• Baseado em políticas:
▫ Seleção: quais as páginas para download
▫ Revisita: verificar alterações na página
▫ Educação: como visitar sem sobrecarregar outras
páginas
▫ Paralelização: coordenação de crawlers de forma
distribuída
• Existem algoritmos para cada política
Crawlers
• Naive Best-First Crawler
▫ Busca ponderada através de frequências das
palavras na página
▫ Mantém uma lista de prioridades através dos
pesos
▫ Considerado ingênuo e um dos primeiros a ser
estudado
Crawlers
• SharkSearch
▫ Semelhante ao anterior, mas com refinamento
▫ Antes de prosseguir avalia a importância da
página de acordo com os ancestrais
▫ Possui uma limite de profundidade no grafo de
busca
▫ Tentativa de evitar visitar páginas irrelevantes
Crawlers
• InfoSpiders
▫ Usa Redes Neurais para decidir qual página será
visitada
▫ A rede é alimentada pela freqüência de palavraschaves na página
▫ A saída é combinada indicando a qualidade do link
▫ Pode trabalhar em multi-thread, onde o agente é
uma thread e o crawling possui vários agentes
Browsing
• Conceito: “Processo de Exploração de Listas e
Conjuntos de Documentos”
Browsing
• Sistemas aonde a base de informação é gerada e
indexada pelo homem
▫ Difere da abordagem de crawlers
• Categorização baseada na página toda, ao invés
de palavras-chave;
• Pouca Cobertura
▫ Aproximadamente 1% de toda a web
• Exemplos:
▫ Open Directory ( http://www.dmoz.org/);
▫ Yahoo (http://www.yahoo.com/) (Híbrido).
Sistemas de Buscas
• Sistemas que pesquisam informações na
internet;
Sistemas de Buscas
• Buscas Gerais
▫ Google (http://www.google.com/);
▫ Yahoo! (http://www.yahoo.com/);
▫ Bing (http://www.bing.com/);
Sistemas de Buscas
• Buscas (domínios específicos):
▫ Scirus (http://www.scirus.com/) – Fins
acadêmicos;
▫ Froogle (http://www.froogle.com) – Compras;
▫ Tucows (http://www.tucows.com) – Software;
Metabuscadores
• Meta: “abstração”;
• Sistemas que realizam procuras sem a
necessidade de um domínio específico;
▫ Nenhuma base de dados necessária;
▫ Agrupamento de Informações numa página só;
Metabuscadores
• Maior abrangência;
• Mais rapidez;
• Maior chance de haver mais resultados com
tópicos “obscuros”;
• Bom para pesquisas quantitativas;
Metabuscadores
• Exemplos:
▫
▫
▫
▫
Mamma ( http://www.mamma.com );
Clusty (http://clusty.com/ );
DogPile (http://www.dogpile.com/);
SurfWax (http://www.surfwax.com/);
Conclusão
• Sistemas na web possuem arquitetura
centralizada e robusta;
• Formatos de obtenção das informações pela
internet (crawling, browsers e híbridos);
• Sistemas de buscas são tanto gerais como
específicos;
• Metabuscadores realizam buscas agrupando
resultados de vários sistemas diferentes;
Dúvidas?
Referências
• Brin, S., and Page, L., The Anatomy of a
Large-Scale Hypertextual Web Search
Engine. Computer Science Department,
Stanford University, Stanford, CA 94305
• G. Pant, P. Srinivasan, and F. Menczer.
Crawling the Web. InM. Levene and A.
Poulovassilis, editors, Web Dynamics. Springer,
2003.
Referências
• http://www2.dbd.pucrio.br/pergamum/tesesabertas/0313143_06_ca
p_05.pdf
• http://www.scribd.com/doc/379383/RECUPER
ACAO-DA-INFORMACAO-NA-WEB
• http://www.ct.ufrj.br/bib/bibliotecaonline/pesq
c&t/metabusca.htm
Referências
• http://www.dimap.ufrn.br/~roberta/publicacoe
s/rita_magazine.pdf
• http://wikipedia.org/