Apache Lucene

Lucene è una libreria che permette di avere in Java un motore di ricerca per diverse tipologie di file. E’ un progetto opensource della Apache Software Foundation scritto da Doug Cutting. E’ una libreria estremamente flessibile che permette di inserire nelle applicazioni le funzionalità di un motore di ricerca. Per maggiori informazioni si consulti il sito ufficiale http://lucene.apache.org/java/docs/index.html.

Caratteristiche di Lucene

Lucene presenta una vasta collezione di interfacce che definiscono tutti i classici passi della ricerca (come vogliono i buoni libri di Information Retrieval). Questa libreria quindi non è un vero e proprio motore di ricerca che noi richiamiamo dicendogli “Mi cerchi questa cosa?” e lui fa tutto in automatico. Proprio per questo motivo per una parte non viene subito capito dagli sviluppatori. Bisogna però rendersi conto della flessibilità delle API che vengono messe a disposizione da Lucene. Infatti una volta capito il modo in cui possiamo adattare i dati che vogliamo ricercare al pattern di Lucene, il suo utilizzo diventa molto semplice. Una base di dati testuale Lucene viene chiamata, con un termine che può essere fuorviante, indice (Index); utilizzando la terminologia dei database relazionali, possiamo dire che ogni indice contiene una sola tabella le cui righe altro non sono che i documenti da noi inseriti. L’indice è normalmente contenuto in una cartella del filesystem, ma esistono altre possibilità, quali la creazione di un indice in RAM, utilizzato soprattutto per aumentare le prestazioni (attenzione però al limite imposto dalle dimensioni della memoria!). All’interno dell’indice vengono inseriti i documenti (istanze di Document), a loro volta divisi in campi o colonne (Fields); come nei database esistono vari tipi di campi, anche se in questo caso il tipo di dati è lo stesso per ogni colonna (o quasi, in realtà esistono alcune piccole differenze). I campi testuali veri e propri (come il titolo ed il corpo di un documento) verranno indicizzati , mentre altri campi, ad esempio l’identificatore del documento all’interno di un database, saranno solo salvati, per essere utilizzati come riferimento. In pratica non sarà possibile eseguire ricerche in questi campi, ma solo accedere al loro valore, nei documenti ritornati da una query eseguita su un altro campo. Lo scenario di utilizzo prevede infatti nella quasi totalità dei casi l’affiancamento della base di dati full-text ad una relazionale. Così facendo utilizzeremo Lucene per fornire un sistema di ricerca (e per presentarne i risultati), mentre quando l’utente desidererà visualizzare un documento (ad esempio cliccando sul titolo) accederemo ad una pagina popolata dal database relazionale; sfrutteremo Lucene per l’efficienza delle ricerche ed il DBMS per la maggiore velocità nella selezione di un singolo elemento (aiutato in questo magari da un opportuno meccanismo di caching, attivo e passivo).

Inserire un documento nell’indice

L’inserimento di un documento all’interno dell’indice comporta una scansione del testo, per individuare le parole presenti; tale procedimento prende il nome di analisi ed ovviamente è dipendente dalla lingua del testo. Lucene fornisce un analizzatore standard, mirato sulle necessità delle lingue occidentali più diffuse: una volta che il documento (o meglio, i suoi campi) sono stati indicizzati questi sono disponibili per l’esecuzione di ricerche.  Come abbiamo già detto, i campi possono essere trattati in maniera diversa, a seconda della funzione che rivestono. I campi testuali sono normalmente analizzati (scomposti in una lista di termini) e quindi indicizzati, mentre il campo identificatore (che contiene solamente un riferimento al corrispondente elemento della base di dati relazionale) deve essere solamente salvato all’interno dell’indice, per essere usato come riferimento tra l’indice full-text e una base di dati relazionale. L’indicizzazione di documenti è ottimizzata da Lucene, in maniera tale da aumentare le prestazioni senza però interferire con eventuali operazioni contemporanee di ricerca. Il metodo IndexWriter.optimize() serve appunto a riorganizzare l’indice, per aumentare le prestazioni delle future ricerche (e scritture). La gestione dell’accesso concorrente (in scrittura e lettura, quindi indicizzazione e ricerca) ad un indice Lucene è piuttosto articolata, anche se di facile comprensione: è possibile un solo accesso in scrittura, ma che può essere condiviso da vari processi logici (o thread) di indicizzazione, mentre non sono poste limitazioni alle ricerche contemporanee.

La ricerca

