Como o Google funciona | Ram Rajagopal | Digestivo Cultural

busca | avançada
38130 visitas/dia
1,3 milhão/mês
Mais Recentes
>>> Banda GELPI, vencedora do concurso EDP LIVE BANDS BRASIL, lança seu primeiro álbum com a Sony
>>> Celso Sabadin e Francisco Ucha lançam livro sobre a vida de Moracy do Val amanhã na Livraria da Vila
>>> No Dia dos Pais, boa comida, lugar bacana e MPB requintada são as opções para acertar no presente
>>> Livro destaca a utilização da robótica nas salas de aula
>>> São Paulo recebe o lançamento do livro Bluebell
* clique para encaminhar
Mais Recentes
>>> Rinoceronte, poemas em prosa de Ronald Polito
>>> A forca de cascavel — Angústia (FUVEST 2020)
>>> O reinado estético: Luís XV e Madame de Pompadour
>>> 7 de Setembro
>>> Outros cantos, de Maria Valéria Rezende
>>> Notas confessionais de um angustiado (VII)
>>> Eu não entendo nada de alta gastronomia - Parte 1
>>> Treliças bem trançadas
>>> Meu Telefunken
>>> Dor e Glória, de Pedro Almodóvar
Colunistas
Últimos Posts
>>> Diogo Salles no podcast Guide
>>> Uma História do Mercado Livre
>>> Washington Olivetto no Day1
>>> Robinson Shiba do China in Box
>>> Karnal, Cortella e Pondé
>>> Canal Livre com FHC
>>> A história de cada livro
>>> Guia Crowdfunding de Livros
>>> Crise da Democracia
>>> Banco Inter É uma BOLHA???
Últimos Posts
>>> Uma crônica de Cinema
>>> Visitação ao desenho de Jair Glass
>>> Desiguais
>>> Quanto às perdas I
>>> A caminho, caminhemos nós
>>> MEMÓRIA
>>> Inesquecíveis cinco dias de Julho
>>> Primavera
>>> Quando a Juventude Te Ferra Economicamente
>>> Bens de consumo
Blogueiros
Mais Recentes
>>> O Brasil não é a Seleção Brasileira
>>> Para tudo existe uma palavra
>>> O reinado estético: Luís XV e Madame de Pompadour
>>> O Presidente Negro, de Monteiro Lobato
>>> Roçando a poesia de Alberto Beuttenmüller
>>> A Euforia Perpétua, de Pascal Bruckner
>>> A Euforia Perpétua, de Pascal Bruckner
>>> As ligações perigosas
>>> Apresentação
>>> Micro-Twitter-Blogging
Mais Recentes
>>> As Chaves do Reino, Vol. 2 - O Horrível Terça-Feira de Garth Nix pela Fundamento (2009)
>>> As Chaves do Reino, Vol. 01 - Sr. Segunda-Feira de Garth Nix pela Fundamento (2008)
>>> Hipnose - Descubra o poder da sua mente de Pyong Lee pela Outro Planeta (2018)
>>> A Chave para Rondo de Emily Rodda pela Fundamento (2010)
>>> As Crônicas das Irmãs Bruxas, Vol. 01 - Enfeitiçadas de Jessica Spotswood pela Arqueiro (2014)
>>> Trilogia Fronteiras do Universo, Vol. 01 - A Bússola de Ouro de Philip Pullman pela Objetiva (1995)
>>> Trilogia Fronteiras do Universo, Vol. 02 - A Faca Sutil de Philip Pullman pela Objetiva (1997)
>>> Assassins Creed, Vol. 05 - Renegado de Oliver Bowden pela Galera Record (2012)
>>> Os Heróis do Olimpo, Vol. 05 - O Sangue do Olimpo de Rick Riordan pela Intrínseca (2014)
>>> Sonho Febril de George R. R. Martin pela Leya (2019)
>>> Juízo Final: Odisseia dos Deuses de Horst Schadeck pela Chiado (2018)
>>> The Mystery of the Missing Antimatter de Helen R. Quinn pela Princeton University Press (2007)
>>> São José da Terra Firme de Gilberto Gerlach e Osni Machado pela Cultura Turismo São José (2004)
>>> Geometry - the Easy Way de Lawrence S. Leff pela Barrons (1997)
>>> A Solução Anabólica para Fisiculturistas de Dr. Mauro Di Pasquale pela Phorte (2006)
>>> Fallen, Vol. 3.5 - Apaixonados, Histórias de amor de Fallen de Lauren Kate pela Galera Record (2012)
>>> The Black Atlantic de Paul Gilroy pela Verso (1993)
>>> Fallen, Vol 03 - Paixão de Lauren Kate pela Galera Record (2016)
>>> Nos Céus de Paris - O romance da Vida de Santos Dumont de Alcy Cheuiche pela LPM Pocket (2001)
>>> Perda de uma Chance e Responsabilidade Civil dos Profissionais de Lisiane Lazzari Pietroski pela Conceito (2013)
>>> Acampamento Shadow Falls, Vol. 1 - Nascida à Meia-Noite de C.C. Hunter pela Jangada (2011)
>>> Comentários à Lei 11. 419/06 e as Práticas Processuais por Meio de Alexandre Atheniense pela Juruá (2010)
>>> Fallen, Vol. 04 - Êxtase de Lauren Kate pela Galera Record (2012)
>>> Administrando para Obter Resultados de Peter Drucker pela Thomson Pioneira (1998)
>>> Fallen, Vol. 01 de Lauren Kate pela Galera Record (2010)
>>> Clínica e Política: Subjetividade e Violão dos Direitos Humanos de Cristina Rauter / Eduardo Passos pela : Ifb Te Corá (2002)
>>> Príncipe Cativo, Vol. 01 - O Escravo de C.S. Pacat pela Vergara e Riba (2019)
>>> Peinture Sur Porcelaine, Techniques Pour Tous de Colette Lamarque Texte et Creations pela Fleurus (1984)
>>> Brida de Paulo Coelho pela Sextante (2013)
>>> Escribir para Television - Cómo Elaborar Guiones Y.... de Madeline Dimaggio pela Paidos (1992)
>>> Adivinhe Quem Sou de Megan Maxwell pela Essência (2014)
>>> Introdução Crítica ao Ato Infracional de Alexandre Moraes da Rosa pela Lumenjuris (2007)
>>> Ensaio Sobre a Natureza do Comercio Em Geral - 1755 - 3 Vol. de Richard Cantillon pela Segesta (2002)
>>> Fallen, Vol 02 - Tormenta de Lauren Kate pela Galera Record (2011)
>>> Beginning Albegra - Fifth Edition de John Tobey pela Prentice Hall (2002)
>>> O Orfanato da Srta. Peregrine Para Crianças Peculiares de Ransom Riggs pela Leya (2015)
>>> Log Horizon - Volume 1 de Mamare Touno pela NewPop (2016)
>>> Quel Avenir Pour les Ruraux de Paul Houee pela Ouvrières (1974)
>>> Jurisdição do Real x Controle Penal Direito & Psicanálise de Alexandre Morais da Rosa pela Digital (2011)
>>> Os Diários do Semideus (Os Heróis do Olimpo) de Rick Riordan pela Intrínseca (2013)
>>> Os Arquivos do Semideus (Percy Jackson & os Olimpianos) de Rick Riordan pela Intrínseca (2010)
>>> Estatuto da Criança e do Adolescente Comentado de Josiane Rose/lusiano Rosato/paulo pela Conceito (2011)
>>> Quando os mortos pedem justiça de Elói Gonçalves de Azevedo pela Lunardelli (2001)
>>> Preacher - Nº. 18 a 23 e do 25 ao 42 - 25 Volumes de Garth Ennis & Steve Dillon pela Vertigo/dc. Comics (2003)
>>> De Problemate Realitatis de Julius Girardi pela Augustae Taurinorum (1957)
>>> Percy Jackson e os Olimpianos, Vol. 05 - O Último Olimpiano de Rick Riordan pela Intrínseca (2010)
>>> El Despertar del Buda Interior de Lama Surya Das pela Luz de Oriente (1997)
>>> El Vizconde de Bragelonne - Tomo II de Alejandro Dumas pela Editorial Porruá S. A. (1992)
>>> Percy Jackson e os Olimpianos, Vol. 04 - A Batalha do Labirinto de Rick Riordan pela Intrínseca (2010)
>>> Percy Jackson e os Olimpianos, Vol. 03 - A Maldição do Titã de Rick Riordan pela Intrínseca (2009)
COLUNAS >>> Especial Google

