Sistema di ranking per siti web
Da Tesine Linguaggi e Traduttori.
Contents |
Obiettivo del progetto
Il progetto è nato in seno al LABinf (http://www.labinf.polito.it), un laboratorio informatico che offre ai suoi utenti la possibilità di ospitare siti web personali.
Lo scopo del progetto era riconoscere quali tra i siti ospitati offrissero materiale potenzialmente didattico, assegnando a ciascun sito un punteggio in base a determinati valori. In questo modo, lo staff sarebbe in grado di incentivare i siti più socialmente utili con bonus o altre agevolazioni, come l'aumento dello spazio disponibile.
Specifiche del progetto
Il sistema deve privilegiare i siti ad alto contenuto di materiale scaricabile e corretti dal punto di vista formale, oltre che non troppo obsoleti. Non è fondamentale l'aspetto grafico o l'uso di tecnologie web dinamiche, anche se vengono assegnati bonus addizionali.
A ciascun sito viene associato un punteggio finale che è dato dalla somma del punteggio della pagina principale e dei punteggi di tutte le pagine che linka, eventualmente corretti con particolari pesi. Un parametro permette di specificare la profondità dei link da seguire.
A partire da questi presupposti, ecco i criteri utilizzati dal sistema per l'assegnazione del punteggio:
| Condizione | Punteggio |
|---|---|
| La pagina fa uso di CSS | +10 |
| La pagina fa uso di JavaScript | +5 |
| La pagina fa uso di PHP | +5 |
| Presenza di sorgenti C, C++ | +5 |
| Presenza di sorgenti Java | +5 |
| Presenza di archivi ZIP/RAR/TAR/GZ/... | +5 |
| Presenza di documenti PDF | +4 |
| Presenza di documenti di testo generici (TXT, XML) | +4 |
| Presenza di documenti Office/OpenOffice | +3 |
| Presenza di eseguibili o script | +2 |
| Presenza di immagini JPEG/PNG | +2 |
| Presenza di immagini GIF | +1 |
| Errori di bilanciamento tag | -2 |
Questi sono invece i pesi, ovvero i fattori per i quali viene moltiplicato il punteggio delle sotto-pagine o delle pagine linkate:
| Tipo di pagina | Peso |
|---|---|
| Pagina principale | 1.0 |
| Link interno/sotto-pagina | 0.75 |
| Link esterno di primo livello | 0.5 |
| Link esterno di secondo livello | 0.25 |
| Link esterno di terzo livello o superiore | 0.1 |
Composizione del progetto
Il progetto è composto dai seguenti file:
- scanner.jflex - il codice dello scanner scritto per JFlex
- parser.cup - la grammatica e la semantica per il parsing scritto per Java CUP
- Main.java - classe Java che inizializza lo scanner e il parser
- Downloader.java - classe Java che gestisce il download delle pagine da analizzare
- Pagina.java - classe Java che mantiene le informazioni relative ad una singola pagina (URL)
- PaginaId.java - classe Java che contiene la coppia URL / FileReader associato
- SeriePagine.java - classe Java che fa da contenitore per le classi Pagina
- ParserInternalException.java - classe Java che gestisce eventuali eccezioni nel parsing
- compila - semplice script Shell per compilare il progetto
Funzionamento
Per compilare il progetto, è sufficiente lanciare lo script compila nella cartella in cui sono contenuti tutti i file sopra elencati.
Successivamente, si lancia il seguente comando:
java Main <URL> [profondità]
dove:
- URL indica la URL (remota o locale) da analizzare
- profondità è un paramentro opzionale ed indica l'annidamento massimo da utilizzare durante il parsing (se non specificato, non c'è limite di annidamento)
NOTA: è consigliabile non superare mai il limite di profondità 2, in modo da ottenere risultati più veloci e coerenti.
--
Per esempio, per analizzare il sito personale di un fantomatico utente pippo del LABinf, si procederebbe in questo modo:
java Main http://www.labinf.polito.it/~pippo/ 2
A scopo di test, abbiamo proceduto ad analizzare preventivamente tutti i siti personali degli utenti attualmente ospitati sul server del LABinf. I risultati si possono ammirare nella Test sul campo.
Scanner
Lo scanner è in grado di riconoscere quasi tutti i tag dello standard HTML 4.01, scartando automaticamente quelli sconosciuti. Per ciascun tag, invia al parser i simboli "nome_tagopen "e "nome_tagclose", in modo da controllarne poi il corretto utilizzo sintattico. In realtà, tale funzionamento non sarebbe necessario (sarebbe sufficiente un solo generico simbolo TAGopen/TAGclose), ma abbiamo deciso di implementarlo ugualmente in caso di eventuali sviluppi ulteriori.
Inoltre, è in grado di verificare la presenza di codice PHP o riferimenti a fogli di stile CSS all'interno della pagina in esame.
--
Lo scanner definisce i seguenti stati:
%xstate tag_aperto %xstate tag_chiuso %xstate tag_dentro %xstate tag_jscript %xstate tag_link %xstate tag_img %xstate tag_css %xstate tag_content
tag_aperto: dopo aver identificato l'apertura di un tag (ovvero il simbolo "<"), lo scanner entra in questo stato per identificare il nome del tag associato; quindi, passa a:
- se è un tag <a> --> stato tag_link
- se è un tag <img> --> stato tag_img
- se è un tag <script> --> stato tag_jscript
- se è un tag <link> --> stato tag_css
- tutti gli altri tag --> stato tag_link
tag_dentro: quando si trova in questo stato, lo scanner ignora ogni carattere fino ad incontrare la chiusura del tag (ovvero il simbolo ">"); quindi, passa allo stato iniziale.
tag_chiuso: dopo aver identificato la chiusura di un tag (ovvero il simbolo "</"), lo scanner entra in questo stato per identificare il nome del tag associato; quindi, passa allo stato iniziale.
tag_link: dopo aver identificato un tag riferimento (ovvero il tag "<a>"), lo scanner entra in questo stato per identificare l'URL definito nel campo href="; a tal fine, non appena incontra tale sequenza passa allo stato tag_content.
tag_img: dopo aver identificato un tag immagine (ovvero il tag "<img>"), lo scanner entra in questo stato per identificare l'URL definito nel campo src="; a tal fine, non appena incontra tale sequenza passa allo stato tag_content.
tag_content: questo stato è necessario per ritornare come simbolo ID il contenuto di link o immagini; una volta incontrato il simbolo ", passa allo stato tag_dentro.
tag_css: questo stato è necessario per verificare l'eventuale presenza di riferimenti a fogli di stile CSS (ovvero un generico campo "text/css"); quindi, passa allo stato iniziale.
tag_jscript: in questo stato, lo scanner ignora qualsiasi carattere fino ad incontrare il tag di chiusura JavaScript (ovvero il simbolo "</script>"); quindi, passa allo stato iniziale.
--
Quando lo scanner non si trova in nessuno degli stati precedenti (ovvero non si trova all'interno di tag, codice JavaScript o codice PHP), ignora qualsiasi cosa.
Parser
Si è cercato di mantenere la grammatica il più semplice possibile, in modo tale da garantire un funzionamento base corretto ed eventuali espansioni future (per esempio, la realizzazione di un mini-validatore HTML). Siamo partiti dallo scheletro base di una classica pagina web:
<html> ... <head> ... </head> ... <body> ... </body> ... </html>
esprimendolo in questo modo:
start with html; html ::= taglist HTMLopen taglist HEADopen taglist HEADclose BODYopen taglist BODYclose taglist HTMLclose | taglist HTMLopen taglist BODYopen taglist BODYclose taglist HTMLclose ; taglist ::= taglist tag | taglist ID | ;
La lista di tag è stata quindi definita nel modo seguente:
taglist ::= taglist tag | taglist ID
|
;
tag ::= ABBRopen taglist ABBRclose
| ACRONYMopen taglist ACRONYMclose
...
| ULopen taglist ULclose
| VARopen taglist VARclose
| ABBRopen error {: parser.report_error("bilanciamento tag abbr errato!", null); :}
| ACRONYMopen error {: parser.report_error("bilanciamento tag acronym errato!", null); :}
...
| ULopen error {: parser.report_error("bilanciamento tag ul errato!", null); :}
| VARopen error {: parser.report_error("bilanciamento tag var errato!", null); :}
Siamo così riusciti a realizzare un controllo minimo sul bilanciamento dei tag: in parole povere, se un tag è stato aperto deve anche essere stato chiuso - pena errore (e penalizzazione conseguente). In realtà, tale limite sintattico è molto evidente e prono ad errori... lo standard HTML infatti è molto vario, per non parlare della fantasia dei programmatori!
Per gestire il punteggio, il parser contiene al suo interno un riferimento alla classe Java della pagina presa in esame. All'interno di tale classe, è memorizzato il punteggio associato alla pagina. In presenza di particolari simboli (presenza CSS, presenza PHP) o di link a file/immagini di contenuto potenzialmente didattico, si è incrementato tale punteggio. Per maggiori dettagli, vedere i metodi examineImg e examineLink in cui sono definiti i pesi per ciascun tipo di materiale.
Inoltre, un altro obiettivo del progetto era analizzare ricorsivamente tutte le pagine linkate da ciascuna pagina. A tal fine, se la profondità del collegamento è corretta, prima di accodare il file si controlla che il collegamento sia valido (ovvero che punti realmente ad una pagina HTML). I protocolli supportati sono l'HTTP, l'HTTPS, l'FTP e ovviamente il file system locale.
Descrizione delle classi Java
SeriePagine
La classe SeriePagine modella il set di pagine esplorate o in fase di esplorazione da parte del motore di ricerca. Per ogni pagina scoperta (tramite link in una pagina già esplorata, oppure ricevuta dall'utente come punto di partenza della ricerca) viene creato un corrispondente oggetto Pagina, memorizzato mediante l'HashMap pages ed accessibile attraverso i metodi lookup.
La classe si occupa internamente di ogni dettaglio relativo alla creazione degli oggetti Pagina quando viene effettuato il lookup di una pagina precedentemente non trovata. Viene anche effettuata una normalizzazione degli URL: potrebbe infatti capitare che due URL diversi (specie se si tratta di URL relativi) puntino la stessa pagina web. In questo caso, ai fini del computo del Page Rank e per evitare di esaminare due volte lo stesso file, è necessario ricondurre ogni URL ad una forma canonica.
La classe interagisce inoltre con la classe Downloader per accodare gli URL relativi a nuove pagine non ancora analizzate. A questo scopo viene creato internamente un oggetto di tipo Downloader e viene esportato il metodo getNext() che restituisce una nuova coppia URL <-> file scaricato per l'analisi.
La classe SeriePagine tiene anche traccia di un limite di profondità. Ad ogni pagina è associata una profondità calcolata come distanza dalla pagina di partenza più uno. Se durante l'analisi viene scoperto un collegamento ad una pagina non ancora analizzata, questa viene creata con profondità pari a quella della pagina-padre incrementata di 1. Se così facendo la profondità supera il limite, l'URL di questa pagina non sarà inserito nella classe Downloader. In questo modo per la pagina viene conteggiato il Page Rank, ma la pagina in sé non verrà mai esaminata, a meno che non sia raggiungibile rispettando il limite di distanza tramite qualche altro link.
Per finire, la classe SeriePagine è responsabile dell'ordinamento delle pagine per punteggio singolo durante la stampa delle statistiche. Siccome la classe Pagina implementa l'interfaccia Comparable, è sufficiente inserire tutte le pagine scoperte in un TreeSet e poi iterare sugli elementi del TreeSet stesso. Dopo aver stampato il punteggio di ciascuna pagina associata al sito dell'utente scelto, si stampa un punteggio globale uguale alla somma di essi.
Pagina
La classe Pagina rappresenta la base dati di ciascuna pagina HTML trovata dal programma. Al suo interno, contiene i seguenti attributi:
- un indice numerico che indica la profondità della pagina (distanza dalla pagina iniziale)
- l'URL identificativo
- il punteggio associato a tale pagina
- il Page Rank
- un campo booleano che indica se la pagina è stata realmente analizzata o meno
- un campo booleano che indica se la pagina è una discendente diretta della pagina iniziale
Il Page Rank viene aggiornato chiamando il metodo found ogni volta che il parser trova un link alla pagina considerata. Ogni pagina parte da Page Rank 0 e viene incrementato di 1 ad ogni link. Dato che le pagine vengono create al momento dell'esame del link, ogni pagina ha sicuramente Page Rank superiore ad 1. Fa eccezione la pagina di partenza, che potrebbe non ricomparire mai nell'analisi del web, e quindi potrebbe avere Page Rank pari a 0.
I punteggi vengono assegnati con il metodo setScore, che va a modificare il punteggio totale della pagina. Al momento della stampa delle statistiche, si utilizza il metodo getScore che ritorna il punteggio totale pesato in base alla profondità della pagina e sommato al proprio Page Rank: ci è sembrato infatti il metodo migliore per valorizzare in modo coerente le pagine più direttamente accessibili all'utente finale.
PaginaId
La classe PaginaId è una classe helper realizzata per contenere l'associazione FileReader <-> URL. In questo modo è possibile passare allo scanner la pagina da esaminare (il FileReader) e allo stesso tempo sapere a quale URL fosse associata (necessario al parser, in quanto gli URL sono la chiave necessaria ad ottenere l'oggetto Pagina dalla classe SeriePagine).
Test sul campo
Una volta completato il programma, il programma è stato testato nell'ambiente per cui è stato progettato. Abbiamo infatti ottenuto la lista di tutti i siti web attualmente ospitati dal server del LABinf e dato in pasto ciascun sito al programma.
I risultati sono inseriti in tabelle dalle quali sono stati ricavati i seguenti due grafici:
Verificando manualmente il contenuto dei siti che hanno registrato il punteggio maggiore, possiamo affermare che i risultati sono coerenti con le attese:
