Un crawler (anche detto spider, boot o web robot) è un programma che naviga il web al fine di ricercare pagine nuove (o aggiornate) a scopo di indicizzazione o più in generale per estrarre informazioni di diverso tipo. La particolarità di tali software è che sono in grado di allargare autonomamente il proprio raggio di azione seguendo i link presenti nelle pagine visitate. Per tale motivo i tempi di esecuzione divengono rapidamente esponenziali al punto che i crawler dei motori di ricerca commerciali (google, yahoo, etc.) sono praticamente sempre attivi (continuous crawling) ed in esecuzione su server diversi.

L’algoritmo

L’algoritmo di crawling in pseudocodice è in realtà molto semplice ma prima di introdurlo diamo alcune definizioni:

La frontiera F è un insieme da cui vengono prelevati (e quindi rimossi) i link da seguire ed in cui vengono inseriti i nuovi link trovati;
I semi sono gli indirizzi (URL) di partenza del processo di crawling;
Un set L di link visitati identifica tutti i documenti già analizzati.

L’algoritmo avrà quindi la seguente struttura:

si recupera un link dalla frontiera;
1. Il link viene eliminato da F ed inserito in L;
si scarica il codice HTML della pagina al fine di;
1. analizza la pagina secondo gli scopi del crawler;
2. estrarre tutti i link della pagina;
ogni link estratto che non è presente né in L né il F viene aggiunto alla frontiera.
si ritorna al punto 1 se la frontiera contiene ancora link, altrimenti il processo termina.

Si noti che al punto 3 è possibile aggiungere ulteriori condizioni per l’inserimento dei link nella frontiera, ad esempio per limitare il crawling all’interno di uno specifico dominio. In questo caso più propriamente di parla di web scraping.

L’Implementazione

Esistono diversi tool e framework che implementano un crawler. Ma prima di parlarne presentiamo un esempio di codice java che ci sarà comunque utile per comprendere il comportamento di un crawler e la sua complessità.

Innanzitutto abbiamo bisogno di due insiemi che implementano rispettivamente la frontiera ed i link visitati e dei metodi per popolarli:

/* Frontiera e link visitati */
private Set<String> frontier = new HashSet<String>();
private Set<String> visited  = new HashSet<String>();

/**
 * Aggiunge un URL alla frontiera solamente se non gia' inserito o visitato
 * @param url Url da aggiungere
 */
public void addFrontier( String url ) {
    if ( url != null && !url.isEmpty() 
            && !frontier.contains( url ) && !visited.contains( url ) ) {
        frontier.add( url );
    }
}
	
/**
 * Aggiunge una lista di utl alla frontiera
 * @param urls Lista di url da aggiungere
 */
public void addFrontiers( List<String> urls ) {
    for ( String url : urls ) {
        addFrontier( url );
    }
}

/* Frontiera e link visitati */

private Set<String> frontier = new HashSet<String>();

private Set<String> visited = new HashSet<String>();

/**

* Aggiunge un URL alla frontiera solamente se non gia' inserito o visitato

* @param url Url da aggiungere

public void addFrontier( String url ) {

if ( url != null && !url.isEmpty()

&& !frontier.contains( url ) && !visited.contains( url ) ) {

frontier.add( url );

}

/**

* Aggiunge una lista di utl alla frontiera

* @param urls Lista di url da aggiungere

public void addFrontiers( List<String> urls ) {

for ( String url : urls ) {

addFrontier( url );

}

Quindi abbiamo bisogno di un metodo che scarica il file HTML referenziato da un URL dato:

/**
 * Recupera la pagina html dao l'url
 * @param url Url della pagina
 * @return La pagina html recuperata
 */
public String read(String url) {		
    try {
        /* Inserisce il protocollo se mancante */
        if ( !url.startsWith( "http://" ) ) {
            url = "http://" + url;
        }

        /* Apre lo streaming verso l'url */
        URL website = new URL( url );
        BufferedReader in = new BufferedReader( new InputStreamReader( website.openStream() ) );

        /* Legge lo stream una riga alla volta 
         * e la inserisce nel buffer 
         */
        StringBuffer buffer = new StringBuffer();
        String inputLine = null;
        while ( ( inputLine = in.readLine() ) != null ) {
            buffer.append( inputLine );
        }
        in.close();
        return buffer.toString();

    } catch (Exception e) {
        System.err.println( e.getLocalizedMessage() );
    } 
    return null;
}

