Internet aut Web

Dalla sua nascita la rete Internet si è continuamente espansa fino ad assumere le enormi proporzioni attuali.

Il Web nacque inizialmente per permettere la collaborazione e lo scambio di informazioni tra i ricercatori nel settore della fisica delle alte energie.

Poi nel Maggio del 1991 il Web divenne un sistema di condivisione dell’informazione basato su HTML, http e un programma client chiamato www: il sistema permetteva di consultare i documenti scritti in HTML che erano memorizzati su un calcolatore ([1] e [2]).

Già nell’anno successivo si contavano una cinquantina di Web servers sparsi per il mondo (soprattutto mantenuti da università e centri di ricerca), nel giugno 1999 se ne contavano 720,000.

Un paio di anni dopo, nell’Aprile del 2001, i Web servers erano saliti a circa 24 milioni, a Marzo del 2007, lo studio condotto periodicamente dalla Netcraft [3] riportava 110,460,149 di Web servers attivi.

La semplicità di utilizzo del Web e la facilità con cui è possibile mettere in linea propri materiali, ha fatto sì che in pochi anni il Web crescesse a dismisura; secondo il già citato studio Netcraft [3] (Fig. 1) si può facilmente notare che ci troviamo di fronte a tassi di crescita fortemente esponenziali.

Purtroppo per l’utente è diventato sempre più difficile trovare le informazioni che gli interessano all’interno di una mole così notevole di dati. Attualmente si stima che solo il 15% degli utenti arrivano ad una certa pagina Web conoscendone direttamente l’indirizzo, nella maggioranza dei casi ci si rivolge ad un motore di ricerca, in grado di fornire un elenco di indirizzi tendenzialmente pertinenti alle parole chiavi digitate, quindi, sono sempre più indispensabili strumenti in grado di ritrovare velocemente le informazioni volute, con il massimo di efficienza ed efficacia.

Quando le dimensioni del web erano ancora piuttosto ridotte riscuotevano un buon successo quei motori di ricerca che si basavano prevalentemente sulle pagine segnalate dagli utilizzatori del servizio o dai gestori delle pagine stesse. I contenuti dei siti segnalati venivano controllati manualmente da esseri umani che, con molta pazienza, si occupavano di classificare i documenti per categorie e indicizzarli per parole chiave.

Un esempio di questo genere di servizio e tutt’ora costituito da Open Directory Project (ODP) [4] che continua ad offrire un ampio archivio di siti Web classificati per categoria, scartando l’inutile ma conservando ed ordinando solo i contenuti realmente interessanti.

I motori di ricerca moderni si basano su un modello comune che consiste nello scaricare un gran numero di pagine Web grazie a programmi appositi, a cui spesso ci si riferisce col nome di Spider, Bot o Web Crawler.

Attualmente i più importanti sono Google, Yahoo, Msn che nonostante stiano creando un oligopolio nel settore, non riescono comunque a coprire l’intero web, ma hanno la capacità di indicizzare miliardi di pagine e di rispondere alle richieste in frazioni di secondo con qualità molto alta.

Purtroppo, non conoscendo con esattezza la formula per definire la rilevanza dei risultati (ranking), non abbiamo la certezza che ci sia la completa trasparenza nel modo di operare questo ordinamento.

Con i software open-source invece, abbiamo a disposizione i codici e siamo liberi di personalizzarli e utilizzarli nel rispetto delle licenze con le quali sono distribuiti; siamo altrettanto consapevoli della maniera in cui il ranking è effettuato.

Il primo obiettivo di questa tesi è di analizzare il panorama offerto dal mondo open-source nell’ambito del progetto e la realizzazione di un motore di ricerca, per collezioni di documenti testuali, con la finalità di individuare i motori "migliori" per flessibilità e semplicità d’uso, per efficacia ed efficienza. I software che ho scelto di esaminare sono quelli che hanno più visibilità nel web, quindi i più utilizzati da siti importanti: Sphider, PhpDig, Nutch, ht://Dig.

Nel seguito della relazione saranno mostrate le caratteristiche generali e implementative di ognuno, poi con un piccolo tutorial sarà descritto il loro funzionamento e si fornirà un giudizio finale.

