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.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *