[Hackerjournal 203] Distanza di Levenshtein – Implementiamo il forse cercavi di Google

[Hackerjournal 203] Distanza di Levenshtein – Implementiamo il forse cercavi di Google

in: Hacker Journal So/Code: Generico Data: 02/09/2010 Ora: 13.11:01 Articolo visualizzato: 1247 volte
Il “forse cercavi” di Google è una funzionalità della ricerca molto comoda nel caso di “orrori” di battitura o semplice dubbio. Vediamo come riprodurla per le ricerche dei nostri siti. L’algoritmo di ricerca della parola ipoteticamente corretta si basa sulla distanza di Levenshtein anche nota come ‘Edit Distance’. [LA DISTANZA DI LEVENSHTEIN] La distanza di Levenshtein è il numero di modifiche elementari necessarie per trasformare una stringa A in B. Le modifiche sono: Sostituzione di un carattere Cancellazione di un carattere Aggiunta di un carattere Mettiamo caso che nella nostra ricerca scrivessimo erroneamente linxu.Per trasformare “linxu” in “linux” sono necessarie n modifiche. Questa n è la distanza di Levenshtein. La distanza quindi sarà: Levenshtein(‘linxu’,’linux’) Minore è il numero che esprime questa distanza maggiore sarà l’attinenza tra le parole. Per far funzionare il tutto abbiamo bisogno di un enorme dizionario italiano: ne ho estrapolato uno abbastanza completo eseguendo un ‘merge’ di diversi dizionari. Il problema è che dovremmo eseguire il test per ogni parola presente nel dizionario. Il che diventerebbe molto pesante poiché, avendo circa 145000 parole, ci sarebbero 145000 distanze da calcolare. La soluzione consiste nell’effettuare un primo filtro nella selezione delle parole; quindi utilizzare un database (nel nostro caso MySQL) per estrarre solo le parole che hanno una lunghezza pari alla parola cercata ± un valore numerico a nostro piacimento, per esempio 1. Quindi estrapoleremo dal database - nel caso di linxu = 5 char (caratteri) - tutte le parole che hanno lunghezza di 4,5,6 e le confronteremo con la distanza di Levenshtein. Per velocizzare ulteriormente l’estrazione dal dizionario indicizziamo i campi “parola” e “lunghezza parola”. [IL NOSTRO DIZIONARIO] Il nostro dizionario è composta da 143770 parole. I campi del database sono organizzati così: N_REC_ID - Progressivo del record C_PAROLA - Parola N_CHRLEN – Intero che rappresenta la lunghezza della parola E’ disponibile un dump del database con le 143770 parole al seguente indirizzo ( Oltre al SQL è in CSV,TXT e XLS): http://www.guido8975.it/index.php?ctg=6&id=67 [ATTO PRATICO] Questo script si basa su 3 files: • conf.php Solito file di configurazione e connessione al database ricerca.php File della ricerca proc.php File dell’algoritmo File conf.php <?php $server="localhost"; $user_n="root"; $password="password"; $db_name="dizionario"; $connessione = mysql_connect($server, $user_n, $password) or die("Connessione non riuscita: " . mysql_error()); mysql_select_db($db_name, $connessione) or die ("Errore nella selezione del database."); ?> File ricerca.php La parola è inserita,in questa pagina a scopo illustrativo in una variabile $rRic a cui possiamo assegnare invece di ‘linxu’ i dati provenienti da un POST con $_POST[‘nomecampopost’]. <?php include 'proc.php'; $rRic = trim(‘linxu’); if(!empty($rRic)) { $rRicRes = ""; $rRicArr = explode(" ", $rRic); foreach ($rRicArr as $j) { $rRicRes .= LevWord($j)." "; } $rRicRes = substr_replace($rRicRes ,"",-1); } if($rRicRes <> $rRic){ echo "Forse cercavi: ".$rRicRes;} //Ricerca vostro sito //Qui aggiungerete la parte di codice per effettuare la ricerca nel vostro sito. ?> File proc.php Qui è presente la funzione che calcola la distanza di Levenshtein. Modificando la variabile $rSrcDis, che di default è a 1, possiamo aumentare lo spettro di ricerca della parola nel db. Maggiore è il numero maggiore sarà lo spettro di ricerca. <?php function LevWord($SearchPostWord){ include 'conf.php'; $rSrcDis = '1'; $SearchPostWordLen = strlen($SearchPostWord); $query_rch = "SELECT * FROM italiano WHERE N_CHRLEN in (".($SearchPostWordLen $rSrcDis).",".$SearchPostWordLen.",".($SearchPostWordLen+$rSrcDis).") "; $result_rch = mysql_query($query_rch, $connessione); $rWordLevDst = -1; while($row_rch = mysql_fetch_array($result_rch)){ $rLevDst = levenshtein(strtolower($SearchPostWord), strtolower($row_rch['C_PAROLA'])); if($rLevDst == 0) { $rWord = $row_rch['C_PAROLA']; $rWordLevDst = 0; break; }elseif($rWordLevDst < 0 \|\| $rLevDst <= $rWordLevDst) { $rWord = $row_rch['C_PAROLA']; $rWordLevDst = $rLevDst; } } if(!empty($rLevDst)){ return $rWord;}else{ return $SearchPostWord;} mysql_close(); } ?> Conclusione L’esempio completo è disponibile sul sito http://www.guido8975.it/index.php?ctg=6&id=67 .Dove sono disponibili sorgenti e dump del database. I sorgenti scaricabili sono anche commentati. Un esempio del funzionamento è implementato in http://www.geek-blog.it/ nella ricerca. Guido Camerlingo AKA Guiz
Commenti (1) \| Autore: Guido Camerlingo (Guiz) Tags: Hacker Journal 203 distanza articolo Levenshtein