Comment fonctionne Google?

Michael Eisermann

Description

COMMENT FONCTIONNE GOOGLE?MICHAEL EISERMANN´ ´RESUME. Le point fort du moteur de recherche Google est qu’il trie intelligemment ses resultats´ parordre d’importance. Nous expliquons ici l’algorithme PageRank qui est a` la base de ce classement. Ilfaut d’abord etablir´ un modele` qui permet de definir´ ce que l’on entend par« importance». Une fois cemodele` formalise,´ il s’agit de resoudre´ astucieusement un immense systeme` d’equations´ lineaires.´Il va sans dire que l’application pratique est devenue tres` importante. Bien qu’el´ ementaires,´ les´ ´arguments mathematiques sous-jacents n’en sont pas moins interessants : l’approche fait naturellementintervenir l’algebre` lineaire,´ la« marche aleatoire´ » sur un graphe et le theor´ eme` du point fixe. Tout cecien fait un tres` beau sujet pour la culture des mathematiques´ et leurs applications.`TABLE DES MATIERESIntroduction 11. Que fait un moteur de recherche ? 22. Comment mesurer l’importance d’une page web ? 33. Marche aleatoire´ sur la toile 64. Existence et unicite´ d’une solution 85. Implementation´ efficace 116. Quelques points de refle´ xion 12Ref´ erences´ 15INTRODUCTIONCet article discute les mathematiques´ utilisees´ par Google, un moteur derecherche gen´ eraliste´ qui a eu un succes` fulgurant depuis sa creation´ en1998. Le point fort de Google est qu’il trie par ordre d’importance lesresultats´ d’une requete,ˆ c’est-a-dire` les pages web associees´ aux mots-cles´ cherches.´ L’etonnante´ ...

Sujets

• ordinateur
• réseau
• réseaux

Informations

• Publié par: Urne
• Nombre de lectures: 65
• Langue: Français

Extrait

COMMENT FONCTIONNE GOOGLE? MICHAEL EISERMANN

R ´ SUM ´ E . Le point fort du moteur de recherche Google est qu’il trie intelligemment ses re´sultats par E ordre d’importance. Nous expliquons ici l’algorithme PageRank qui est a` la base de ce classement. Il fautd’aborde ´ tablirunmode ` lequipermetded ´ efinircequel’onentendpar « importance » . Une fois ce mode`leformalis´e,ils’agitdere´soudreastucieusementunimmensesyst`emed’e´quationsline´aires. Il va sans dire que l’application pratique est devenue tre`s importante. Bien qu’e´le´mentaires, les arguments mathe´matiques sous-jacents n’en sont pas moins inte´ressants : l’approche fait naturellement intervenirl’alg`ebrelin´eaire,la « marcheal´eatoire » surungrapheetlethe´or`emedupointfixe.Toutceci en fait un tre`s beau sujet pour la culture des mathe´matiques et leurs applications.

T E DES ` S ABL MATI ERE Introduction 1. Que fait un moteur de recherche ? 2. Comment mesurer l’importance d’une page web ? 3. Marche  ale´atoire sur la toile 4. Existence et unicite´ d’une solution 5. Imple´mentation  efficace 6. Quelques points de re´flexion R´efe´rences

1 2 3 6 8 11 12 15