Terça-feira, 14/3/2006
Como o Google funciona
Ram Rajagopal

+ de 22800 Acessos
+ 1 Comentário(s)

Muitos amigos meus, leigos em ciência da computação, me pediram uma explicação sucinta e sem jargões de como o Google funciona. Qual a receita mágica que determina as páginas que o Google deve responder quando você faz a sua busca? Em primeiro lugar, vale esclarecer que o Google não é dono de nenhum grande mistério tecnológico. Mas, certamente, desenvolveram uma tecnologia interessante, e que vamos entender um pouco melhor a seguir.

O Google é basicamente um banco de dados inteligente. Se você já usou o fichário da biblioteca do seu colégio, então sabe já como um banco de dados funciona. Os dados são agrupados em tabelas (as gavetas do fichário), e ordenados de acordo com palavras-chave, como autor ou título. A vantagem do banco de dados sobre o fichário é que o ordenamento pode ser por um número imensamente maior de características. Já imaginou se sua biblioteca tivesse que ter trinta tipos de fichários, um para ordernar por autor, outra por título de livros, outra por ano de publicação, outra por editora, e assim por diante.

Pois bem, o que o Google faz é acumular cada página da Web num banco de dados. O endereço da página, o nome, e as palavras mais frequentes e suas respectivas frequências são todas incluídas na ficha daquela página (cada página é como um livro a ser catalogado). O mais importante, todas as outras páginas para as quais a página linca também são guardadas. Quando você digita a sua busca na caixinha do Google, o software traz todas as fichas cujo conteúdo casam com sua busca.