E’ possibile eseguire ricerche sull’indice in due modalità distinte: utilizzando direttamente le API di ricerca oppure utilizzando una sorta di linguaggio di interrogazione. Il primo metodo prevede l’utilizzo delle classi che derivano da Query e che si trovano nel package org.apache.lucene.search, per brevità si aggiungeranno solo alcune note su queste classi più avanti; il secondo metodo sarà dettagliato nel prossimo paragrafo. L’accesso in lettura all’indice avviene attraverso la classe IndexSearcher. Il metodo QueryParser.parse() ci permette di ottenere direttamente un oggetto Query; è necessario passare a questo metodo la stringa di ricerca (che naturalmente può essere composta da più parole), un campo in cui eseguire la ricerca ed un analizzatore (usato per trattare la query string, che sostanzialmente è elaborata come se fosse un documento da inserire nell’indice). Il metodo IndexSearcher.search() restituisce un oggetto di tipo Hits, che contiene i risultati. Per evitare di incappare in errori abbastanza fastidiosi e che potrebbero rivelarsi di difficile interpretazione è bene avere presente che i documenti all’interno della collezione Hits non sono più accessibili quando si è chiamato il metodo IndexSearcher.close(), pertanto è necessario estrarre i dati necessari alla presentazione dei risultati prima di procedere a questa chiamata. Naturalmente utilizzando le API è possibile eseguire ricerche più complesse, ad esempio per termini vicini tra loro (PhraseQuery), oppure utilizzando wildcards.

Sintassi della Query

Una query è suddivisa in termini ed operatori. Ci sono due tipi di termini: termini singoli e frasi. Un termine singolo è una parola singola come “hello” o “test”. Una frase è un gruppo di parole racchiuso tra apici doppi come “hello word”. Termini multipli possono essere combinati insieme tramite operatori booleani per formare una query complessa. Di seguito si riportano una serie di modificatori e di operatori tra termini della query che permettono una più ampia possibilità di ricerca.

Operatori Booleani

Gli operatori booleani permettono di combinare i termini tramite operatori logici. Lucene supporta AND, ”+”, OR, NOT e “-“ come operatori booleani. L’operatore OR è quello di default. Ciò significa che se non ci sono operatori tra due termini, viene sottointeso l’operatore OR. Tale operatore collega due termini e trova un documento rilevante e uno dei due termini esiste nel documento in esame. L’operatore AND trova i documenti che presentano entrambi i termini della query nel testo di un singolo documento. L’operatore “+” richiede che il termine dopo il simbolo “+” esista in un field del documento (devono contenere il termine necessariamente). L’operatore NOT esclude i documenti che contengono il termine dopo il NOT. L’operatore “-“esclud i documenti che contengono il termine dopo il simbolo “-“. Raggruppamento

Lucene supporta l’uso delle parentesi per raggruppare dei termini per formare delle sotto-query. Ciò è utile se si vuole controllare la logica booleana di una query (elimina possibili ambiguità).

Ricerca tramite Wildcard

Lucene supporta singole o multiple ricerche tramite wildcard all’interno di un singolo termine (non all’interno di frasi). Per realizzare una ricerca utilizzando un singolo carattere come jolly si usa il simbolo “?”. Per realizzare una ricerca con caratteri multipli come jolly si usa il simbolo “*”. Ad esempio per ricercare “text” oppure “test” si può usare la sintassi: te?t . Altrimenti si possono ricercare 0 o più caratteri jolly, ad esempio per trovare “test”, “tests” oppure “tester” utilizzando la sintassi: test*.

Ricerca Fuzzy Lucene supporta la ricerca fuzzy basata sul’algoritmo di Levenshtein Distance (o Edit Distance). Per realizzare una tale ricerca si usa il simbolo tilde “~” alla fine di un termine. Ad esempio per ricercare un termine simile nello spelling a “roam” si usa la sintassi: roam~ , questo ritornerà come risultato i termini come foam e roams. Inoltre è possibile specificare la similarità richiesta, cioè un valore tra 0 e 1, tale che con un valore vicino ad uno saranno ritornati solo i  termini con un’alto grado di similarità. Il valore di default è 0.5.

Boosting di un termine

Un dato termine può assumere una rilevanza maggiore all’interno di una query, per assegnargli un peso maggiore si utilizza il simbolo “^” insieme ad un fattore di incremento (un numero). Più alto sarà il fattore maggiormente rilevante sarà il termine.

Scoring

