La distancia de Levenshtein es una herramienta muy potente y aplicada en diferentes correctores ortograficos de editores de texto. La distancia de Levenshtein, que también es conocida como la generalización de la distancia de Hamming, determina la medida de similitud entre dos cadenas de caracteres.
Este algoritmo fue propuesto por Vladimir Levenshtein en 1965 y desde entonces ha sido ampliamente usado para realizar el matching entre cadenas de caracteres con diferente longitud.
La implementación eficiente de éste algoritmo requiere del uso de la programación dinámica puesto que implementa el uso de una matriz de tamaño (n + 1) × (m + 1), donde n y m son las longitudes de los cadenas que se comparan. Su implementación es sencilla y se las presento a continuación. (Esto no lo escribí yo, es un copi paste lo deje así ya esta clara la reseña sobre distancia de Levenshtein lo copie de aqui)
Un ejemplo en java desarrollado con netbeans.
http://www.2shared.com/file/oG5kzucg/Levenshteintar.html
Ahora mas fácil aun encontraran en la api de apache common land la clase StringUtils esta clase tiene un método getLevenshteinDistance
http://commons.apache.org/lang/api-release/org/apache/commons/lang/StringUtils.html#getLevenshteinDistance%28java.lang.String,%20java.lang.String%29
Sobre este tema hay mucha más información por ejemplo :
http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance
http://es.wikipedia.org/wiki/Distancia_de_Levenshtein
http://jc-info.blogspot.com/2009/03/distancia-de-levenshtein-codigo.html
