Questo sito non e' ottimizzato per la visione con nessun browser
particolare, ne' per nessuna risoluzione particolare ne' impone
l'uso di font particolari. Siate liberi di vederlo come vi pare
e piace.
Ultimo aggiornamento: 01 Novembre 2000
Un motore di ricerca fatto in casa |
| A cura di Davide Bianchi |
Come funziona un motore di ricerca e come costruirne ed usarne
uno "casereccio" in Java.
|
| Cosa e' e come funziona un "motore di ricerca" ? |
Un "motore di ricerca" nel senso generale del termine e' un "arnese" che
consente di effettuare delle ricerche all'interno di un sito o
all'interno di tutta Internet. Questo tanto per "il cosa fa", come viene fatto il tutto ? Un motore si basa su di un indice che in generale e' composto da un database, questo database fondamentalmente contiene le seguenti informazioni:
Quando un utente inserisce una parola da ricercare, il "motore" cerca tutti i record che hanno questa parola-chiave, quindi presenta tutte le pagine in cui si ha una corrispondenza. Eventualmente il motore consente di "ridurre" il numero dei risultati ottenuti applicando delle condizioni di filtro sui dati o altro. In generale quindi un motore e' composto da tre parti:
Come si puo' capire i grossi problemi sono i punti (1) e (3), cioe' la costruzione del database inserendo i singoli termini che si vogliono ricercare e la parte di codice che analizza quello che l'utente ha scritto per poi fare la ricerca nel database.
|
||||||||||
| La costruzione del database |
Vi sono fondamentalmente due modi di costruire il database dei
contenuti: il primo modo e' quello di mettersi li' a mano ed infilare
dentro i termini che si vuole che possano essere cercati. Questo sistema e', come si puo' ben capire, moolto lento e molto noioso, pero' consente un controllo assoluto su cosa si mette dentro all'indice. Un secondo modo (molto piu' rapido) e' quello di avere una procedura o programma apposito che si "attacca" ad un sito, lo scandisce reperendo tutte le pagine che lo compongono e, per ogni pagina, estrae e cataloga tutte le parole che compongono la pagina. Esistono (ovviamente) procedure e "motori" gia' fatti e pronti all'uso. Uno di questi e' Microsoft Index Server, che e' in grado di indicizzare l'intero Server. Un altro e' il celebre motore usato da Altavista. Il piccolo problema con questi due e' che il primo funziona solo su macchine IIS, mentre il secondo non e' propriamente a buon mercato, entrambi poi richiedono una macchina notevolmente potente.
|
||||||||||
| Costruire un motore di indicizzazione |
Supponiamo di non avere quei 3-4000 $ da spendere ne' un P3
con 5 Gb di spazio disponibile sotto mano, ma di voler fare un piccolo
motore di ricerca per la nostra Intranet aziendale. Che fare ? Occorre costruire un motore di indicizzazione casereccio. Banalmente, un motore di indicizzazione deve svolgere i seguenti compiti:
Questo per processare l'intero sito. Ci sono poi degli "accorgimenti" da utilizzare per evitare grossi problemi, per esempio evitare di processare link che portano "fuori" dal sito (questo per non processare tutta internet), link che contengono "mailto" e cose simili (in ogni caso il web server risponderebbe con errore).
|
||||||||||
| Una richiesta HTTP |
Per ottenere una pagina HTML occorre collegarsi con un web server,
che di solito sta' in ascolto sulla porta 80, ed inviare una richiesta
HTTP corretta. Che vuol dire ? Vuol dire "parlare" con il Web Server
dicendo quello che lui si aspetta e vuole sentire. Il protocollo HTTP che e' usato e' specificato nella RFC 2068, che e' repribile presso http://info.internet.isi.edu/in-notes/rfc/files/rfc2068.txt. In soldoni, una richiesta viene inviata "spedendo" al server un messaggio del tipo: GET <url> HTTP/1.0 1.0 indica la versione di HTTP, non di HTML, mentre <url> e' un URL valido, cioe' l'indirizzo di una pagina HTML presente sull'HOST. Se tutto va' bene, il server "risponde" spedendo la pagina richiesta al client. Per esempio, se apriamo TELNET e ci colleghiamo al nostro sito Web preferito (specificando 80 come porta di collegamento) e spediamo la richiesta, riceveremo tutta la pagina HTML come risposta. La "risposta" e' qualche cosa di simile a: HTTP/1.1 200 OK Server: Microsoft-IIS/4.0 Content-Location: http://www.soft-land.org/index.html Date: Tue, 24 Oct 2000 08:04:08 GMT Content-Type: text/html Accept-Ranges: bytes Last-Modified: Tue, 29 Aug 2000 06:14:39 GMT ETag: "1adfd0698011c01:7377c" Content-Length: 6091 <html> <head> <title> Articoli, documenti, faq e tutto quello che fa programmazione </title></head> <body> <table width="100%" border=0 cellspacing=0 cellpadding=0> <tr bgcolor=orange> <td width="80%" height="50" align=left> <h1> Articoli, documenti, faq e tutto quello che fa programmazione </td> </tr> </TABLE> <!--- NAVIGATION BAR ---> <hr> <b> <a href="/index.html">Home Page</a> | <a href="/commenti/index.html">Commenti</a> | <a href="/articoli/articoli.asp">Articoli</a> | ...Come si vede, la prima parte di "header" specifica diverse caratteristiche interessanti del server che si trova dall'altra parte, mentre il resto e' il codice della pagina HTML richiesta.
|
||||||||||
| Processare l'HTML |
Ora sappiamo come ottenere una pagina HTML "a mano", il problema e'
nel "processare" la pagina e catalogare le singole parole. La cosa
migliore e' ovviamente quello di farlo fare ad un programma apposito.
Praticamente quello che il nostro programma deve fare e' "scorrere" la pagina, riconoscere l'inizio e la fine dei vari tag, identificare i tag HREF e TITLE, ignorare tutti gli altri ed ignorare tutte le parole che non sono al DI FUORI dei tag. La cosa sembra molto complicata, ma fondamentalmente non lo e'. Il codice che processa la pagina e' (tolte un po' di cose) quello seguente:
for( i=0; i < buffer.length(); i++ )
{
/* read the element (1)*/
process=true;
el = buffer.charAt(i);
/* remove tabs, new line etc. (2)*/
if( el == '\t' || el == '\n' )
{
el = ' ';
}
/* check begin or end of a tag (3)*/
if( el == '<' )
{
/* If I was in the Title, collect the title */
if( inTitle )
{
/* remove trailing spaces */
title = x.toString().trim();
inTitle = false;
}
else
{
/* If I was in the body, process the text */
if( inBody && word.length() > 0 )
{
processWords( word );
}
}
preHtml= false;
inTag = true;
x = new StringBuffer();
}
/* check end of a tag (4) */
if( el == '>' )
{
tag = x.toString();
checkTag( tag );
/* check what tag I found */
switch( tagId )
{
case IBuild.TITLE:
inTitle = true;
break;
case IBuild.HREF:
break;
}
process=false;
inTag = false;
inBody = true;
x = new StringBuffer("");
}
/* if valid char, add to the temporary
buffer (5)*/
if( process )
x.append( el );
/* (6) */
if( inBody )
{
/* I'm in the body of the page, get the word */
word = x.toString();
}
if( inTitle )
{
/* I'm in the title */
title = x.toString();
}
}
Molto brevemente:nel punto (1) utilizzo un flag process per indicare che il carattere e' da processare, questo flag viene resettato ogni volta che leggo un carattere (lo so, e' mostruosamente inefficiente, ma e' il sistema piu' semplice). il singolo carattere viene letto dal buffer ed inserito nella variabile el. In (2) verifico se il carattere e' un newline (CR/LF) o se e' un Tabulatore, se lo e', riduco il carattere ad uno spazio per semplicita'.
In (3) verifico se il carattere e' un <, cioe'
l'inizio di un Tag. Se lo e' procedo a verificare in che condizione
mi trovavo. In (4) verifico se sto' leggendo la fine di un Tag, in questo caso procedo a verificare che tag ho letto. Questo viene fatto dalla funzione specifica checkTag(). In (5), il carattere teste' letto viene aggiunto al buffer temporaneo di elaborazione. In (6), il buffer temporaneo viene assegnato ad una parola di testo normale o ad un titolo, a seconda dello stato attuale (sono in un tag, sono nel titolo, sono nel testo).
|
||||||||||
| Processare i Link |
La fase di processo dei link viene svolta dalla funzione
checkTag, la quale si occupa anche di verificare tutti gli
altri tag. Se il tag viene riconosciuto come un LINK (cioe'
contiene HREF), viene eseguita la funzione parseLink, questa
si occupa di reperire dal tag il vero e proprio URL e di aggiungerlo
all'elenco degli url da processare/gia' processati. La funzione parseLink e' cosi' definita:
/* look for the HREF part of the tag (1)*/
while( t.hasMoreTokens() )
{
p = t.nextToken();
if(p.length() > 4 )
{
if( p.substring(0,4).compareTo("href") == 0 )
{
/* gotcha! */
break;
}
}
}
/* loop and get the real URL */
for( i=0; i < p.length(); i++ )
{
if( p.charAt(i) == 34 || p.charAt(i) == 39 )
{
in++;
}
if( in == 1)
{
l.append( p.charAt(i) );
}
}
/* now remove the first char (") from the URL */
if( l.length() > 1 )
{
p = l.toString();
p = p.substring( 1 );
/* check if the link is a valid one (2)*/
for( i=0; i < extStrip.length; i++ )
{
if( p.indexOf( extStrip[i] ) >= 0 )
{
/* wrong! */
p = "";
break;
}
}
/* Ok, add the link to the list (3)*/
if( p.compareTo("") != 0 )
{
addUrl( p );
}
}
La prima parte del codice, da (1) fino a (2), si
occupa di estrarre dal tag la sola parte relativa all'URL, ignorando
ed eliminando ogni altro elemento (target, class e quant'altro). Al
termine, in (3) cio' che e' rimasto viene confrontato con un
elenco di URL illegali. L'elenco di URL illegali contiene una serie
di url che puntano verso documenti non parserizzabili, come per
esempio documenti WORD (.doc), PDF (.pdf), RTF (.rtf), indirizzi di
FTP (ftp://...) etc. Questi indirizzi sono semplicemente scartati.
Anche indirizzi assoluti (http://) vengono scarati.Quello che rimane (se rimane qualche cosa), viene aggiunto all'elenco dalla funzione addUrl. Questa merita una piccola spiegazione perche' effettua anche lei un po' di elaborazione.
/* check if the url is relative to
this document (1)*/
if( url.startsWith("#") )
{
/* does nothing */
return;
}
/* check if the URL contain a relative position
into a document (#) (2)*/
if( url.indexOf('#') > 0 )
{
/* remove the relative position */
i = url.indexOf('#');
url = url.substring( 0, i );
}
/* check if the url is absolute or not (3)*/
if( ! url.startsWith("/") )
{
/* url is relative, add the current Url */
url = getCurrentUrl( ) + url;
}
/* add the url (4)*/
if( ! urls.contains( url ) )
{
totUrl++;
urls.add( url );
}
In (1) l'url viene verificato per controllare se inizia con
un #, se si', significa che non e' un URL ma un rimando allo
stesso documento, quindi va' scartato (il documento e' gia' in fase
di processo).In (2) controllo se l'url non e' un riferimento specifico ad un documento, cioe' se e' del tipo document#riferimento, se lo e', rimuovo il riferimento per avere solo l'URL. In (3) verifico che l'url sia assoluto, se non lo e', devo aggiungere in fronte l'url corrente, questo per consentire al successivo accesso di reperire il documento (in caso contrario riceverei un errore di "documento non trovato"). La getCurrentUrl processa e ritorna l'url corrente rimuovendo il nome del file .htm o .html in fase di elaborazione ed eventuali parametri. In (4) infine, l'url e' aggiunto all'elenco, non senza verificare che non sia gia' presente. Questo mi evita di processare 'n' volte lo stesso documento.
|
||||||||||
| Processare le singole parole |
La fase di elaborazione delle singole parole non e' poi molto
differente dalla fase di elaborazione dei Link. Le uniche
accortezze che sono prese sono:
Questo e' arguibile, ma ritengo che un termine di meno di 6 caratteri non sia poi cosi' significativo, inoltre mi evita di riempire il database di e, a, il etc. Il codice che effettua l'analisi e' il seguente:
/* (1) */
StringTokenizer t = new StringTokenizer(words,
"\n\t\" ;.:,'<>/?{}[]()*#@$!+-");
String p = "";
int i;
/* loop and process each token */
while( t.hasMoreTokens() )
{
/* get the token and convert in
lower case (2)*/
p = t.nextToken();
p = p.toLowerCase();
/* remove eventually &xgrave... (3)*/
if( (i = p.indexOf("à")) >= 0 )
{
if( i == 0 )
break;
p = p.substring(0, i-1 ) + "a";
}
if( (i = p.indexOf("è")) >= 0 )
{
if( i == 0 )
break;
p = p.substring(0, i-1 ) + "e";
}
if( (i = p.indexOf("ì")) >= 0 )
{
if( i == 0 )
break;
p = p.substring(0, i-1 ) + "i";
}
if( (i = p.indexOf("ò")) >= 0 )
{
if( i == 0 )
break;
p = p.substring(0, i-1 ) + "o";
}
if( (i = p.indexOf("ù")) >= 0 )
{
if( i == 0 )
break;
p = p.substring(0, i-1 ) + "u";
}
/* process only word more than "MINLEN" (4)*/
if( p.length() >= MINLEN )
{
/* save the data (5)*/
writeData( p );
}
}
Il parametro MINLEN e' definito come costante all'inizio
del codice, quindi se volete indicizzare parole piu' corte basta
modificarlo la'.
|
||||||||||
| Il database |
Come database puo' essere usato un qualsiasi database, la struttura
dati minimale e' la seguente:
Queste sono le informazioni minimali da inserire nel db.
|
||||||||||
| Il programma |
Il programma proposto come "motore di indicizzazione" e' scritto in
Java. Questo consente di farlo funzionare praticamente dappertutto,
l'unica cosa che bisogna fare e' installare un JRE (Java Runtime
Environment), che in generale e' gratuito e liberamente scaricabile
da internet. Quella per Windows di SUN e' repribile sul sito
della Sun stessa (java.sun.com). NOTA: Per il collegamento al database nel codice e' impostato l'uso del "bridge" Jdbc/Odbc, questo richiede l'uso del DSN nel pannello di controllo. Se non si vuole usare questo driver/database, e' sufficiente modificare il driver caricato e la connessione al database e ricompilare il codice. Per ricompilare il programma e' necessario il JDK, anch'esso liberamente disponibile dalla stessa Sun. Vedere il tutorial su JDBC della Sun per ulteriori informazioni.
|
||||||||||
| La pagina di ricerca |
La pagina di ricerca (e corrispondente codice di "scansione" del
database) e' realizzata con JSP. Dato che il "motore" di
indicizzazione utilizza un database ODBC, la pagina JSP utilizza
lo stesso principio.
Per far funzionare la pagina e' necessario un Web Server in grado di interpretare il JSP, le alternative a tutt'oggi sono: JServ, TomCat o altri prodotti similari. JServ non e' un Web Server di suo ma si "appoggia" su un altro Web Server che di solito e' Apache. TomCat invece fa' anche da Web Server, inoltre e' molto ma molto piu' semplice da configurare di Apache + JServ ed e' distribuito gratuitamente. La pagina di ricerca che ho costruito e' in grado di interpretare query semplici (del tipo parola and parola or altraparola), ma l'efficienza non e' delle migliori. Probabilmente ridisegnando parte del lavoro come una Stored Procedure all'interno del database (sempre avendo un database che consente questo tipo di cose) si migliorerebbero di molto le prestazioni. Il codice "utile" della pagine e' il seguente (non riporto il codice di inizializzazione ne' il testo della pagina stessa):
/* parse the string and search (1) */
StringTokenizer t = new StringTokenizer(p," ,;." );
/* load the driver and open connection (2) */
try
{
Class.forName("sun.jdbc.odbc.JdbcOdbcDriver");
conn = DriverManager.getConnection("jdbc:odbc:SOFT;
UID=USER;PWD=PASS");
}
catch( Exception e )
{
out.println("Error loading the database driver:" + e.getMessage());
return;
}
/* build the base sql (3) */
sql = "SELECT DISTINCT Title, Url FROM KeyWord WHERE ";
/* parse the string */
while( t.hasMoreTokens() )
{
/* retrive a token and convert to lower case (4) */
original = t.nextToken();
original = original.toLowerCase();
previous = 0;
/* if the string is enclosed in " i must collect */
if( original.startsWith("\"") )
{
/* must collect other token */
while( ! original.endsWith("\"") )
{
original += " " + t.nextToken();
}
/* remove the leading and terminating */
original = original.substring( 1, original.length() -1 );
previous = 0;
}
/* check if the token is "AND" or "OR" (5) */
if( original.compareTo("and") == 0 )
{
/* AND clause */
sql += " AND ";
previous=1;
orand = true;
}
if( original.compareTo("or") == 0 )
{
/* OR clause */
sql += " OR ";
previous=1;
orand = true;
}
/* add the word to the query (6) */
if( previous==0 )
{
if( ! orand )
{
sql += " OR ";
}
sql += " URL IN (SELECT URL FROM KeyWord WHERE"
sql += " Word LIKE '%" + original + "%') ";
orand = false;
}
}
/* display SQL for debug */
out.println(sql);
out.println("<br>");
/* build the statement (7) */
try
{
st = conn.createStatement();
rs = st.executeQuery( sql );
}
catch( SQLException e )
{
out.println("Error building the search query, try again.");
return;
}
Una rapida spiegazione:1 Inizio con il parserizzare la stringa, la StringTokenizer effettua il parsing e mi ritorna 'n' elementi, uno per ogni parola. 2 Apro la connessione con il database. 3 Inizializzo la query SQL inserendo la parte iniziale che non varia mai. Dovro' solo aggiungere le varie clausole "where"... 4 Ogni singolo "token" (parola) e' convertito in minuscolo per evitare problemi successivi. 5 Il token e' poi confrontato con AND o OR per verificare se non sia una parola-chiave. 6 Se si tratta di una parola da ricercare, alla query viene aggiunta una sottoquery per reperire il record "giusto".
Nota: la query cosi' costruita e' di una lentezza e di una
inefficienza unica. Questo perche' per ogni singola parola da
ricercare effettuo una SELECT che ritorna 'n' record, i vari 'n'
record vengono poi confrontati tra di loro per reperire solo
quelli che corrispondono a tutte le parole indicate.
|
||||||||||
| Utilizzare il motore di indicizzazione |
Per prima cosa occorre costruire il database, la tabella che viene
usata si suppone si chiami KeyWord, una volta fatto questo e
collegato il db tramite DSN (nome DSN="SOFT"), siamo pronti per
indicizzare il nostro sito. Il "motore" accetta una serie di parametri, di cui uno (l'host) e' obbligatorio. I parametri sono:
Eseguiamo il motore con: java IBuild -h www.pincopallo.it Ovviamente al posto di www.pincopallo.it ci mettete l'host del vostro sito (o un bel "localhost" se siete sul Web Server stesso). Il motore inizia a richiedere le pagine e visualizza un elenco di pagine "scandite". Al termine dell'indicizzazione viene presentato un conteggio di parole e link indicizzati. A questo punto nel nostro database (se non abbiamo fatto delle cavolate), ci ritroveremo tutte le parole indicizzate.
Il file di log
|
||||||||||
| Miglioramenti e problemi noti |
Dato che l'intero "motore" e' stato sviluppato in qualche cosa come
6 ore, ho "tralasciato" di molto il controllo degli errori, in
pratica le Exception sono "trappate" ma poi non gestite, il che
non e' poi troppo bello. Il motore non memorizza niente della pagina oltre al titolo, sarebbe bene invece memorizzare almeno la prima parte del testo per presentare all'utente un testo leggibile, in modo che possa rendersi conto se il documento e' quello che gli interessa oppure no. Non e' implementato nessun sistema di "paginazione" dei risultati, se la ricerca ritorna 700 record all'utente viene presentato un elenco di 700 righe. Il che non e' molto bello... Nota: dopo aver giocato un po' con questo arnese mi sono reso conto che e' anche molto utile per verificare i link delle pagine. Se un link e' errato si ricevera' infatti una segnalazione di errore che verra' inserita nel file di LOG. Ragion percui ho pensato bene di aggiungere un flag di "test" che consente di fare il solo testing del sito senza inserire effettivamente i dati nel database.
|
||||||||||
| Il motore |
Qui' trovate un unico file .zip che contiene il codice sorgente del
motore (.java), il programma gia' compilato (.class), il sorgente
della pagina di interrogazione (.jsp) ed il database che ho usato
per le mie prove (Access .mdb). Come al solito, commenti e suggerimenti sono bene accetti (anche banconote in busta chiusa...).
|
| L'autore | Davide Bianchi, pomposamente definito Software Engineer dal biglietto da visita, lavora per la Square bv, societa' olandese con sede a Roermond, che si occupa di sviluppo di software con orientamento grafico. Attualmente sta' lavorando in Java (e si diverte un sacco). |
|
Commenti |
Vuoi mandare un commento su questo articolo? Scrivi all'autore. |
|
Contribuire |
Ti senti in grado di scrivere un articolo e vorresti vederlo pubblicato? Leggi come fare |
|
Copyright |
Il presente sito e' frutto del sudore della mia fronte
(e delle mie dita), se siete interessati a ripubblicare
uno degli articoli, documenti o qualunque altra cosa
presente in questo sito per cortesia datemene comunicazione,
cosi' il giorno che faccio delle aggiunte potro' avvisarvi
e magari mandarvi il testo aggiornato.
|
Questo sito non e' ottimizzato per la visione con nessun browser
particolare, ne' per nessuna risoluzione particolare ne' impone
l'uso di font particolari. Siate liberi di vederlo come vi pare
e piace.
Ultimo aggiornamento: 01 Novembre 2000