I NTRODUCTION Cetarticlediscutelesmathe´matiquesutilis´eesparGoogle,unmoteurde recherchege ´ n ´ eralistequiaeuunsucce ` sfulgurantdepiss ´ eationen u a cr 1998. Le point fort de Google est qu’il trie par ordre d’importance les r ´ esultatsd’unereque ˆ te,c’est-a ` -direlespageswebassoci ´ eesauxmots- cl´escherche´s.L’e´tonnanteefficacit´edecettem´ethodeafaitlesucce`sdeGoogleetlafortunedeses fondateurs,SergeyBrinetLawrencePage.L’ide ´ eestneelorsdeleurth ` esededoctorat,puispublie ´ e ´ dansleurarticle[1].Ils’agitessentiellementder´esoudreungrandsyste`med’e´quationsline´aireset fortheureusementl’algorithmeit ´ eratifquiend ´ ecouleestaussisimplequepuissant.Ons’inte ´ resseici depluspr`es`acetalgorithme,a`lafoissimpleeting´enieux.Enconjonctionavecunehabilestrat´egie d’entreprise, on pourrait dire que Google gagne des milliards de dollars avec l’algebre line´aire ! ` AjoutonsqueGoogleaeulachancedenaı ˆ tredansunesituationfavorable,quandla « nouvelle ´economie » ´etaitencoreenpleinecroissance:levolumed’internetexplosaitetlesmoteursdere- cherchedepremie ` rege ´ ne ´ rationavaientdumala ` s’adapterauxexigencesgrandissantes.Sivousvou- lezsavoirplussurlafoudroyantehistoiredel’entrepriseGoogle,sesl ´ egendesetanecdotes,vouslirez avec profit le livre de David Vise et Mark Malseed [2]. Date : 16 mai 2006. Derni ` eremise ` ajour : 13 mai 2009. URL : www-fourier.ujf-grenoble.fr/ ~ eiserm Universit ´ eJosephFourier • Licence de Mathe´matiques • cours « Math ´ ematiquesassiste ´ esparordinateur » . 1

2 MICHAEL EISERMANN 1. Q UE FAIT UN MOTEUR DE RECHERCHE ? 1.1. Fouille de donne´es. ` Apremie`revue,leprinciped’unmoteur de recherche est simple : on copie d’abord les pages web concerne´es ´ ire l le, puis on trie le contenu (les mots-cle´s) par ordre en memo oca alphab ´ etiqueafind’effectuerdesrechercheslexiques.Une requˆete est ladonn´eed’unouplusieursmots-cl´es;la re´ponse est une liste des pagescontenantlesmots-cle ´ srecherch ´ es.C’estengroscequefaisaientlesmoteursderecherche, ditsdepremie`rege´ne´ration,danslesanne´es1990.Apre`sr´eflexion,cettede´marchesimplisten’est passie ´ videntecarlaquantite ´ desdocumentsa ` g ´ ererest ´ enormeetrienquelestockageetlagestion efficacesposentdesde´fisconside´rables.Etcelad’autantplusquelesrequˆetesdoiventˆetretraite´esen tempsr ´ eel:onneveutpaslare ´ ponsedansunesemaine,mais tout de suite . Uneimple´mentationop´erationnelle`acette´echelledoitdoncemployerlaforcebruted’unre´seau puissant,afinder ´ epartirlesdonn ´ eesetlest ˆ achessurplusieursordinateurstravaillantenparall ` ele. Plusimportantencoresontlesalgorithmes,hautementsp´ecialis´esetoptimise´s,sanslesqlˆe ue s mem unre ´ seaudequelquesmilliersd’ordinateursresteraitimpuissantdevantcettet ˆ achehercul ´ eenne.Pour se faire une idee de l’ordre de grandeur, voici quelques chiffres sur l’entreprise Google : ´ Cerveaux: environ6000employ ´ es(d ´ ebut2006) Ordinateurs: plusde60000PCenr´eseausousLinux(onignoreleschiffresexacts) Me´moire vive: plus de 130 000 Go de RAM pour les calculs (on ignore les chiffres exacts) Disques dures: plusde5000000Gopourstockerlesdonn ´ ees(onignoreleschiffresexacts) Trafic en ligne: quelquesmilliersderequ ˆ etesparsecondes(onignoreleschiffresexacts) ´ Part du marche´: plus de 50% aux Etats-Unis et dans de nombreux autres pays Chiffre d’affaires: plusde$6000000000en2005,dont$1465400000b´´efisnet en ce Cotationboursi`ere: environ$80000000000enao ˆ ut2005 Pr ´ ecisonsquelarecherchesurGoogleestunservicegratuit.En1998iln’ ´ etaitpasdutout ´ evident commentgagnerdel’argentavecunproduitgratuit,aussiappr ´ eci ´ equ’ilsoit.Jusqu’en2000l’entre- priseaccumulaitdespertesetfutme ˆ memenace ´ edefaillite.L’ide ´ equil’asauv ´ eea ´ ete ´ laventede liens commerciaux etdepuis2001cesplacementspublicitairesg´en`erentdeplusenplusdebe´ne´fices. 1.2. Classementdesr ´ esultats. L’e ´ normequantit ´ edesdonne ´ esentra ˆ ıneundeuxi ` emeprobl ` eme,plus de´licat encore : les pages trouvees sont souvent trop nombreuses, il faut donc en choisir les plus perti- ´ nentes.Lagrandeinnovationapport ´ eeparGoogleen1998estletridespagesparordred’importance. Ce qui est frappant est que cet ordre correspond assez pre´cise´ment aux attentes des utilisateurs. Parexemple,sivousvousint´eressez`alaprogrammationetvousfaiteschercherlesmots-cle´s « C++ compiler » , vous trouverez quelques millions de pages. Des pages importantes comme gcc.gnu.org se trouvent quelque part en teˆte du classement, ce qui est tre`s raisonnable. Par contre, une petite page personnelle,o ` ul’auteurmentionnequ’ilneconnaı ˆ trienduC++etn’arrivepasa ` compiler,nefigurera queverslafindelaliste,cequiest´egalementraisonnable.CommentGoogledistingue-t-illesdeux? Selon les informations fournies par l’entreprise elle-meˆme, l’index de Google porte sur plus de 8 milliards de documents web. Une bonne partie des informations re´pertorie´es, pages web et documents changent f ´quemment. Il est donc hors de question de les classer manuellement, par des annexes, re eˆtreshumains:ceseraittropcoˆuteux,troplentetjamaisa`jour.L’importanced’unepagedoitdonc e ˆ trede ´ termin ´ eedemanie ` reautomatise ´ e,parunalgorithme.Commentest-cepossible?