Come funziona Google (Easy Mode)

Ti sei mai chiesto come faccia Google a decidere l’ordine dei risultati di una ricerca? Ogni giorno su Google vengono eseguite milioni di ricerche e i risultati appaiono sempre in poche frazioni di secondo. Prima che tu riesca a vedere i risultati ordinati nella pagina di ricerca, nei server e data center di Google avvengono moltissime attività in lassi di tempo infinitesimali. Il processo con cui Google scansiona ed indicizza tutte le risorse presenti sul web è molto complesso e cercherò di spiegarlo nel modo più semplice possibile.

Crawling e indexing

Il primo passo per un motore di ricerca è fare crawling (scaricare) ed indicizzare tutti i documenti presenti nel web. Questo lavoro è svolto da Googlebot, lo spider di Google, che si connette ai web server sparsi nel pianeta per scaricare i documenti/pagine web.

I compiti del crawler sono gestiti dallo scheduler. Erroneamente si pensa che il crawler salti da un link all’altro navigando per le pagine web, in realtà il crawler interroga i web server per farsi dare specifiche pagine che gli vengono indicate dallo scheduler. Questi documenti vengono letti per estrapolarne i link che a loro volta vengono inviati allo scheduler che pianificherà le visite successive del crawler… e così via il ciclo si ripete. Lo scheduler quindi pianifica quali documenti il crawler deve scaricare. Ogni singolo documento scaricato viene identificato con un ID univoco ed è visualizzabile richiedendo a Google la versione cache (cache:www.esempio.com/pagina.html).

Il crawler produce tantissimi documenti, questi dati tuttavia non possono essere ancora ricercati. Senza un indice, se tu vuoi fare una ricerca per il termine “mondiali motociclismo”, i data center di Google dovrebbero leggersi tutti i documenti ogni volta che viene eseguita una ricerca e questo non è un processo efficace.

Indicizzazione e Indice invertito

Il prossimo passo quindi è creare un indice, per fare questo Google inserisce i dati di crawling in un indice invertito. Invece di dover leggere tutti i documenti per ogni query eseguita, questi vengono inseriti in un database formato da un Dizionario e i dati di posting. Ad ogni parola vengono associati gli ID dei documenti che la contengono e l’elenco degli ID è detto posting.

Le tecniche di indicizzazione studiate per le basi di dati relazionali non sono adatte per i sistemi di Information Retrieval. L’indice più utilizzato è l’indice invertito:

• Viene memorizzato l’elenco dei termini contenuti nei documenti
  della collezione;
• Per ogni termine, viene mantenuta una lista dei documenti nei quali tale termine compare.

Ad esempio la parola “motociclismo” potrebbe essere presente nei documenti 1, 5 e 9, mentre la parola “mondiali” potrebbe essere nei documenti 2, 5, e 11. L’indicizzazione avviene attraverso passi successivi

1. Scansione dei documenti e creazione di un elenco di coppie (termine, Document ID)
2. Ordinamento dell’elenco per termine
3. I termini che compaiono più volte nello stesso documento collassano in un unico elemento, al quale viene aggiunta la frequenza del termine
4. Il risultato viene memorizzato in due file: il file del Dizionario e il file dei Posting

Una volta costruito l’indice è il momento di ordinare i risultati e valutare la loro rilevanza rispetto alla ricerca effettuata. Supponiamo che un utente cerchi su Google la frase campionato motociclismo. Al fine di presentare e ordinare i risultati, Google ha bisogno di due cose:

1. trovare il set di pagine che contiene la ricerca dell’utente
2. ordinare i risultati in base alla rilevanza

Google ha trovato un modo furbo per gestire questa enorme mole di dati: invece di salvare tutto l’indice in un unico super-computer, vengono utilizzati centinaia di computer assieme e l’indice è suddiviso in piccole porzioni ciascuno. Dato che il lavoro è suddiviso tra tanti computer, la risposta può essere trovata molto più velocemente.

Immaginiamo che l’indice di una enciclopedia sia lungo 30 pagine. Se una persona dovesse cercare da sola diverse informazioni nell’indice impiegherebbe almeno qualche secondo per ogni ricerca. Ma cosa cambierebbe se si potesse assegnare una singola pagina a 30 persone? Potrebbero cercare la loro porzione di indice molto più velocemente di una sola persona che deve leggere 30 pagine da sola.

