Raccolta, ranking e query delle pagine di un webgraph Ilaria Bordino.

Raccolta, ranking e query delle pagine di un webgraph

Ilaria Bordino

Pagina 2

Programma della lezione

• Nutch: un motore di ricerca configurabile dall’utente

• Esecuzione di Pagerank sul grafoDIS;

• Esecuzione di HITS sul grafoDIS;

• Indicizzazione delle pagine html del grafo DIS in MG4J;

• Query da riga di comando usando MG4J;

Nutch

• Framework Apache per la costruzione di crawler scalabili e applicazioni per Web Search

• Software opne source costruito al top di Jakarta Lucene

• Disponibile gratuitamente presso• http://lucene.apache.org/nutch/

Ilaria BordinoMG4J -- Managing GigaBytes for Java

Jakarta Lucene

• Java API per lo sviluppo di motori di ricerca testuali• Non applicazione ma API che consente la

realizzazione di search applications customizzate in base alle specifiche esigenze degli sviluppatori.

• Grande comunità di sviluppatori• Tecnologia usata nello sviluppo di molti siti e

applicazioni web (furl, zoe, jira, lookout)• http://jakarta.apache.org/lucene


Lucene: principali caratteristiche

• Indicizzazione scalabile e performante• Algoritmi per la Search potenti, accurati ed efficienti:• Include supporto per ranked searching, fielded

searching, wildcard queries, phrase queries, proximity queries, range queries and more

• Ricerca su molteplici indici con merging dei risultati• Permette esecuzione simultanea di update e search• Cross platform solution: 100% java, disponibile come

software open source


Nutch

• Giovane progetto open source• Software per lo sviluppo di applicazioni per Web Search• Non è un sito di ricerca ma intende essere un mezzo per

potenziare molti siti di ricerca• Non è un progetto di ricerca ma intende essere un

supporto per la ricerca• Obiettivo: incrementare la disponibilità di tecnologie per

Web Search• Obiettivo: aumentare la trasparenza nella web search.


Nutch: Obiettivi tecnici

• Scalare all’intero Web: milioni di server differenti, miliardi di pagine: il completamento di un crawl richiede settimane e c’è molto rumore nei dati

• Supporto per traffico elevato (migliaia di ricerche al secondo)

• Qualità paragonabile allo stato dell’arte per la search.


Nutch: Architettura


Pagina 9

Nutch: motore di ricerca configurabile dall'utente

• Permette la raccolta delle pagine, l’indicizzazione e l’interrogazione delle pagine web.

• INPUT: un set di pagine html

• OUTPUT: motore di ricerca sulle pagine raccolte

• USO: raccolta di pagine e ricerca sulla collezione indicizzata

Pagina 10

Nutch: download

• Disponibile gratuitamente in http://www.nutch.org– Tutorial: http://www.nutch.org/tutorial.html– Presentazione generale del codice:– http://www.nutch.org/apidocs/overview-summary.html

• Ultimaversione:• http://www.nutch.org/release (il file nutch-0.7.tar.gz)

Pagina 11

Nutch: configurazione

