Un Web Crawler in Java – I parte
Giugno 24, 2016E’ da tempo che vorrei sviluppare un Web Crawler e con questo progetto, insieme agli altri ventimila, finalmente riuscirò nell’impresa. Subito, una delle prime domande:
“A cosa serve un Web Crawler?”. Leggendo l’articolo potrete capire come funziona un Web Crawler e a cosa serve. Vi ricordo che in Github potrete trovare un esempio di Crawler in linguaggio Python. A breve riuscirò a pubblicare anche la versione in Java.
Un Web Crawler o spider o robot “attraversa” la rete Web, analizza il codice HTML e lo copia trovando titoli, links, keywords e altro ancora. Normalmente, i motori di ricerca ne fanno uso per capire cosa c’è e come cambia il WWW (World Wide Web).
Per dovere di cronaca, è da sapere che il primo Web Crawler (Matthew Gray’s Wanderer) risale al lontano 1993 all’epoca di Mosaic un Browser scritto dalla NCSA (Nation Center Supercomputing Applications). Da allora i Web Crawlers si sono moltiplicati e adattati alla struttura della rete e i più famosi sono l’originale Google Crawler (sviluppato a Stanford) e l’Internet Archive Crawler.
Ma come funzionano i Web Crawlers?
L’immagine seguente spiega a grandi linee il funzionamento di un Web Crawler. Innanzi tutto, un Web Crawler scansiona il web con diverse modalità e copia in un database le pagine visitate (STORAGE DATABASE). A questo punto, le pagine vengono successivamente elaborate dal motore di ricerca e proposte secondo alcuni algoritmi di ordinamento sul Web, in sostanza ciò che fa Google attualmente.
Figura 1.
(Ecco come funziona un Web Crawler!)
Perchè in linguaggio Java?
Con questo linguaggio sono stati progettati numerosi Web Crawler. I più famosi, non in ordine di importanza, sono: Heretrix, WebSPHINX, Web-Harvest, e JSpider. Java è stato una scelta obbligata, sia per i motivi sopra elencati, sia per la maturità del linguaggio e sia per una certa mia esperienza in numerosi progetti.
Esistono differenti tipi di Web Crawlers?
Si, a seconda della modalità con cui vengono scaricate le pagine di un sito Web. L’elenco seguente indica le diverse modalità per ognuna delle quali farò un esempio più avanti e nelle prossime puntate.
Ecco l’elenco dei diversi tipi di Web Crawlers:
- Breadth First Crawlers
- Depth First Crawlers
- Path Ascending Crawlers
- Random Walk
- Focused Crawling
- Incremental Crawling
Iniziamo dal primo tipo di Web Crawler e cerchiamo di spiegarlo brevemente così da non annoiare nessuno con un escursus troppo tecnico.
Breadth First Crawlers ossia ricerca in ampiezza.
Per la teoria dei grafi partendo da un vertice detto nodo (che nella ricerca del Web Crawler corrisponde alla pagina principale o main page) o sorgente si esplorano i nodi successivi (pagine ricavate dai link trovati) nei livelli inferiori.
In sostanza il Web Crawler analizza la main page e trova dei links (nuove pagine) che vengono inseriti in fondo ad una coda. Il link nella “coda” viene nuovamente analizzato e così di seguito i nuovi links trovati vengono ancora accodati in fondo. Questo si ripete finché nella coda non vi sono più links. La seguente immagine vi aiuterà a comprendere l’algoritmo di ricerca.
Figura 2.
(Ricerca in ampiezza)
Come vedete nella main page (pallino azzurro) sono stati trovati dei links; Questi vengono memorizzati in fondo ad una coda e le pagine (pallini gialli) a cui rimandano, saranno rilette dal Web Crawler per la ricerca di nuovi links. Il tutto si ripete finché non vi sono più link presenti nella coda. Così le pagine dei livelli superiori (a distanza minore) vengono scoperte prima delle pagine dei livelli inferiori (a distanza superiore).
Depth First Crawlers ossia ricerca in profondità.
Questa modalità di scansione dei links è diversa dalla precedente in quanto segue i “rami” dell’albero (teoria dei grafi). Cosa significa?
Ancor prima di “visitare” i nodi vicini alla sorgente (main page) l’algoritmo può andare in profondità e raggiungere i nodi più lontani. I nuovi links trovati invece di essere inseriti in fondo alla coda vengono inseriti in cima alla coda e sono i primi ad essere visitati. Così di pagina in pagina il percorso può corrispondere ad un ramo dell’albero e quindi esplorare e visitare pagine a distanze diverse. Una volta che non si trovano più links (a cui corrispondono nuove pagine) l’algoritmo torna indietro fino a trovare dei links che non sono stati ancora esplorati così da percorrere altri rami del grafo.
Figura 3.
(Ricerca in profondità)
Il tutto inizia dalla prima pagina o sorgente, il primo link trovato nel nodo (1) viene posto in cima alla coda e quindi visitato e si accede al nodo (2). Il primo link a questa distanza dal nodo sorgente viene posto in cima alla coda e quindi visitato e si accede al nodo (3). In questo nodo non vengono trovati nuovi link e quindi si torna al nodo (2) e si visita il nodo (4) e così di seguito.
