G.Morreale
Introduzione:
I moderni motori di ricerca, riescono a proporre una versione "corretta" di una query presunta erronea.
Quante volte vi sarà capitato su google di effettuare un errore di digitazione e google vi ha risposto, ad esempio, con un
"Forse Cercavi: Java"
dopo aver digitato 'jav'.
Gli approcci per raggiungere tale obiettivo sono diversi:
- Minimum Edit distance: Calcolare il numero di inserimenti, cancellazioni e sostituzioni necessarie a trasformare una stringa(Quella presupposta erronea) in un'altra(quella presupposta corretta)
- Similiarity Key: Basato su un dizionario dove sotto la stessa chiave ci sono le stringhe similiari.
- Letter n-gram: n indica il numero di lettere all'interno di una sotto-sequenza di una parola. Es. 3-grams per la parola lucene "luc", "uce", "cen","ene". Confrontare due n-gram può dare con buona approssimazione un suggerimento. Per approfondimenti (http://en.wikipedia.org/wiki/N-gram)
Lucene Spell Checker:
All'interno pacchetto di librerie scaricabili da: http://www.apache.org/dyn/closer.cgi/lucene/java/
è possible trovare una libreria chiamata "lucene-spellchecker-2.4.0.jar" (Si trova nel seguente path: lucene-2.4.0\contrib\spellchecker).
Tale libreria consente di raggiungere l'obiettivo di suggerire una query "vicina" a quella introdotta inizialmente in input.
Quindi qualora il numero di risultati di una query è 0 oppure al di sotto di un certa soglia lo spellchecker potrà suggerire una nuova query.
Lo spellchecker utilizza il metodo letter-ngram, il suo compito è quello di analizzare un suo indice, vediamo in seguito come costruirlo, al fine di calcolare una query similiare in grado di restituire dei risultati "buoni".
La query suggerita dallo spellChecker può essere data in pasto nuovamente ai metodi di ricerca.
Come visto nel precedente articolo la fasi salienti dell'uso della libreria sono 2: Costruzione e Scrittura Indice, e ricerca all'interno dell'indice.
Anche nel caso dello Spell Checker si distinguono due fasi:
- Scrittura del dizionario
- Ricerca all'interno del dizionario
Scrittura del dizionario
Il dizionario dello SpellChecker viene rappresentato dalla classe LuceneDictionary.
Esso viene costruito a partire da un indice.
Adesso costruiamo un package che si occupa dei vari step dell'indicizzazione e costruzione dizionario.
La classe astratta IndexMaker contiene il campo indexDirectory che rappresenta la locazione sulla quale verrà memorizzato l'indice e il metodo generateIndex che dato un gruppo di oggetti Document si occupa della generazione dell'indice.
BaseIndexMaker estende IndexMaker al fine di implementare concretamente il metodo generateIndex.
Il costruttore inoltre prevede il settaggio di alcuni parametri per l'indicizzazione:Analyzer, MaxFieldLength(numero massimo di elementi dell'indice).
La classe SpellIndexMaker è in grado di svolgere le stesse funzioni di BaseIndexMaker, ma in più è in grado di generare il dizionario per lo spellChecking(metodo generateSpellIndex(String fieldname).
Il dizionario viene creato su un determinato campo del document.
Di seguito il codice delle 3 classi presenti nel diagramma e appena descritte
- IndexMaker
package index;
import org.apache.lucene.document.Document;
import org.apache.lucene.store.Directory;
public abstract class IndexMaker
{
protected Directory indexDirectory;
public IndexMaker(Directory dir)
{
this.indexDirectory = dir;
}
public abstract void generateIndex(Document[] documentArray, boolean append);
}
- BaseIndexMaker
package index;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.SimpleAnalyzer;
import org.apache.lucene.document.Document;
import org.apache.lucene.index.CorruptIndexException;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriter.MaxFieldLength;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.LockObtainFailedException;
public class BaseIndexMaker extends IndexMaker
{
Analyzer analyzer;
MaxFieldLength maxFieldLength;
public BaseIndexMaker(Directory indexDirectory)
{
super(indexDirectory);
analyzer = new SimpleAnalyzer();
this.maxFieldLength = IndexWriter.MaxFieldLength.UNLIMITED;
}
public BaseIndexMaker(Directory indexDirectory, Analyzer analyzer)
{
super(indexDirectory);
this.analyzer = analyzer;
}
public BaseIndexMaker(Directory indexDirectory, Analyzer analyzer, MaxFieldLength maxFieldLength)
{
super(indexDirectory);
this.analyzer = analyzer;
this.maxFieldLength = maxFieldLength;
}
/**
* Genera un indice a partire da un array di document.
* L'indice viene creato sulla directory indicata nel costruttore
* @param documentArray - Array di Document da inserire nell'indice
* @param append - Indica se inserire in modalità append o creare un nuovo indice da zero.
*/
@Override
public void generateIndex(Document[] documentArray, boolean append )
{
try
{ //inizializzazione dell'IndexWriter
IndexWriter indexWriter = new IndexWriter(indexDirectory, analyzer, !append, maxFieldLength);
//Inserimento documenti all'interno dell'indice
for (Document d : documentArray)
{
indexWriter.addDocument(d);
}
//committ delle modifiche
indexWriter.commit();
//chiusura del writer.
indexWriter.close();
}
catch (CorruptIndexException ex)
{
Logger.getLogger(this.getClass().getName()).log(Level.SEVERE, null, ex);
} catch (LockObtainFailedException ex)
{
Logger.getLogger(this.getClass().getName()).log(Level.SEVERE, null, ex);
} catch (IOException ex)
{
Logger.getLogger(this.getClass().getName()).log(Level.SEVERE, null, ex);
}
}
}
- SpellIndexMaker
package index;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.apache.lucene.index.CorruptIndexException;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.search.spell.LuceneDictionary;
import org.apache.lucene.search.spell.SpellChecker;
import org.apache.lucene.store.Directory;
/**
* Tale classe è in grado di costruire un indice su una determinata directory a partire
* da un array di document.
* Inoltre è in grado di costruire un dizionario partendo dalla directory dell'indice al fine
* di poterlo utilizzare in fase di spell checking(Ricerca query similiari).
*/
public class SpellIndexMaker extends BaseIndexMaker {
Directory dictionaryDirectory;
public SpellIndexMaker(Directory indexDirectory, Directory dictionaryDirectory)
{
super(indexDirectory);
this.dictionaryDirectory = dictionaryDirectory;
}
public void generateSpellIndex(String fieldName)
{
IndexReader indexReader = null;
try
{
//apertura dell'indice
indexReader = IndexReader.open(indexDirectory);
//inizializzazione dizionario su un dato campo
LuceneDictionary dictionary = new LuceneDictionary(indexReader, fieldName);
//inizializzazione oggetto spellchecker
SpellChecker spellChecker = new SpellChecker(dictionaryDirectory);
//scrittura del dizionario sulla Directory
spellChecker.indexDictionary(dictionary);
} catch (CorruptIndexException ex)
{
Logger.getLogger(this.getClass().getName()).log(Level.SEVERE, null, ex);
} catch (IOException ex)
{
Logger.getLogger(this.getClass().getName()).log(Level.SEVERE, null, ex);
} finally
{
if (indexReader != null)
{
try
{
indexReader.close();
} catch (IOException ex)
{
Logger.getLogger(this.getClass().getName()).log(Level.SEVERE, null, ex);
}
}
}
}
}
Dando un occhio ai commenti e al codice stesso non credo sia difficile cogliere la struttura e il significato dei vari step.
Al fine di utilizzare il codice si possono utilizzare le seguenti righe di codice.
//Connessione e ottenimento array di document dal db
//E' possibile utilizzare qualsiasi altro metodo che generi un insieme di Document
String dbUrl = "jdbc:mysql://localhost:3306/mydb?user=peppe&password=sql";
Document[] documentArray = dao.DAO.getContenutiDocument(dbUrl);
//Inizializzazione campi necessari all'indicizzazione
String path = "c:\\luceneIndex"; //path dell'indice.
String pathDict = "c:\\luceneIndex\\Dictionary";//path del dizionario per lo spellchecking.
//Ottenimento oggetto Directory dalla stringa path
Directory dir = (FSDirectory.getDirectory(path));
Directory dirDict = FSDirectory.getDirectory(pathDict);
//Inizializzazione IndexMaker
SpellIndexMaker spellIndexMaker = new SpellIndexMaker(dir, dirDict);
//Generazione indice (Vedi nel path c:\\luceneIndex la creazione dei file dopo l'esecuzione)
spellIndexMaker.generateIndex(documentArray, false);
//Generazione dizionario.
spellIndexMaker.generateSpellIndex(fieldName);
Ricerca e SpellChecking
In maniera del tutto analoga al precedente step(Indicizzazione e Scrittura del dizionario) costruiamo un package che si occupa della ricerca all'interno di un indice e dell'eventuale suggerimento all'interno del dizionario qualora la ricerca non soddisfa le aspettative:
La classe astratta SearchEngine pone le basi per una classe adatta alla ricerca all'interno di un indice; essa è dotata del campo su cui effettuare la ricerca (defaultField), della Directory dell'indice, del numero massimo di hits per il risultato della ricerca, e infine il tipo di operatore, AND o OR. Il metodo da implementare è un metodo che data una stringa effettua la ricerca ritornando oggetti di tipo SearchResult.
La classe SearchResult infatti incapsula il Document su cui la ricerca è stata vincente e il relativo punteggio di affinità per la ricerca.
La classe SimpleSearchEngine implementa il metodo di ricerca e ne aggiunge uno in grado di recepire in input una query rappresentata non più da una stringa ma da un oggetto Query proprio delle librerie di Lucene.
SuggestAndSearchEngine estende le precedenti funzionalità e aggiunge un metodo in grado di suggerire delle query similiari.
Nota bene che suggest suggerisce solo la query similiare, se si vogliono ottenere i risultati "similiari" bisogna dare tale query nuovamente in pasto al metodo search.
Vediamo direttamente il codice:
- SearchResult
package search;
import org.apache.lucene.document.Document;
public class SearchResult
{
//Document contenente il risultato
Document doc;
//Punteggio della ricerca, più è altro più la ricerca è affine
float Score;
public SearchResult(Document doc, float score)
{
this.doc = doc;
this.Score = score;
}
public float getScore()
{
return Score;
}
public Document getDoc()
{
return doc;
}
}
- SearchEngine
package search.engine;
import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.queryParser.QueryParser.Operator;
import org.apache.lucene.store.Directory;
import search.SearchResult;
public abstract class SearchEngine
{
//campo field sul quale effettaure la ricerca
protected String defaultField;
//istanza della Directory sulla quale risiede l'indice
protected Directory indexDirectory;
//Numero di hits
protected int maxHits;
//Operatore di ricerca (AND o OR)
protected Operator operator;
//Analyzer per tokenizzare e filtrare la ricerca
protected Analyzer analyzer;
public abstract SearchResult[] search(String queryString);
}
- SimpleSearchEngine
package search.engine;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.SimpleAnalyzer;
import org.apache.lucene.queryParser.ParseException;
import org.apache.lucene.queryParser.QueryParser;
import org.apache.lucene.queryParser.QueryParser.Operator;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.ScoreDoc;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.store.Directory;
import search.SearchResult;
public class SimpleSearchEngine extends SearchEngine
{
public SimpleSearchEngine(String defaultField, Directory directory, int maxHits, Operator op, Analyzer analizyer)
{
this.defaultField = defaultField;
this.indexDirectory = directory;
this.maxHits = maxHits;
this.operator = op;
this.analyzer = analizyer;
}
/**
* Metodo per la ricerca data una query all'interno dell'index specificato
* nel costruttore
* @param query - Oggetto Query di Lucene
* @return
*/
public SearchResult[] search(Query query)
{
IndexSearcher is = null;
SearchResult[] ret = null;
try
{
//Inizializzazione dell'oggetto chiave della ricerca
is = new IndexSearcher(indexDirectory);
//Ricerca indicando il numero massimo di hits da ottenere
TopDocs topDocs = is.search(query, maxHits);
//Estrazione risultati
ScoreDoc[] scoreDocs = topDocs.scoreDocs;
int len = topDocs.totalHits > maxHits ? maxHits : topDocs.totalHits;
ret = new SearchResult[len];
int i = 0;
for (ScoreDoc sc : scoreDocs)
{
ret[i++] = new SearchResult(is.doc(sc.doc), sc.score);
}
} catch (Exception e)
{
Logger.getLogger(this.getClass().getName()).log(Level.INFO, "Error in searching..", "");
} finally
{
if (is != null)
{
try
{
is.close();
} catch (IOException ex)
{
Logger.getLogger(SimpleSearchEngine.class.getName()).log(Level.SEVERE, null, ex);
}
}
return ret;
}
}
/**
* Metodo per la ricerca all'intero di un index.
* La location(Directory) dell'index è specificata tramite il costruttore
* @param queryString - stringa rappresentante la query, viene convertita
* in Query attraverso il QueryParser
* @return - Insiemi oggetti SearchResult contenenti Document e relativo
* punteggio di affinità
*/
public SearchResult[] search(String queryString)
{
try
{
//Costruzione della query partendo da una stringa
QueryParser queryParser = new QueryParser(this.defaultField, new SimpleAnalyzer());
//Tipo di ricerca (AND o OR)
queryParser.setDefaultOperator(operator);
//parsing vero e proprio della stringa
Query query = queryParser.parse(queryString);
return search(query);
} catch (ParseException ex)
{
Logger.getLogger(SimpleSearchEngine.class.getName()).log(Level.SEVERE, null, ex);
return null;
}
}
}
- SuggestAndSeachEngine
package search.engine;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.index.Term;
import org.apache.lucene.queryParser.QueryParser.Operator;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.TermQuery;
import org.apache.lucene.search.spell.SpellChecker;
import org.apache.lucene.store.Directory;
public class SuggestAndSeachEngine extends SimpleSearchEngine
{
//Directory sulla quale si trova il dizionario
private Directory spellDictionaryDir;
public SuggestAndSeachEngine(String defaultField, Directory indexDirectory, int maxHits, Operator op,Analyzer analyzer ,Directory spellDictionaryDir)
{
super(defaultField, indexDirectory, maxHits, op, analyzer);
this.spellDictionaryDir = spellDictionaryDir;
}
/**
* Data una singola parola il sistema costruisce al massimo nsuggesion Query
* contenenti parole similiari a quella proposta in input.
* @param word - Input sul quale effettuare l'elaborazione
* @param nsuggestion - Numero massimo di suggerimenti e quindi di query da restituire
* @return - Query per le parole similiari a word
*/
public List<Query> suggest(String word, int nsuggestion)
{
List<Query> ret = new ArrayList<Query>();
try
{
//Inizializzazione oggetto chiave del metodo!
SpellChecker spellChecker = new SpellChecker(spellDictionaryDir);
//Se la query string esiste nel dizionario vuol dire che non ha
//senso cercare un suggerimento!
if (!spellChecker.exist(word))
{
//ricerca di parole similiari all'interno del dizionario
String[] similiarWords = spellChecker.suggestSimilar(word, nsuggestion);
if (similiarWords.length != 0)
{
for (String s : similiarWords)
{
//date le parole similiari si procede alla costruzione delle query
ret.add(new TermQuery(new Term(defaultField, s)));
}
}
}
} catch (IOException ex)
{
Logger.getLogger(SuggestAndSeachEngine.class.getName()).log(Level.SEVERE, null, ex);
} finally
{
return ret;
}
}
}
Utilizzare il codice per una ricerca e relativo suggerimento
Vi invito a leggere direttamente il codice e i relativi commenti.
Il meccanismo è abbastanza semplice: Si richiede un input all'utente, si inizializza il motore di ricerca e si richiedono dei risultati.
Se il numero dei risultati è al di sotto di 1, allora si procede con la creazione di query alternative utilizzando lo spellChecking.
Una di queste query, se presente, viene data nuovamente in pasto la motore di ricerca per conseguire dei risultati basati su di essa.
//Catturiamo una stringa per effettuare la ricerca
String sentence = JOptionPane.showInputDialog("sentence");
//Inizializzazione motore di ricerca, indicando
//il campo su cui ricercare, la Directory dell'indice, il tipo di operatore, l'Analyzer e la directory del dizionario.
SuggestAndSeachEngine se = new SuggestAndSeachEngine(fieldName, dir, 10, QueryParser.Operator.OR, new SimpleAnalyzer(), dirDict);
//Richiesta risultati relativi alla query catturata con l'input dialog.
SearchResult[] res = se.search(sentence);
//Stampa a video risultati
int i = 1;
if (res != null)
{
for (SearchResult s : res)
{
System.out.println(i++ + "° " + s.getDoc().get("descrizione") + " - " + s.getScore());
}
}
//Se il numero di risultati ottenuti è meno di 1 si procede con lo spell checking
if (res.length < 1)
{
//Richiesta query di suggerimento
List<Query> suggested = se.suggest(sentence, 2);
//stampa query suggerite
System.out.println(suggested);
//Se esiste almento un suggerimento..
if (suggested != null && suggested.size() > 0)
{
//effettuiamo una nuova ricerca con la prima query suggerita
res = se.search(suggested.get(0));
i = 1;
//stampa risultati con la nuova query.
for (SearchResult s : res)
{
System.out.println(i++ + "° " + s.getDoc().get("descrizione") + " - " + s.getScore());
}
}
}
Migliorare la Qualità dei Risultati
Al fine di migliorare la qualità dei risultati è possibile avvalersi di un suggerimento che tiene conto della frequenza con la quale appare il suggerimento nell'indice (non nel dizionario).
Utilizzando
public String[] suggestSimilar(String arg0, int arg1, IndexReader arg2, String arg3, boolean arg4) throws IOException
Questo overloading è possibile avvalersi di due criteri per l'ottenimento dei risultati.
- La distanza di editing tra l'input e il suggerimento
- La popolarità del suggerimento all'interno dell'indice originale (ribadisco: non nel dizionario).
E le query Composte?
Per semplicità fin ora si è considerato un suggerimento su una singola parola, il metodo suggest infatti è in grado di fornire suggerimenti su una query composta da una singola parola.
Adesso cercherò di spiegare come generare un suggerimento su query composte da diverse parole
(es. input:program jav - suggerimento: programma java)
L'idea di base è quella di suddividere l'input in diversi token e ottenere il suggerimento per ciascuno di essi.
La suddivisione in token potrebbe essere fatta con i canonici metodi offerti dalle librerie standard (es. StringTokenizer o metodo String.split(regx)) ma ciò non tiene conto delle modalità di tokenizzazione utilizzate in fase di creazione indice e ricerca.
Infatti in queste fasi si è fatto uso dell'Analyzer, che ha proprio il compito di gestire la suddivisione delle stringhe composte in token tenendo conto di diversi criteri (più o meno complessi a seconda della classe specifica scelta (SimpleAnalyzer, StandardAnalyzer etc.))
Quindi la suddivisione in token presuppone l'uso dell'Analyzer che attraverso il metodo
public abstract TokenStream tokenStream(String arg0, Reader arg1)
Ci consente di navigare tra i token ottenuti.
Bene, visto però che il metodo suggest realizzato nella classe SuggestAndSearchEngine ritorna diverse Query(diversi suggerimenti), è opportuno creare un metodo suggest in grado di ottenere un solo suggerimento per input.
Tale metodo sarà di supporto al metodo finale suggestComposite la cui realizzazione è obiettivo del paragrafo.
Ne incollo l'implementazione (Da inserire nella classe SuggestAndSearchEngine )
/** * Data una singola parola è in grado di generare il suggerimento * @param word - input su cui generare il suggerimento * @return - Il suggerimento, esso viene proposto sottoforma di Term in modo * da permettere la costruzione di Query composte da più termini */ public Term suggest(String word) { Term term = null; try { //Inizializzazione oggetto chiave del metodo! SpellChecker spellChecker = new SpellChecker(spellDictionaryDir); //Se la query string esiste nel dizionario vuol dire che non ha //senso cercare un suggerimento! if (!spellChecker.exist(word)) { //ricerca di parole similiari all'interno del dizionario IndexReader indexReader = IndexReader.open(indexDirectory); String[] similiarWords = spellChecker.suggestSimilar(word, 1,indexReader,defaultField,true); //String[] similiarWords = spellChecker.suggestSimilar(word, 1); if (similiarWords.length != 0) { //data la parole similiari si procede alla costruzione del Term term = new Term(defaultField, similiarWords[0]); } } } catch (IOException ex) { Logger.getLogger(SuggestAndSeachEngine.class.getName()).log(Level.SEVERE, null, ex); } finally { return term; } }
Anche il metodo suggestComposite per semplicità fornisce un solo suggerimento per input.
Ecco la firma del metodo
public Query suggestComposite(String queryString)
Tale metodo quindi,
- Suddivide in token l'input
- Per ogni token richiede un suggerimento
- Concatena i vari suggerimenti all'interno di una query (tale query è una PhraseQuery, addatta alla composizione con più termini)
Implementazione e relativi commenti:
/**
* Data una query composta da diverse parole il metodo restituisce un
* oggetto Query contenente la query di suggerimento
* @param queryString - input composto anche da diverse parole
* @return - Query suggerita
*/
public Query suggestComposite(String queryString)
{
//Predisposizione di un oggetto Query contente il suggerimento
PhraseQuery query = new PhraseQuery();
//Inizializzazione stream dei token considerando la stringa di input
//e il campo di default su cui basarsi
TokenStream tstream = analyzer.tokenStream(defaultField, new StringReader(queryString));
Token t = new Token();
try
{
Term suggestedTerm = null;
while ((t = tstream.next(t)) != null)
{
//Richiesta suggerimento per ogni token
suggestedTerm = suggest(t.term());
if (suggestedTerm != null)
{
//concatenazione suggerimento all'intero della query
query.add(suggestedTerm);
}
}
} catch (Exception e)
{
Logger.getLogger(this.getClass().getName()).log(Level.INFO, "Token Stream Exception ", e.getMessage());
} finally
{
if (tstream != null)
{
try
{
tstream.close();
} catch (IOException ex)
{
Logger.getLogger(SuggestAndSeachEngine.class.getName()).log(Level.SEVERE, null, ex);
}
}
return query;
}
}
Conclusione
Lucene è una libreria molto potente alla quale è possibile associare feature molto interessanti come quella dello spellChecking