Para fazer isto de forma eficiente, um dicionário global é criado (o famoso dicionário reverso ou índice reverso), onde cada palavra que existe na Web aparece uma vez. E na ficha de cada palavra são colocados códigos que se relacionam com as páginas que contém aquela palavra. Uma maneira de entender isso é que cada palavra tem uma lista com os endereços das páginas que a contêm. Quando você digita uma palavra e clica em buscar, tudo que precisa ser feito é imprimir na tela as listas de endereços de todas as palavras que você pediu.

Mas então onde está o segredo do Google? Até aí não há nada demais. Na verdade o que foi citado já é feito há anos por bancos de dados não estruturados. O segredo do Google, e na verdade de qualquer buscador, está em duas coisas: como ele faz para encontrar todas páginas da Grande Rede e como ele decide a ordem em que vai listar os resultados. Os nomes técnicos para estas duas atividades são crawling e scoring. Um bom buscador é bastante abrangente, e ao mesmo tempo lista as respostas na ordem que o maior número de pessoas espera. E responde à busca rápido.

Por exemplo, se você procurar por "Ronaldo" no Google Brasil, você espera que os primeiros linques que apareçam sejam sobre o Ronaldinho Gaúcho ou sobre Ronaldo Fenômeno. Não que a primeira página seja a de Ronaldo, seu vizinho, e a resposta de posição 1,233,233 seja a primeira com Ronaldo, o jogador de futebol. Ao mesmo tempo, se você coloca "World Champion 2002", quer que algo relacionado ao assunto apareça e provavelmente ficará decepcionado se não aparecer. E além disso tudo, sua paciência não aguenta esperar duas horas para uma busca ser respondida.

Todo buscador, do Google ao MSN Search, passando pelo Yahoo, pelo Ask Jeeves e até o Cadê, procura atender a esses três requisitos. Mas como falei do Google, vamos entender melhor como ele funciona. O crawling do Google, assim como o da maioria dos buscadores é feito através de programas de computador que vão seguindo todos os linques de uma página, e acumulando as informações das páginas visitadas, a partir de uma página inicial. Uma boa página inicial é a de um índice como o Yahoo (www.yahoo.com) . A coisa toda é feita de forma organizada, de maneira que ao final do processo, um componente desconectado da Web inteira foi explorada. Outra página inicial deve ser fornecida para explorar outros componentes desconectados. Por exemplo, é pouco usual um índice em inglês levar a descobrir páginas em alfabetos não ocidentais. Portanto o crawler, programa que faz o engatinhamento, tem que ser reinciado com uma página em japônes.