• Java 1.4.x (http://java.sun.com/j2se/downloads.html)– Tomcat di Apache 4.x (http://jakarta.apache.org/tomcat)

– Almeno un gigabyte su disco;

– Connessione Internet veloce;

Pagina 12


• Inizializzare NUTCH_JAVA_HOME con la directory radice di Java.

– edit .bashrc per inserire “export NUTCH_JAVA_HOME=/usr/local/lib/j2sdk1.4.2_03”

– MAC OS: export NUTCH_JAVA_HOME=/Library/Java/Home

• Aggiungere nutch/bin al PATH

– edit .bashrc per inserire “export PATH=$PATH:nutch/bin ”

Nutch: Configurazione

• A partire dalla versione 0.8 è necessario configurare alcuni parametri come l’identificatore dello user-agent.

• Editare il file conf/nutch-site.xml settando alcune proprietà minimali:


<property> <name>http.agent.name</name>

<value></value> <description>HTTP 'User-Agent' request

header. MUST NOT be empty - please set this to a single word uniquely related to your organization. </description>

</property>

Nutch: Configurazione

• NOTE: You should also check other related properties:

• http.robots.agents • http.agent.description • http.agent.url • http.agent.email • http.agent.version • and set their values appropriately.



• <property> <name>http.agent.description</name> <value></value> <description>Further description of our bot- this text is used in the User-Agent header. It appears in parenthesis after the agent name. </description></property><property> <name>http.agent.url</name> <value></value> <description>A URL to advertise in the User-Agent header. This will appear in parenthesis after the agent name. Custom dictates that this should be a URL of a page explaining the purpose and behavior of this crawler. </description></property><property> <name>http.agent.email</name> <value></value> <description>An email address to advertise in the HTTP 'From' request header and User-Agent header. A good practice is to mangle this address (e.g. 'info at example dot com') to avoid spamming. </description></property>


Crawlare il Web con Nutch

• Nutch è stato progettato per la gestione di crawl su larga scala, che siano eseguiti in un sistema distribuito e che possono richiedere molto tempo (settimane) per il completamento.

• I dati raccolti sono organizzati nel modo seguente:• Crawldb: database del crawl. Contiene info su ogni url

nota a nutch, incluso se/quando è stato fatto fetching;• Linkdb: database dei link. Contiene inlink noti a tutte le url

raccolte, riportando url sorgente e anchor text;• Un insieme di segmenti; un segmento è un insieme di URL

considerate come un’unità durante il fetching.• Indici: nel formato supportato da Lucene


Crawlare il Web con Nutch

• Un segmento è una directory che contiene le seguenti sottodirectory:

• crawl_generate contiene elenco URL di cui bisogna fare il fetching

• crawl_fetch contiene lo stato di fetching di ogni URL• Content: mantiene il contenuto associato a ogni URL• parse_text contiene il testo estratto con il parsing da ogni

URL• parse_data contiene outlink e metadata estratti con il

parsing • crawl_parse contiene gli outlink, usati per aggiornare

crawldb


Nutch: due approcci al crawling

• Intranet crawling, usando il comando crawl: scelta appropriata se si vuole effettuare un crawl di dimensioni limitate, fino a 1M pagine

• Whole-Web crawling: da utilizzare per crawl molto estesi, che abbiano bisogno di una quantità notevole di tempo e di risorse computazionali.

• Maggiore controllo usando comandi a più basso livello:• inject, fetch, generate, updatedb.


Pagina 19

Raccolta delle pagine del DIS

• Creare il file dis/urls e inserire la home page

– Ex: http://www.dis.uniroma1.it

• Modificare il file nutch-0.6/conf/crawl-urlfilter.txt per personalizzare la raccolta

• Aggiungere +^http://([a-z0-9]*\.)*dis.uniroma1.it/ per limitare la raccolta alle pagine al dominio dis.uniroma1.it

• Inizializzare crawldb

Pagina 20

Raccolta delle pagine del DIS

• Lista di parametri: nutch crawl– -dir <dir-name>: directory dove saranno memorizzati i

resultati della raccolta– -depth <depth>: profondita’ dei path a partire dalla pagina

radice– delay <delay>: intervallo di tempo, in secondi, fra due

consecutive richieste su uno stesso host.– -threads <thread>: numero di threads eseguiti in parallelo

• Esecuzione del crawl:– nutch crawl urls -dir mycrawl -depth 3 >&

mycrawl.log – NON ESEGUIRE A LEZIONE

Interrogazione del DB

• Usage: CrawlDbReader <crawldb> (-stats | -dump <out_dir> | -topN <nnnn> <out_dir> [<min>] | -url <url>)

• <crawldb>directory name where crawldb is located• -stats [-sort] print overall statistics to System.out• [-sort]list status sorted by host-dump <out_dir>• [-format normal|csv ]dump the whole db to a text file in

<out_dir>[-format csv]dump in Csv format[-format normal]dump in standard format (default option)

• -url <url>print information on <url> to System.out• -topN <nnnn> <out_dir> [<min>]dump top <nnnn> urls

sorted by score to <out_dir>[<min>]skip records with scores below this value.This can significantly improve performance.


Interrogazione del DB: readlinkdb

• Usage: LinkDbReader <linkdb> {-dump <out_dir> | -url <url>)

• -dump <out_dir> dump whole link db to a text file in <out_dir>

• -url <url> print information about <url> to System.out• Dopo aver eseguito un crawl possiamo analizzare la

struttura degli hyperlink della collezione raccolta.• nutch readlinkdb mycrawl/linkdb/ -dump mylinks• Il comando crea una directory chiamata mylinks che

conterrà informazioni sugli inlink delle URL create in semplice formato testuale.


Interrogazione del DB: readlinkdb

• more mylinks/part-00000• http://www.dis.uniroma1.it/~wine09/#ja-col2Inlinks: fromUrl:

http://www.dis.uniroma1.it/~wine09/ anchor: Skip to second columnhttp://www.dis.uniroma1.it/~wine09/#ja-contentInlinks: fromUrl: http://www.dis.uniroma1.it/~wine09/ anchor: Skip to contenthttp://www.dis.uniroma1.it/~wine09/#ja-mainnavInlinks: fromUrl: http://www.dis.uniroma1.it/~wine09/ anchor: Skip to main navigationhttp://www.dis.uniroma1.it/~wine09/index.phpInlinks: fromUrl: http://www.dis.uniroma1.it/~wine09/ anchor: WINE'09, the fifth Workshop on Internet & Network Economicshttp://www.dis.uniroma1.it/~wine09/media/system/js/caption.jsInlinks: fromUrl: http://www.dis.uniroma1.it/~wine09/ anchor: http://www.dis.uniroma1.it/~wine09/media/system/js/mootools.jsInlinks: fromUrl: http://www.dis.uniroma1.it/~wine09/ anchor:

• egrep -v $'^$' mylinks/part-00000 >inlinks.txt


Estrazione degli outlink

• Il database linkdb fornisce informazioni relavimente ai soli link entranti.

• Per estrarre gli outlink dai dati raccolti dobbiamo leggere I segmenti.

• Usiamo il comando readseg• Usage: SegmentReader (-dump ... | -list ... | -get ...) [general options]* General options:-

nocontentignore content directory-nofetchignore crawl_fetch directory-nogenerateignore crawl_generate directory-noparseignore crawl_parse directory-noparsedataignore parse_data directory-noparsetextignore parse_text directory* SegmentReader -dump <segment_dir> <output> [general options] Dumps content of a <segment_dir> as a text file to <output>.<segment_dir>name of the segment directory.<output>name of the (non-existent) output directory.* SegmentReader -list (<segment_dir1> ... | -dir <segments>) [general options] List a synopsis of segments in specified directories, or all segments in a directory <segments>, and print it on System.out<segment_dir1> ...list of segment directories to process-dir <segments>directory that contains multiple segments* SegmentReader -get <segment_dir> <keyValue> [general options] Get a specified record from a segment, and print it on System.out.<segment_dir>name of the segment directory.<keyValue>value of the key (url).Note: put double-quotes around strings with spaces.


Estrazione outlink: merging dei vari segmenti

• Usiamo il comando mergeseg per fondere i vari segmenti ottenuti con il crawling

• nutch mergesegs whole-segments mycrawl/segments/*• Quindi usiamo il comando readseg per estrarre outlink

dal segmento globale ottenuto• nutch readseg -dump whole-segments/20091110143344/

dump-outlinks• cat dump-outlinks/dump | egrep 'URL|toUrl' >outlinks.txt


Lista degli outlink

• URL:: http://www.uniroma1.it/studenti/stranieri/default.phpURL:: http://www.uniroma1.it/studenti/stranieri/chinadesk.phpURL:: http://www.uniroma1.it/studenti/stranieri/URL:: http://www.uniroma1.it/studenti/sort/default.phpURL:: http://www.uniroma1.it/studenti/serviziutilita/counseling.phpURL:: http://www.uniroma1.it/studenti/segreterie/default.phpURL:: http://www.uniroma1.it/studenti/scuole/default.php outlink: toUrl: http://www.uniroma1.it/ufficiostampa/identita.php anchor: Identit? visiva outlink: toUrl: http://www.uniroma1.it/sitemap.php anchor: Sitemap outlink: toUrl: http://www.merchandising.uniroma1.it/ anchor: Merchandising outlink: toUrl: http://www.uniroma1.it/eletel/telefoni/default.php anchor: Elenco telefonico outlink: toUrl: http://www.uniroma1.it/contatti/ anchor: Contatti outlink: toUrl: http://www.uniroma1.it/about/ anchor: Chi siamo outlink: toUrl: http://www.uniroma1.it/studenti/cultura/iniziative.php anchor: Iniziative culturali proposte dagli studenti (finanziate dall?universit?) outlink: toUrl: http://w3.uniroma1.it/cta/index.asp anchor: Laboratorio teatrale outlink: toUrl: http://www.uniroma1.it/cappella/ anchor: Cappella universitaria outlink: toUrl: http://www.dssp.uniroma1.it/gong/educazionenutrizionalegastronomica.htm anchor: Servizio di educazione nutrizionale e gastronomica outlink: toUrl: http://www.uniroma1.it/studenti/serviziutilita/counseling.php anchor: Servizi di counseling psicologico outlink: toUrl: http://www.cattid.uniroma1.it/index.html anchor: Postazioni per l?utilizzo di pc e connessioni internet outlink: toUrl: http://www.campus.uniroma1.it/studenti/ anchor: Distribuzione gratuita di software


Creazione della lista dei link

• java nutchGraph.PrintInlinks inlinks.txt >links.txt• java nutchGraph.PrintOutlinks outlinks.txt >>links.txt• Rimozione di eventuali duplicati:• LANG=C sort links.txt | uniq >cleaned-links.txt• head cleaned-links.txt• http://www.dis.uniroma1.it/~wine09/http://www.dis.uniroma1.it/~wine09/#ja-col1http://

www.dis.uniroma1.it/~wine09/http://www.dis.uniroma1.it/~wine09/#ja-col2http://www.dis.uniroma1.it/~wine09/http://www.dis.uniroma1.it/~wine09/#ja-contenthttp://www.dis.uniroma1.it/~wine09/http://www.dis.uniroma1.it/~wine09/#ja-mainnavhttp://www.dis.uniroma1.it/~wine09/http://www.dis.uniroma1.it/~wine09/index.phphttp://www.dis.uniroma1.it/~wine09/http://www.dis.uniroma1.it/~wine09/media/system/js/caption.jshttp://www.dis.uniroma1.it/~wine09/http://www.dis.uniroma1.it/~wine09/media/system/js/mootools.jshttp://www.dis.uniroma1.it/~wine09/http://www.dis.uniroma1.it/~wine09/modules/mod_briaskISS/mod_briaskISS.jshttp://www.dis.uniroma1.it/~wine09/http://www.dis.uniroma1.it/~wine09/templates/ja_purity/js/ja.rightcol.jshttp://www.dis.uniroma1.it/~wine09/http://www.dis.uniroma1.it/~wine09/templates/ja_purity/js/ja.script.js


Creazione mappa delle URL

• cut -f1 links.txt >url-list.txt• cut -f2 links.txt >>url-list.txt• LANG=C sort url-list.txt | uniq >sorted-url-list.txt• java -Xmx2G it.unimi.dsi.util.FrontCodedStringList -u -r

32 umap.fcl < sorted-url-list.txt• java -Xmx2G it.unimi.dsi.mg4j.util.MinimalPerfectHash

--offline sorted-url-list.txt -c it.unimi.dsi.mg4j.util.HashCodeSignedMinimalPerfectHash -s umap.smph


Creazione del grafo

• java -Xmx2G nutchGraph.PrintEdges cleaned-links.txt umap.smph > webgraph.dat

• numNodes=$(wc -l < webgraph.dat )• java -Xmx2G nutchGraph.IncidenceList2Webgraph

$numNodes webgraph• java -Xmx2G it.unimi.dsi.webgraph.BVGraph -g

ASCIIGraph webgraph webgraph


Pagina 30

Download delle pagine html

– Procediamo all' indicizzazione delle pagine raccolte da Nutch mediante MG4J.

– Le pagine devono essere precedentemente scaricate, visto che non e’ possible ottenerle dal db di Nutch

– Scaricare le pagine:• wget -N pagine –I sorted-url-list.txt

Pagina 31

db

Linkstructure

IPS

RankPG

Nutch ParserDB

WEB

readdb

graph.txt

txt2IPSPageRank

HITSRankHITS

getfiles

files

MG4JQueryMG4JQuery

Pagina 32

Indicizzazione delle pagine html

– Costruzione della base documentale:

• find ../htmlDIS -type f | java it.unimi.dsi.mg4j.document.FileSetDocumentCollection -f it.unimi.dsi.mg4j.document.HtmlDocumentFactory htmldis.collection

– Creazione dell’indice:• java -Xmx512M it.unimi.dsi.mg4j.tool.Index --

downcase -S htmldis.collection collectionDIS

Pagina 33

MG4J: Scorer

– Tra gli scorer di MG4J :

– clarkeComarckScorer: documentazione in Class ClarkeCormarkScorer di MG4J

– DocumentRankScorer: assegna un rank pre-calcolato alle pagine. Il “default” e’ il resultato di query booleana: le pagine sono ritornate in ordine crescente di suei ID.

Pagina 34

Interrogazione da riga di comando

– java it.unimi.dsi.mg4j.query.Query –help– Uso: java Query -c collection collectionBaseName1

collectionBaseName2– java -Xmx512M it.unimi.dsi.mg4j.query.Query -c

htmldis.collection collectionDIS-text collectionDIS-title– [!help]>Dipartimento– Redirezionare la query su un file di output (outFile)– grep "Document #" outFile | more

Pagina 35

db

Linkstructure

IPS

RankPG

Nutch ParserDB

WEB

readdb

graph.txt

txt2IPSPageRank

HITSRankHITS

getfiles

files

MG4JRankMG4JQuery

Raccolta, ranking e query delle pagine di un webgraph Ilaria Bordino.

Documents

Transcript of Raccolta, ranking e query delle pagine di un webgraph Ilaria Bordino.