Per valutare i metodi di ricerca, si sono effettuati dei test su vari tipi di collezioni documentali e di interrogazioni. Nella relazione saranno spiegati e commentati i test effettuati per misurare le loro prestazioni in termini di velocità di indicizzazione, spazio occupato dall’indice, rilevanza delle risposte alle interrogazioni.

L’aspetto progettuale consisteva nella combinazione di più sistemi esistenti e nella risoluzione di tutti i problemi sistemistici e algoritmici ad essa correlati.

Un ulteriore obiettivo, è stato quello di analizzare i tre più grandi crawler ‘Googlebot, Yahoo!, Msnbot’ al fine di studiare il loro comportamento .

Crawler Module

Il Crawler (Spider) [6], si occupa di raccogliere documenti dalla rete a partire da un set S0 fornito in input. Da un punto di vista algoritmico questo task può essere modellato come la visita di un grafo orientato Gweb=( Nweb ,Eweb ) con Nweb pari all’insieme delle pagine web presenti su internet, ed Eweb corrispondente ai link tra pagine.

Un Crawler visita il grafo servendosi di due strutture dati di appoggio: “Already Seen Pages” (una struttura che tiene traccia delle pagine già raggiunte), ed una coda con priorità “Priority Que” (usata per selezionare il prossimo set di pagine da visitare). Il processo va avanti senza sosta: i dati raccolti sono mantenuti all’interno del “Page Repository”.
Le funzioni svolte da un Page Repository sono molto simili a quelle di un database system, ma data la natura particolare degli oggetti da memorizzare e il contesto al quale deve essere applicato, un repository dovrebbe soddisfare i seguenti requisiti: [7]

Scalabilità. Il Repository dovrebbe essere in grado di rispondere alla crescita del Web. Inoltre, data la necessità di mantenere aggiornata la collezione dei documenti, lo spazio occupato dalle versioni obsolete delle pagine deve essere riorganizzato e reso disponibile per le nuove versioni.

Modalità di accesso differenziate. Vi sono tre moduli che interagiscono con il Page Repository: il crawler, l’indexer e il query engine. Mentre il crawler e l’indexer (incluso anche l’analysis module) necessitano di un accesso di tipo stream, per il query engine è più efficiente un metodo di accesso random, tramite il quale una pagina può essere recuperata velocemente grazie al suo identificatore unico.

Politiche di distribuzione delle pagine. Come diretta conseguenza della scalabilità, i moderni Page Repository sono in realtà sistemi distribuiti, formati da un certo numero di nodi. Se ogni nodo ha la stessa importanza e viene pertanto considerato al pari di tutti gli altri, si dice che la politica di distribuzione delle pagine è di tipo uniforme (uniform distribution policy). Ciò significa che, data una pagina, essa potrebbe essere assegnata per la memorizzazione ad uno qualsiasi dei nodi. Al contrario, quando una pagina viene assegnata ad un nodo in base ad un criterio come, ad esempio, l’identificatore della pagina, non si tratta di una distribuzione uniforme. In questo caso, infatti, si parla di distribuzione hash.

Organizzazione del nodo. All’interno di un singolo nodo, le operazioni di inserimento ed eliminazione delle pagine sono sicuramente le più caratterizzanti, assieme ai metodi di accesso random e stream. Il metodo con il quale le pagine sono organizzate influisce sicuramente sull’efficienza delle citate operazioni. Ad esempio, in una organizzazione hash il dispositivo di memorizzazione viene suddiviso in un certo numero di buckets di dimensione limitata. Le pagine vengono assegnate ai vari buckets in base al valore di una chiave, ad esempio l’identificatore unico della pagina. Questo tipo di organizzazione è però svantaggiosa sia per quanto riguarda il metodo di accesso stream che per le operazioni di inserimento di nuove pagine. Al contrario, in una organizzazione del disco in cui le nuove pagine vengono aggiunte in coda alle altre (log-structured organization) le operazioni di inserimento sono sicuramente favorite. Per quanto riguarda l’accesso random, accanto alla coda delle pagine viene mantenuto un indice B-tree. Altri sistemi, invece, basano la propria organizzazione su un sistema ibrido, in parte hash ed in parte log: il supporto di memorizzazione viene suddiviso logicamente in extents di dimensione maggiore rispetto ai buckets hash; le pagine vengono assegnate ai vari extents tramite una funzione di hash; la gestione di ogni extent è realizzata in modalità log.