/**

* Recupera la pagina html dao l'url

* @param url Url della pagina

* @return La pagina html recuperata

public String read(String url) {

try {

/* Inserisce il protocollo se mancante */

if ( !url.startsWith( "http://" ) ) {

url = "http://" + url;

}

/* Apre lo streaming verso l'url */

URL website = new URL( url );

BufferedReader in = new BufferedReader( new InputStreamReader( website.openStream() ) );

/* Legge lo stream una riga alla volta

* e la inserisce nel buffer

StringBuffer buffer = new StringBuffer();

String inputLine = null;

while ( ( inputLine = in.readLine() ) != null ) {

buffer.append( inputLine );

}

in.close();

return buffer.toString();

} catch (Exception e) {

System.err.println( e.getLocalizedMessage() );

}

return null;

}

In ultima analisi abbiamo la necessità di un metodo che estragga gli URL dalle pagine HTML. Questo è sicuramente un compito molto complesso e di non semplice implementazione. Nella soluzione proposta ci siamo affidati ad una regular expression trovata in internet ma sicuramente nei crawler “industriali” sono adottate tecniche più avanzate che tengono conto anche di aspetti legati alla posizione del link nel testo etc.

/* Regular expression per recupero dei link */
private Pattern pattern = Pattern.compile(
    "\\b(((ht|f)tp(s?)\\:\\/\\/|~\\/|\\/)|www.)" + 
    "(\\w+:\\w+@)?(([-\\w]+\\.)+(com|org|net|gov" + 
    "|mil|biz|info|mobi|name|aero|jobs|museum" + 
    "|travel|[a-z]{2}))(:[\\d]{1,5})?" + 
    "(((\\/([-\\w~!$+|.,=]|%[a-f\\d]{2})+)+|\\/)+|\\?|#)?" + 
    "((\\?([-\\w~!$+|.,*:]|%[a-f\\d{2}])+=?" + 
    "([-\\w~!$+|.,*:=]|%[a-f\\d]{2})*)" + 
    "(&(?:[-\\w~!$+|.,*:]|%[a-f\\d{2}])+=?" + 
    "([-\\w~!$+|.,*:=]|%[a-f\\d]{2})*)*)*" + 
    "(#([-\\w~!$+|.,*:=]|%[a-f\\d]{2})*)?\\b");

/**
 * Utilizza la regular expression per estrarre gli url dalla pagina html
 * @param input La pagina html
 * @return Lista di url estratti
 */
public List<String> extractUrls(String input) {
    List<String> result = new ArrayList<String>();
    Matcher matcher = pattern.matcher(input);
    while (matcher.find()) {
        result.add(matcher.group());
    }
    return result;
}

/* Regular expression per recupero dei link */

private Pattern pattern = Pattern.compile(

"\\b(((ht|f)tp(s?)\\:\\/\\/|~\\/|\\/)|www.)" +

"(\\w+:\\w+@)?(([-\\w]+\\.)+(com|org|net|gov" +

"|travel|[a-z]{2}))(:[\\d]{1,5})?" +

"(((\\/([-\\w~!$+|.,=]|%[a-f\\d]{2})+)+|\\/)+|\\?|#)?" +

"((\\?([-\\w~!$+|.,*:]|%[a-f\\d{2}])+=?" +

"([-\\w~!$+|.,*:=]|%[a-f\\d]{2})*)" +

"(&(?:[-\\w~!$+|.,*:]|%[a-f\\d{2}])+=?" +

"([-\\w~!$+|.,*:=]|%[a-f\\d]{2})*)*)*" +

"(#([-\\w~!$+|.,*:=]|%[a-f\\d]{2})*)?\\b");