Lucene utilizza una combinazione del Vector Space Model (VSM) dell’Information Retrieval e del Boolean model, per determinare quanto un documento sia rilevante rispetto ad una query dell’utente. In generale, l’idea che sta dietro il VSM è che se più volte si presentano termini della query in un documento rispetto al numero di volte che tali termini appaiono in tutti i documenti della collezione, tanto più sarà rilevante quel documento rispetto alla query. Esso inoltre usa il Boolean Model per prunare i documenti che devono essere sottoposti a scoring basandosi sull’uso della logica booleana quando si specifica una query. Lucene inoltre aggiunge alcune funzionalità e raffinamenti a questo modello per supportare la ricerca fuzzy e la ricerca booleana, ma essenzialmente rimane un sistema basato sul VSM. Il sistema di scoring è molto dipendente da come i documenti sono indicizzati. In Lucene gli oggetti che sono risultato della ricerca sono dei Documents. Ogni Document è una collezione di Fields ed ogni field a sua volta ha una semantica che descrive come è stato creato e conservato nell’indice. È importante notare che lo scoring di Lucene lavora sui Fields e poi combina i risultati per ritornare i Documents (i documenti veri e propri). Ciò è importante perché due documenti che hanno lo stesso identico contenuto, ma uno ha il contenuto in due Field e l’altroo in un solo Field ritorneranno un differente risultato per la stessa query a causa della diversa normalizzazione dovuta alla lunghezza dei campi. Lucene permette di influenzare il risultato della ricerca utilizzando il “boosting” (incremento) a diversi livelli:

• Boosting al livello del documento: quando si indicizza si incrementa la rilevanza di un documento (document.setBoost()) prima che sia aggiunto all’indice;
• Boosting al livello del Field: quando si indicizza si incrementa la rilevanza di un field (field.setBoost()) prima che sia aggiunto al documento e prima di aggiungere il documento all’indice;
• Bosting al livello della query: durante la ricerca si può incrementare la rilevanza di una clausola di query utilizzando Query.setBoost().

Lo score di una query q per un documento a è correlato al coseno della distanza o prodotto scalare, tra il vettore rappresentante il documento e quello rappresentante la query come prevede il VSM. Un documento il cui vettore è più vicino a quello della query è quello che avrà un punteggio maggiore. Lo score è calcolato come segue: score (q,d)= coord(q,d) · queryNorm(q) · ∑ _{t in q} (tf(t in d)· idf(t)² · t.getBoost() · norm(t,d)) dove:

• tf(t in d) è correlato alla frequenza del termine, definito come il numero di volte che un termine t è presente nel documento d oggetto dello scoring. Documenti che hanno più occorrenze di un dato termine ricevono uno score più alto. Tale indice è calcolato di default come:

tf(t in d) = frequency ^½

• idf(t) indica la frequenza inversa nel documento Questo valore è correlato all’inverso della docFreq(cioè il numero dei documenti in cui compare il termine t). Ciò significa che termini “rari” (meno frequenti in tutti i documenti) danno un contributo maggiore allo score totale. Il calcolo di default di tale indice è:

idf(t) = 1 + log (numDocs/docFreq+1)

• coord(q,d) è un fattore basato su quanti termini della query sono trovati in uno specifico documento. Tipicamente, un documento che contiene più termini della query riceverà un punteggio maggiore rispetto ad un altro che ne ha meno.
• queryNorm(q) è un fattore di normalizzazione usato per rendere lo score tra query comparabile. Questo fattore non influenza il ranking di un documento  (poiché tutti i documenti classificati sono moltiplicati per lo stesso fattore), ma piuttosto cerca di rendere lo score derivante da differenti query (o effettuato su indici diversi) comparabile. Tale indice è calcolato come:

queryNorm(q) =1 / sumOfSquaredWeights^½

La somma dei pesi al quadrato ( dei termini della query) è calcolata come: sumOfSquaredWeights= q.getBoost()²∑ _{t in q} idf(t)t.getBoost()) ²

1. t.getBoost() è un incremento della rilevanza del termine t nella query q;
2. norm(t,d) comprende dei fattori di boosting e di lunghezza:
   1. Document boost
   2. Field boost
   3. lengthNorm(field) calcolato quando il documento è aggiunto all’indice in accordo al numero di token di questo field nel documento, cosicché field meno lunghi contribuiscono di più al punteggio finale.

Quando un documento è aggiunto all’indice, tutti i fattori visti sopra sono moltiplicati. Se il documento ha campi multipli con lo stesso nome, tutti i loro boost sono moltiplicati insieme:

norm(t,d) = doc.getBoost() lengthNorm(field)  ∏ f.getBoost()