Strategie di update. Se il Page Repository deve interagire con un crawler di tipo batch, allora riceverà nuovi dati per un periodo limitato di tempo. Al contrario, se il crawler è di tipo steady il Repository dovrà essere in grado di ricevere dati in modo pressoché continuo. Le politiche di update [8] della collezione di documenti non possono essere implementate senza considerare le modalità di funzionamento dei crawler. Si parla di in-place update se le pagine ottenute dal crawler sono inserite direttamente, rimpiazzando eventualmente le vecchie versioni con quelle nuove. Con la tecnica di shadowing, invece, le nuove versioni sono memorizzate separatamente rispetto alle vecchie e solo in uno step successivo l’intera collezione verrà completamente aggiornata. Generalmente, i Page Repository che adottano una strategia di shadowing update distinguono i nodi in read nodes e in update nodes. I read nodes sono utilizzati per l’accesso random e stream, mentre l’inserimento viene effettuato negli update nodes. In questo modo si realizza una perfetta separazione fra le operazioni di accesso e quelle di inserimento, con lo svantaggio, però, di diminuire il grado di freshness dell’intera collezione.

A partire dalle pagine raccolte, nuove pagine sono visitate semplicemente seguendo i link estratti da quelle già conosciute.
Vi sono molte politiche che si possono adottare per la visita del grafo che, una volta scelte, sono implementate dai “Crawler Managers”, mentre i “Down loaders” fornisco i meccanismi per scaricare le pagine prescelte.
Tutte le pagine collezionate dal crawler sono periodicamente analizzate dal modulo “Page Analysis” per estrarre informazioni significative; potrebbero, per esempio, essere memorizzate in un campo particolare le parole estrapolate dai META tag, dai tag <title> o <h1> per dare più peso ad alcune parole rispetto che altre all’interno di un documento.

In sostanza, il lavoro del Crawler si può riassumere in tre fasi:

Link Extractor: il Web viene esplorato alla ricerca di link i quali una volta trovati vengono immessi in una coda con una priorità dipendente dalle politiche scelte dal search engine.

Crawler Management: viene estratto un gruppo di link dalla coda e si controlla che le pagine non siano state già visitate e se lo sono, se la versione estratta al momento è più recente (quindi la pagina è da aggiornare) e se la pagina accetta l’indicizzazione

Download: le pagine vengono scaricate e memorizzate in archivi dedicati.
In conclusione dell’analisi del modulo crawler, non possiamo far a meno di parlare del file robots.txt, il quale è un meccanismo usato dal server per proibire di effettuare l’indicizzazione di un Url. Infatti in tale file sono specificate le parti del sito che il webmaster designa come accedibili e non accedibili; prima che il crawler richieda una pagina, deve verificare se non è proibita dal suddetto file.

1 Freshness: parametro che influisce sulla qualità del servizio offerto dal motore di ricerca. Infatti, una volta recuperate le pagine durante una sessione di crawling, queste devono essere mantenute il più possibile aggiornate.

Ranking System

Le query poste ad una search interface contengono generalmente un numero variabile di keywords e il motore di ricerca risponde estraendo dalle proprie strutture dati un elenco di documenti che sembrano essere di maggiore rilevanza (ranking). Il problema sta nel capire quali siano i documenti più importanti da visualizzare per primi come risposta alla query. Esistono due tipi di approcci: uno consiste nel considerare solo il contenuto dei documenti, l’altro analizza la struttura dei link.

Per il primo metodo una tecnica utilizzata è quella del TDFIDF [12], indicando con q la parola relativa alla query e con d il documento:  TDFIDF(q,d) = (q,d)*IDF(q).

TDF(q,d) = la frequenza del termine q in d.

IDF(q)= l’inverso della frequenza della parola q in tutta la collezione.

In  tal maniera una parola è rilevante quanto più essa è presente nel documento e tanto meno è presente nella collezione. Inoltre è possibile incrementare questo valore di un fattore costante, per esempio se la parola è contenuta nei META tag o nel titolo.

Mentre questo metodo è utile per un dataset controllato, è meno indicato per Internet, dove ognuno può pubblicare pagine a piacimento; infatti, il TDFIDF presenta il problema dello spamming: vale a dire che un webmaster potrebbe riempire le proprie pagine con parole ripetute migliaia di volte, anche non inerenti al contesto del sito, per far aumentare il punteggio assegnato ad esse.