/**

* Utilizza la regular expression per estrarre gli url dalla pagina html

* @param input La pagina html

* @return Lista di url estratti

public List<String> extractUrls(String input) {

List<String> result = new ArrayList<String>();

Matcher matcher = pattern.matcher(input);

while (matcher.find()) {

result.add(matcher.group());

}

return result;

}

Quindi lo pseudocodice descritto sopra si traduce nel seguente codice java, in cui abbiamo inserito come ulteriore condizione di terminazione la visita di 100 link al fine di evitare un loop infinito:

/**
 * Avvia il processo di crawling
 * @throws IOException
 */
public void start() throws IOException {
    while ( !frontier.isEmpty() && visited.size() < 100 ) {		
        /* Estrae il successivo link dalla frontiera */
        String url = frontier.iterator().next();
			
        /* Visita la pagina */
        System.out.println( url );
        String html = read( url );
			
        /* Estrae gli url e li aggiunge alla frontiera */
        if ( html != null ) {	
            addFrontiers( extractUrls( html ) );
        }
			
        /* Rimuove l'url dalla frontiera e lo affiunge ai visitati */
        frontier.remove( url );
        visited.add( url );
			
        System.out.println( "Visitati " + visited.size() + " frontiera " + frontier.size() );
    }
}

/**

* Avvia il processo di crawling

* @throws IOException

public void start() throws IOException {

while ( !frontier.isEmpty() && visited.size() < 100 ) {

/* Estrae il successivo link dalla frontiera */

String url = frontier.iterator().next();

/* Visita la pagina */

System.out.println( url );

String html = read( url );

/* Estrae gli url e li aggiunge alla frontiera */

if ( html != null ) {

addFrontiers( extractUrls( html ) );

}

/* Rimuove l'url dalla frontiera e lo affiunge ai visitati */

frontier.remove( url );

visited.add( url );

System.out.println( "Visitati " + visited.size() + " frontiera " + frontier.size() );

}

Avviando il processo anche solo partendo dal link di google http://www.google.it l’output finale del programma mostra 1355 link ancora da visitare presenti nella frontiera dopo 100 pagine estratte. Questo ci da quindi una idea di quanto sia virtualmente impossibile eseguire il crawling di tutto il web con programmi così semplici come quello presentato.

JSoup

Nell’esempio descritto sopra abbiamo sorvolato sul problema dell’analisi del contenuto della pagina estratta dall’url considerando i fini per cui il crawler è realizzato. Genericamente, infatti, ci siamo limitati a stampare l’url e ad estrarre i link per mezzo della regular expression.

Per fare analisi più approfondite abbiamo bisogno di un parser HTML che abbiamo individuato in JSoap. Si tratta di un framework java le cui API consentono di estrarre dati e manipolare in maniera estremamente semplice documenti HTML5 sfruttando le potenzialità di DOM, CSS e metodi di accesso simili a quelli offerti da JQuery.

Per utilizzare JSoup inseriamo innanzitutto il riferimento Maven nel nostro progetto:

<dependency>
    <groupId>org.jsoup</groupId>
    <artifactId>jsoup</artifactId>
    <version>1.10.2</version>
</dependency>

<groupId>org.jsoup</groupId>

<artifactId>jsoup</artifactId>

</dependency>

Quindi ridisegniamo il metodo start() del nostro crawler eliminando i metodo extractUtls() e read() che invece sono efficientemente implementati da JSoup:

public void start() throws IOException {
    while ( !frontier.isEmpty() && visited.size() < 100 ) {
			
        /* Estrae il successivo link dalla frontiera */
        String url = frontier.iterator().next();
			
        /* Visita la pagina */
        System.out.println( url );
        try {
            Document document = Jsoup.connect( url ).get();
				
            /* Estrae gli url e li aggiunge alla frontiera */
            Elements links = document.select("a[href]");
            for (Element link : links) {
                addFrontier( link.attr("abs:href") );
            }
        } catch ( Exception ex ) {
            System.err.println( ex.getLocalizedMessage() );
        }
			
        /* Rimuove l'url dalla frontiera e lo affiunge ai visitati */
        frontier.remove( url );
        visited.add( url );
			
        System.out.println( "Visitati " + visited.size() + " frontiera " + frontier.size() );
    }
}

