Ben più sofisticato ed efficacie, invece, è l'algoritmo di calcolo della distanza di Levenshtein. L'obiettivo del procedimento è il calcolo del numero minimo di trasformazioni necessarie per rendere una parola uguale all'altra. Le trasformazioni possibili sono: substitute (sostituzione di un carattere), delete (rimozione di un carattere), insert (aggiunta di un carattere). Ad esempio, le parole "mister" e "mounted" hanno distanza di Levenshtein=4, poiché con tre substitute — la 'i' diventa 'o', la 's' diventa 'u' e la 'r' diventa 'd' — ed una insert (inserimento della 'n'), da "mister" si ottiene "mounted".

È importante notare come questo algoritmo dia ottimi risultati nei più comuni errori di battitura: ad esempio "mister" ha distanza 1 da parole come "misteer" o "misster" (doppia digitazione involontaria di un carattere), "midter" (digitazione di un carattere al posto di un altro), "mistr" o "miter" (omissione di un carattere), ma risulta avere distanza 2 dalla parola che si ottiene in caso di pressione invertita di due lettere (ad esempio "mitser" o "msiter"). Per ottimizzare anche la gestione di questa eventualità di errore, è possibile introdurre la trasformazione switch (inversione di due lettere adiacenti), sebbene questa aggiunta possa penalizzare l'efficienza computazionale dell'algoritmo.

Il secondo problema, invece, tratta il caso di errata trascrizione di un testo ascoltato. In questo caso, ciò che conta è la sonorità delle lettere: ad esempio le lettere 'm' e 'n', 'b' e 'p', 't' e 'd', ecc. hanno suono simile e potrebbero essere confuse tra loro. L'algoritmo Soundex offre un'efficacie soluzione a questo inconveniente, associando a ciascuna stringa da cui sono rimosse le vocali e le lettere H, W e Y, un codice formato dall'iniziale della parola e da una cifra per ognuna delle successive 3 consonanti. E' importante notare che la stessa cifra corrisponde a consonanti dal suono simile: in pratica, ad ogni stringa corrisponde un codice di 4 caratteri (una lettera e 3 numeri), e il confronto di similarità tra stringhe avviene calcolando le differenze tra i codici; parole simili hanno lo stesso codice Soundex. Si può notare che, ad esempio, le parole "Rupert" e "Robert" risultano simili secondo l'agoritmo Soundex. Una variante di questo algoritmo è anche alla base della funzione difference presente in MS SQL per le query su stringhe di testo.

• Pubblicazioni correlate:
• 19-09-2007 Algoritmi di similarità (1/2)