Per ovviare a questi inconvenienti, anziché dare un punteggio alle query in relazione al documento, altre tecniche preferiscono dare, accedendo alle URL visitate, uno score alla pagina in funzione dei link entranti e uscenti; i metodi più diffusi sono il PageRank (Google)[13] e HITS (Teoma)[14]. L’idea generale sta nel considerare importante una pagina se è puntata da molte altre a loro volta considerate importanti.

L’architettura generale di un motore di ricerca di cui abbiamo appena parlato è descritta in Fig. 5

Infine, un breve cenno alla qualità di un motore di ricerca: per misurare l’efficienza e la scalabilità, in genere, si fa riferimento alla velocità con cui è indicizzato un certo dataset e allo spazio occupato dall’indice; si può classificare ulteriormente, in base alla velocità con cui i motori rispondono alle query. Tutte queste caratteristiche sono misurabili oggettivamente, ma per stimare la qualità dei risultati forniti, sono necessari i concetti di Precision e Recall (Fig. 6).[15]

Precision: % di documenti ritrovati che sono rilevanti.

Recall: % di documenti rilevanti che sono stati ritrovati.

Ovviamente, un motore di ricerca fornisce risultati migliori tanto più sono alti tali valori (Fig. 7). Per classificare i documenti rilevanti, non ci sono meccanismi automatizzati, ma è un’operazione basata sul lavoro di esperti.  

Alla luce di queste informazioni generali passiamo all’analisi dei crawler da me scelti: Sphider, Nutch, PhpDig, ht://Dig.

Indexer Module

I dati contenuti nel page repository vengono analizzati da un modulo Indexer. L’indexer costruisce tradizionalmente due strutture: il text index (o content index ) e il link index. Entrambi gli indici sono fondamentali per fornire un adeguato supporto al query engine. Dal punto di vista delle strutture dati, il text index viene generalmente realizzato come un inverted index.

Un inverted index è un insieme di inverted list, che come si può vedere dalla Fig. 3, è composta da un dizionario, un vettore ordinato alfabeticamente con le parole trovate nel Repository, ognuna delle quali punta alla Posting list (o location entry), cioè la lista dei documenti in cui è presente. Spesso, nel dizionario, ma anche nelle entry della Posting list, può essere memorizzata la frequenza con cui la parola appare rispettivamente nella collezione e nel documento: tale informazione sarà poi utile per le query. Al modulo query è assegnato il compito di rispondere alle richieste pervenute dall’utente interrogando l’indice; in generale i motori di ricerca possono eseguire query booleane (AND, OR, NOT), per proximity, per frase e wildcard.
Per le prime versioni viene in aiuto la struttura della lista invertita: le query in AND (ma lo stesso vale anche per quelle in Or e NOT) vengono risolte scandendo le posting list delle parole cercate e selezionando solo i documenti presenti in entrambe (Fig. 4).

Per quanto riguarda le query per frase e per proximity, è necessario memorizzare nella lista invertita la posizione della parola all’interno del documento, in maniera da poter controllare se i termini appaiono consecutivamente o a distanza predefinita nella stessa pagina. Le query wildcard sono risolte implementando il dizionario in strutture dati particolari, che permettono un accesso veloce a tutti i termini derivati dall’applicazione della wildcard.
Un altro indice costruito dal modulo Indexer è il Link Index, che rappresenta sinteticamente la topologia del Web Graph. Anche questo indice è particolarmente importante perchè alcuni algoritmi di ranking, tra cui Page-Rank [9] e HITS [10], determinano la rilevanza dei documenti in relazione ad una query, anche sulla base di un’analisi di connettività. Accanto al link index, alcuni motori prevedono la costruzione di utility index da parte del collection analysis module. In letteratura, però, sono stati descritti pochi esempi di utility index, perchè queste strutture sono parte integrante dei moduli di ranking, i quali sono oggetto di segreti commerciali. Un possibile impiego di un utility index è quello descritto in [11], dove un motore di ricerca offre un servizio di ricerca limitato all’interno di un dominio. In questo caso l’utility index contiene la mappa di ogni sito da cui sono state prelevate pagine per la collezione, in modo che, escludendo i domini non di interesse, la ricerca sia effettuata in un tempo inferiore.