Para cada página visitada, o Google cria uma ficha de biblioteca. As palavras da página que estão no dicionário global tem suas frequências contadas, o endereço da página é anotado na ficha, e o endereço de todas as páginas para as quais a página linca são anotados. Finalmente, o próprio dicionário global é emendado caso alguma palavra nova seja encontrada.

Ao fim do processo de crawling - que há uns dez anos atrás demorava cerca de uma semana para visitar a Web inteira, e hoje demora bem mais que um mês - o Google tem um gigantesco banco de dados com informações concisas da página. Uma enxugada no dicionário global é feita, para remover palavras frequentes demais, como por exemplo preposições, e para remover palavras infreqüentes demais, como um erro de tipografia exdrúxulo. Por isso, se seu nome for muito incomum (muito mesmo), você não será indexado pelo Google. Se seu nome for muito incomum, mas você cometer um ato que te põe nas capas de vários jornais, a frequência do seu nome aumenta, e o Google vai te indexar.

O próximo passo é então como o scoring do Google é feito. Uma maneira natural de ordenar as páginas, quando uma busca é feita, é simplesmente pela frequência com que a palavra buscada aparece na página. Por exemplo, se você busca por "mágica", uma página que contenha a palavra mil vezes, é provavelmente mais importante do que uma que contem a palavra somente dez vezes. Infelizmente, um esquema simplista como este pode ser facilmente burlado, com indivíduos criando páginas que tenham milhões de vezes a palavra "mágica", mesmo sem ser relacionado ao assunto ou para vender um livro específico de mágica.

Cada buscador tem então a sua receita mágica para contrabalançar este tipo de problema. O Google usa uma idéia de pontos por autoridade (relevance scoring). Talvez tenha sido a grande sacada da dupla Brin & Page ao projetar seu buscador. A pontuação do Google soma aos pontos tradicionais (como frequência da palavra, importância da palavra num contexto dado por alguma fórmula simples pré-programada, etc.), uma pontuação dada por reputação.

Como medir reputação? A idéia é simples: se páginas com muita reputação apontam para você, então você tem muita reputação. É uma propriedade hereditária. Matematicamente isto é feito usando teoria dos grafos, a mesma que você usa para colorir mapas-múndi com o mínimo de cores possíveis. Mas como medir a reputação de uma página na Web, se você não sabe a reputação de ninguém a priori?

Um jeito simples, solução de engenheiro, é montar um usuário aleatório (um random browser ou monkey browser). A maneira como este usuário funciona é a seguinte: ele começa de uma página inicial e escolhe aleatoriamente um linque a ser clicado. Ele segue para a página clicada e repete o processo. O processo é feito indefinidamente. Após muito longo tempo (provavelmente após centenas de bilhões de cliques) você pode calcular a reputação de cada página com uma fórmula simples: conte o número de vezes que a página foi visitada pelo monkey browser. Para normalizar a pontuação, o melhor é calcular a fração do total de páginas visitadas que cada página aparece. Só para deixar a coisa mais simples, suponha que a Web tem só 3 páginas, A, B e C. Suponha que o monkey browser viajou por cem páginas usando o método aleatório e visitou A trinta vezes. Então a reputação de A é simplesmente 30/100 (ou seja, 0.3 de 1.0).

Uma interpretação bacana do seu score de relevância normalizado desta forma é que ele é simplesmente a chance de um monkey browser ir parar na sua página. Se a probabilidade é alta, então sua página é importante. Tudo isto já era conhecido em teoria dos grafos, e o que os dois jovens de Stanford fizeram com a ajuda de seus professores foi incorporar isto a busca na Web.

Para concluir, um último detalhe: se o Google realmente precisasse lançar macacos aleatórios para calcular a pontuação, provavelmente iriam levar anos para se concluir o cálculo, afinal precisariam fazer bilhões de visitas para se ter um número confiável (a Web tem bilhões de páginas). Felizmente, existe uma maneira eficiente de calcular estas probabilidades sem fazer visita alguma. Você só precisa saber a estrutura de linques do conjunto de páginas (que página liga com quem). O algoritmo é bastante antigo, tem mais de 100 anos. E uma das suas aplicações anteriores foi resolver problemas como calcular as frequências de vibração na corda do seu violão ou a chance de se ganhar em pôquer.