public void start() throws IOException {

while ( !frontier.isEmpty() && visited.size() < 100 ) {

/* Estrae il successivo link dalla frontiera */

String url = frontier.iterator().next();

/* Visita la pagina */

System.out.println( url );

try {

Document document = Jsoup.connect( url ).get();

/* Estrae gli url e li aggiunge alla frontiera */

Elements links = document.select("a[href]");

for (Element link : links) {

addFrontier( link.attr("abs:href") );

}

} catch ( Exception ex ) {

System.err.println( ex.getLocalizedMessage() );

}

/* Rimuove l'url dalla frontiera e lo affiunge ai visitati */

frontier.remove( url );

visited.add( url );

System.out.println( "Visitati " + visited.size() + " frontiera " + frontier.size() );

}

JSoup esegue il parsing dei file HTML indipendentemente dal fatto che il documento sia ben formato o meno, gestendo quindi situazioni, tra l’altro molto comuni, di tag non chiusi o tag impliciti. Il risultato del parsing è una struttura dati costruita in memoria e detta DOM (Document Object Model), che può essere navigata in modo molto efficente con l’implementazione del CSS selector che offre il framework.

Tornando al codice del metodo start() le funzionalità utilizzate del parser sono:

estrazione e parsing del documento: Jsoup.connect( url ).get();
selezione nel documento di tutti i link presenti (il tag <a>): document.select("a[href]");
estrazione dell’attributo href da tutti i link: link.attr("abs:href");

Si noti l’utilizzo del prefisso abs: che risolve l’url, che in genere è relativo, rispetto al contesto dell’applicazione. In altri termini trasforma un link relativo del tipo /post/id=23 in http://www.myapp.com/post/id=23.

Eseguendo il nuovo metodo questa volta i link in frontiera dopo aver visitato 100 pagine sono 4636 a dimostrazione della maggiore efficacia del parser rispetto alla semplice regular expression. Relativamente all’efficienza, invece, si noterà che l’esecuzione è più lenta poiché il parsing è una operazione sicuramente più onerosa.

Crawler4J

Il crawler da noi implementato, pur assolvendo bene il proprio compito, è carente rispetto a determinati aspetti sia tecnici che implementativi. Innanzitutto un crawler dovrebbe essere sufficientemente “gentile” da seguire le direttive specificate nel file robot.txt presente nei siti web visitati. Tale file è utilizzato dai gestori del sito per definire restrizioni per i crawler in termini di frequenza di visita, modalità di visita, etc.

Dal punto di vista implementativo, invece, il nostro codice non tiene conto di diversi aspetti come, ad esempio, i tempi do crawling che, come abbiamo visto, possono essere esponenziali, oppure l’interruzione accidentale dell’esecuzione, che determinerebbe il riavvio del processo daccapo.

Introduciamo quindi una soluzione completa interamente scritta in java, molto efficiente e di semplice utilizzo: crawler4j. Disponibile su Maven Central è possibile includerlo nel progetto semplicemente inserendone la dipendenza nel pom.xml:

<dependency>
    <groupId>edu.uci.ics</groupId>
    <artifactId>crawler4j</artifactId>
    <version>4.2</version>
</dependency>

<artifactId>crawler4j</artifactId>

</dependency>

L’implementazione del crawler richiede l’estensione della classe WebCrawler che implementa l’interfaccia Runnable. Questo perché tale classe può essere eseguita su più thread al fine di parallelizzare il processo di crawling. La classe non presenta metodi astratti ma i due metodi shouldVisit() e visit() hanno implementazioni di default assolutamente inutili. Il primo metodo, infatti, è utilizzabile per filtrare i link da visitare e per default restituisce sempre TRUE. Il secondo, invece, è invocato ad ogni url visitato e per default non fa assolutamente nulla.

Implementiamo quindi il primo metodo per la selezione dei link da visitare facendo in modo da escludere tutti i link che escono dal dominio e che non rimandano a pagine HTML:

private final static Pattern FILTERS = Pattern.compile(".*(\\.(css|js|gif|jpg|png|mp3|mp3|zip|gz))$");

@Override
public boolean shouldVisit(Page referringPage, WebURL url) {
    String href = url.getURL().toLowerCase();
    return !FILTERS.matcher(href).matches() && href.startsWith("http://www.google.it");
}

private final static Pattern FILTERS = Pattern.compile(".*(\\.(css|js|gif|jpg|png|mp3|mp3|zip|gz))$");

@Override

public boolean shouldVisit(Page referringPage, WebURL url) {

String href = url.getURL().toLowerCase();

return !FILTERS.matcher(href).matches() && href.startsWith("http://www.google.it");

}

Nella realizzazione del metodo visit() volevamo mantenere la logica già mostrata negli esempi precedenti al fine di visualizzare il numero di elementi visitati e da visitare. Sfortunatamente il framework è scarsamente documentato quindi l’implementazione che presentiamo è il risultato di una ipotesi che abbiamo fatto ispezionando il codice sorgente:

public void visit(Page page) {
    System.out.println("URL: " + page.getWebURL().getURL() );
    Frontier frontier = super.getMyController().getFrontier();
    System.out.println( "Visitati " + frontier.getNumberOfProcessedPages() + " frontiera " + frontier.getQueueLength() );
}

public void visit(Page page) {

System.out.println("URL: " + page.getWebURL().getURL() );

Frontier frontier = super.getMyController().getFrontier();

System.out.println( "Visitati " + frontier.getNumberOfProcessedPages() + " frontiera " + frontier.getQueueLength() );

}

Esempi più complessi è significativi possono essere trovati direttamente sulla pagina Github del progetto.

Prima di procedere con l’implementazione del controller del nostro crawler realizzato con Crawler4J, accenniamo brevemente alla sua architettura funzionale, mostrata nella seguente immagine (sorgente).

Molto semplicemente il controller gestisce N crawler che ricevono gli URL da visitare da una frontiera comune. Il recupero delle pagine è delegato ad un page fetcher (che a discapito dell’immagine è comune ai crawler) mentre l’analisi è demandata al metodo visit() al quel è inviata la pagina web dopo averla parsata. Un ulteriore componente gestisce infine i file robots.txt incontranti durante il crawling.

/*
 * Configurazione della cartella del db
 */
CrawlConfig config = new CrawlConfig();
config.setCrawlStorageFolder("/Users/massimo/Workspace/javaboss1/crawler");

/*
 * Inizializzazione del controller per il crawling.
 */
PageFetcher pageFetcher = new PageFetcher(config);
RobotstxtConfig robotstxtConfig = new RobotstxtConfig();
RobotstxtServer robotstxtServer = new RobotstxtServer(robotstxtConfig, pageFetcher);
CrawlController controller = new CrawlController(config, pageFetcher, robotstxtServer);

/*
 * I seed url sono le prime pagine visitate. Ogni altra pagina
 * e' ottenuta seguento i link nelle pagine visitate.
 */
controller.addSeed("http://www.google.it");

/*
 * Avvia 5 crawler in modo bloccante, ovvero il mein termina solamente
 * quando il processo di crawling termina.
 */
controller.start(SimpleCrawler4j.class, 5);

* Configurazione della cartella del db

CrawlConfig config = new CrawlConfig();

config.setCrawlStorageFolder("/Users/massimo/Workspace/javaboss1/crawler");

* Inizializzazione del controller per il crawling.

PageFetcher pageFetcher = new PageFetcher(config);

RobotstxtConfig robotstxtConfig = new RobotstxtConfig();

RobotstxtServer robotstxtServer = new RobotstxtServer(robotstxtConfig, pageFetcher);

CrawlController controller = new CrawlController(config, pageFetcher, robotstxtServer);

* I seed url sono le prime pagine visitate. Ogni altra pagina

* e' ottenuta seguento i link nelle pagine visitate.

controller.addSeed("http://www.google.it");

* Avvia 5 crawler in modo bloccante, ovvero il mein termina solamente

* quando il processo di crawling termina.

controller.start(SimpleCrawler4j.class, 5);

Per altre opzioni di configurazione, tipo user-agent, proxy, politiche di fairness etc., vi rimandiamo alla pagina ufficiale su Github.

Codice Sorgente

Il codice sorgente con gli esempi presentati è disponibile qui crawler.

Java Crawler

L’algoritmo

L’Implementazione

JSoup

Crawler4J

Codice Sorgente

Related Posts: