Forse cercavi SiCapisce… [Updated]

Posted on 6 giugno 2011

0


La distanza di Levenshtein è la misura della differenza fra due stringhe espressa nel numero di modifiche necessarie a trasformare una stringa nell’altra, così da determinare quanto siano simili due stringhe: se il risultato è “0” (zero) le due stringe sono identiche, mentre a numero elevato corrisponde una differenza elevata.

Per fare un esempio, in PHP è possibile riprodurre la funzione “Forse cercavi”, resa famosa dal motore di ricerca Google, mediante il seguente codice (estratto dal manuale PHP – http://www.php.net/manual/en/function.levenshtein.php):

<?php
// input misspelled word
$input = 'carrrot';

// array of words to check against
$words  = array(‘apple’,’pineapple’,’banana’,’orange’,
‘radish’,’carrot’,’pea’,’bean’,’potato’);

// no shortest distance found, yet
$shortest = -1;

// loop through words to find the closest
foreach ($words as $word) {

// calculate the distance between the input word,
// and the current word
$lev = levenshtein($input, $word);

// check for an exact match
if ($lev == 0) {

// closest word is this one (exact match)
$closest = $word;
$shortest = 0;

// break out of the loop; we’ve found an exact match
break;
}

// if this distance is less than the next found shortest
// distance, OR if a next shortest word has not yet been found
if ($lev <= $shortest || $shortest < 0) {
// set the closest match, and shortest distance
$closest  = $word;
$shortest = $lev;
}
}

echo “Input word: $input\n”;
if ($shortest == 0) {
echo “Exact match found: $closest\n”;
} else {
echo “Did you mean: $closest?\n”;
}

?>

Questo significa che, se dovete confrontare due stringhe di testo, potete usare la distanza di Levenshtein (magari messa in rapporto al numero di caratteri delle due stringhe) per ottenere una sorta di coefficiente di somiglianza. Questo vi permette di capire se un messaggio su Twitter è simile ad un altro, o se due lunghi testi possono essere considerati somiglianti, eccetera.

Un altro metodo è quello descritto da Ian Barber alla pagina http://phpir.com/shingling-near-duplicate-detection, dove ognuno dei due testi da confrontare viene suddiviso nei corrispondenti 4-gram, così da poter poi estrarre, di questi due elenchi di 4-gram, il minimo comun denominatore (funzione http://it.php.net/array_intersect).

AGGIORNAMENTO (giugno 2011):
Un’altra possibile applicazione della distanza di Levenshtein è quella che Rollo Carpenter ha implementato nel suo chatterbot automatico Cleverbot (http://cleverbot.com/). Qui il sistema memorizza tutto ciò che gli utenti scrivono e, per dare una risposta, pesca da questo repository (che è dunque creato dagli utenti) frasi che siano similia quanto inserito.

Per maggiori informazioni esistono alcuni video in cui Rollo Carpenter spiega il funzionamento dei suoi chatterbot.