O que destacou o Google das outras máquinas de busca existentes foi a idéia de fazer um crawling mais completo que todo mundo, numa época em que ninguém se dispunha a fazer isso, e a receita da reputação entrando como parte da pontuação da página. Portanto agora você já sabe os principais segredos do Google, e pode seguir para descobrir truques para aparecer no topo da lista.


Ram Rajagopal
Berkeley, 14/3/2006


Quem leu este, também leu esse(s):
01. Fake news, passado e futuro de Luís Fernando Amâncio
02. A fotografia é um produto ou um serviço? de Fabio Gomes
03. O que te move? de Fabio Gomes
04. Lançamento de Viktor Frankl de Celso A. Uequed Pitol
05. Bitcoin, smart contracts, blockchain, cryptoassets de Julio Daio Borges


Mais Ram Rajagopal
Mais Acessadas de Ram Rajagopal em 2006
01. Sobre responsabilidade pessoal - 1/5/2006
02. Como o Google funciona - 14/3/2006
03. Como começar uma carreira em qualquer coisa - 24/4/2006
04. Música é coração, computadores, não? - 28/2/2006
05. Reflexão para eleitores - 4/9/2006


Mais Especial Google
* esta seção é livre, não refletindo necessariamente a opinião do site

ENVIAR POR E-MAIL
E-mail:
Observações:
COMENTÁRIO(S) DOS LEITORES
16/3/2006
09h04min
Adorei seu texto, me lembrei de uma tarde inteira que você pacientemente passou me explicando como a Google funciona. Não é porque é meu irmão não, mas o texto está uma maravilha!!! Saudades, Beijos, Lakshmi
[Leia outros Comentários de Lakshmi ]
COMENTE ESTE TEXTO
Nome:
E-mail:
Blog/Twitter:
* o Digestivo Cultural se reserva o direito de ignorar Comentários que se utilizem de linguagem chula, difamatória ou ilegal;

** mensagens com tamanho superior a 1000 toques, sem identificação ou postadas por e-mails inválidos serão igualmente descartadas;

*** tampouco serão admitidos os 10 tipos de Comentador de Forum.




Digestivo Cultural
Histórico
Quem faz

Conteúdo
Quer publicar no site?
Quer sugerir uma pauta?

Comercial
Quer anunciar no site?
Quer vender pelo site?

Newsletter | Disparo
* Twitter e Facebook
LIVROS




1001 DÚVIDAS DE PORTUGUÊS
JOSÉ DE NICOLA E ERNANI TERRA
SARAIVA
(1997)
R$ 10,00



MESTRES DA PINTURA - EUGÈNE DELACROIX (1798-1863)
VICTOR CIVITA (EDITOR)
ABRIL
(1978)
R$ 8,00



FABULAS DE LA FONTAINE TOMO
LA FONTAINE/IRACEMA COSTA
VERBO INFANTIL
R$ 10,00



CARDIOPATIAS AVALIAÇÃO E INTERVENÇÃO EM ENFERMAGEM
COORDENAÇÃO NÉBIA M. A. DE FIGUEIREDO E OUTROS
YENDIS
(2009)
R$ 20,00



HARVARD BUSINESS REVIEW ON MANAGING THE VALUE CHAIN
A HARVARD BUSINESS REVIEW
A HARVARD BUSINESS REVIEW
(2000)
R$ 50,00



CULTURAL AWARENESS
BARRY TOMALIN, SUSAN STEMPLESKI
OXFORD UNIVERSITY PRESS
(2003)
R$ 30,00



O CORPO FALA
PIERRE WEIL E ROLAND TOMPAKOW
VOZES
(2009)
R$ 35,00



INNOVATING FOR HEALTH: THE STORY OF BAXTER INTERNATIONAL
THOMAS G. CODY
BAXTER
(1994)
R$ 40,00



NOVAS TÉCNICAS DE REFRIGERAÇÃO COMERCIAL EM HOTELARIA, VOLUME 1
VICTOR MONTEIRO
LIDEL
(2001)
R$ 19,26



KALTPROFILE 4
GUNYHER BROER
STAHL EISEN
(1993)
R$ 50,00





busca | avançada
38130 visitas/dia
1,3 milhão/mês