Come fa Google a trovare le pagine che contengono la ricerca dell’utente?

Torniamo all’esempio del campionato motociclismo. La parola “motociclismo” era usata nei documenti 1, 5 e 9 mentre la parole “mondiali” era presente nei documenti 2, 5 e 11. Organizzando i documenti in questo modo diventa rapido individuare i documenti che contengono entrambe le parole “mondiali” e “motociclismo”, compaiono infatti soltanto nel documento 5. La lista di ID dei documenti che contiene una parola è chiamata posting list mentre cercare i documenti che contengono entrambe le parole si dice intersecting a posting list.

Ordinare i risultati

Ora abbiamo il set di pagine che contengono le parole ricercate dall’utente ed è ora di ordinare i risultati in termini di rilevanza e authority.

Google utilizza molti fattori di ranking (+200). Uno di questi, l’algoritmo del PageRank è probabilmente il più conosciuto. Il PageRank valuta due cose: quanti link puntano ad una certa pagina e la qualità delle pagine dei siti che linkano. In base al PageRank, 5 o 6 link di qualità da siti autorevoli possono valere molto di più di 10 link provenienti da siti meno autorevoli.

Una evoluzione del PageRank è stato il Reasonable Surfer PageRank (2010). Questo algoritmo assegna pesi diversi ai link presenti in pagina in base alla posizione o zona della pagina dove i link vengono inseriti. Sintetizzando il concetto si evince che un link nel footer ottiene un peso inferiore rispetto ad un link inserito nel primo paragrafo del body text.

L’immagine mostra un esempio di distribuzione del PageRank in base alla posizione del link on-page.

Nel brevetto che descrive questo modello ci spiega che il valore di un link può essere diverso in base a un gran numero di fattori, per esempio dove è posizionato il link nella pagina, se il collegamento è di un altro colore o stile del carattere rispetto agli altri link, quante parole sono usate nel testo di ancoraggio per il link, se il testo del collegamento utilizzato è commerciale o meno, la correlazione tra il tema della pagina che linka e quello della pagina di destinazione, se il link è un’immagine o un testo e molti altri.

Non solo PageRank

Tuttavia Google utilizza tanti altri fattori oltre al PageRank. Ad esempio, se un documento contiene le parole “mondiali” e “motociclismo” affiancate, quel documento potrebbe essere più rilevante di un documento che contiene i due termini posizionati distanti. Inoltre, se una pagina include le due parole “mondiali motociclismo” nel title tag per i motori di ricerca questo è un segnale forte di rilevanza, più forte rispetto ad una pagina che nel titolo non include quei due termini. Nello stesso modo, se i termini “mondiali motociclismo” appaiono diverse volte all’interno della pagina, quel contenuto probabilmente è più rilevante rispetto ad un documento dove le parole compaiono solo una volta e se comparissero più volte della media allora potrebbe essere identificato come spam.

Come regola Google cerca di restituire pagine che hanno una buona reputazione e sono rilevanti. Se due pagine hanno la stessa quantità di informazioni che corrispondono alla ricerca dell’utente, Google mostrerà la pagina più linkata da altri siti autorevoli. In altri casi invece una pagina con pochi link o un basso PageRank può essere scelta come migliore se risulta più rilevante e specifica. Ad esempio, una pagina web totalmente dedicata ai mondiali di motociclismo è spesso più utile di un articolo che menziona solamente i mondiali di motociclismo, anche se l’articolo è pubblicato su siti molto autorevoli.

Una volta compilata la lista di documenti e dopo aver assegnato un punteggio a ciascuno di essi, Google posiziona i risultati in base al punteggio partendo dal più alto.

Come avete visto far funzionare un motore di ricerca non è affatto semplice e richiede tantissima potenza di calcolo. Per ogni ricerca che un utente esegue vengono attivati task in circa 500 computer, il tutto in meno di mezzo secondo!

Vuoi approfondire le tue conoscenze sul funzionamento dei motori di ricerca? Ti consiglio di studiare i Patent di Google, gli articoli di Bill Slawski e di Enrico Altavilla. Aggiungo inoltre InsideSearch e ThinkWithGoogle.