Stringhe simili e distanza di Levenshtein
Nr. 14

11/06/2007
Stringhe simili e distanza di Levenshtein

La condizione di due numeri "quasi" uguali si può ottenere abbastanza facilmente con un'espressione, ad esempio

|x-y| < e

con e molto piccolo. E se si tratta di due stringhe ? Risulta utile in tal caso la cosiddetta "distanza di Levenshtein" (vedi anche ad esempio it.wikipedia.org/wiki/Distanza_di_Levenshtein ) che è in pratica il numero di operazioni elementari (inserimenti, cancellazioni o sostituzioni di singoli caratteri) necessarie per trasformare una stringa A in una B. In questo documento, oltre a dare una routine per la sua implementazione in C# (abbastanza banale invero) si mostra come utilizzarla per normalizzare archivi contenenti record erroneamente simili, che capitano spesso specie nell'ambito dei software gestionali a causa di errati inserimenti. Ad esempio quando due utenti inseriscono lo stesso soggetto fisico con convenzioni diverse nella sua descrizione (es. Via e V., Piazza e P.zza e via dicendo). Nel concreto si individuerannno contesti di record (o documenti) "simili" ovvero fortemente candidati a rappresentare lo stesso soggetto e quindi ad essere "fusi" in uno solo.

Questo sito è ottimizzato per la risoluzione 1024x768, testato su Internet Explorer 6 e Mozzilla Firefox 2.