Forse cercavi: distanza di Levenshtein

Settembre 11, 2008 | By mariano In Appunti digitali, java, programmazione |
FONTE: http://mariano.altervista.org/wordpress
E' LA TUA PRIMA VOLTA SU "IL BLOGGATORE"? SEGUI GRATIS I NOSTRI FEEDS!

Spesso capita di digitare in maniera errata una chiave di ricerca e vedersela correggere non appena clicchiamo il tasto ‘Invio’. Cosa succede? Come può un computer, nella maggior parte dei casi, capire cosa volevamo veramente scrivere? La risposta, abbastanza diretta, è: distanza di Levenshtein (o se lo trovate troppo complicato da pronunciare/scrivere, distanza di edit). Considerate due stringhe sorgente e destinazione, la distanza di Levenshtein è il numero di operazioni elementari necessarie per trasformare la stringa sorgente in quella di destinazione. Essa definisce tre operazioni elementari: i) la cancellazione di un carattere; ii) la sostituzione di un carattere; iii) l’inserimento di un nuovo carattere. Due stringhe uguali hanno distanza di Levenshtein pari a 0.