Agoritmo de Distancia de Levenshtein
Visual CSharp .NET
4.047 visualizaciones desde el 7 de Diciembre del 2016
Hola a todos, esta vez comparto un proyecto sobre el cual he estado trabajando, el propósito de este proyecto es lograr identificar que tan diferentes son dos palabras (para mi caso de uso nombres), para lo cual he implementado un ya muy extendido algoritmo de calculo de Distancia, a continuación la descripción del mismo, texto tomado de Wikipedia.
La distancia de Levenshtein o distancia entre palabras es el número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Se entiende por operación, bien una inserción, eliminación o la sustitución de un carácter. Es útil en programas que determinan cuán similares son dos cadenas de caracteres.
Por ejemplo, la distancia de Levenshtein entre "casa" y "calle" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.
casa → cala (sustitución de 's' por 'l')
cala → calla (inserción de 'l' entre 'l' y 'a')
calla → calle (sustitución de 'a' por 'e')
Para el ejemplo que comparto he desarrollado una ventana de pruebas que consume el algoritmo tanto en c# como en visual basic.
Primero compara Apellidos, luego compara si hay cambios entre apellido y nombre, luego compara nombre y luego segundo nombre, para todo usa el algoritmo de distancia, por ultimo en caso de que no sea aprobado la comparación nombre a nombre, usa toda la cadena de nombres para comparar y dar el resultado final.
Recibe como parámetros de entrada Source1 = Nombre1+Nombre2+Apellido, y Source2 (igual que el anterior), estos los he puesto en una clase para enviarlo como parámetro.
Los resultados están en una clase que devuelve, MENSAJE, LOG, y un boolean indicando el resultado.
Copio solo el código del Algoritmo, la implementación del mismo estará para descargar.
Cualquier comentario me escriben.
Acá ejemplos:
La distancia de Levenshtein o distancia entre palabras es el número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Se entiende por operación, bien una inserción, eliminación o la sustitución de un carácter. Es útil en programas que determinan cuán similares son dos cadenas de caracteres.
Por ejemplo, la distancia de Levenshtein entre "casa" y "calle" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.
casa → cala (sustitución de 's' por 'l')
cala → calla (inserción de 'l' entre 'l' y 'a')
calla → calle (sustitución de 'a' por 'e')
Para el ejemplo que comparto he desarrollado una ventana de pruebas que consume el algoritmo tanto en c# como en visual basic.
Primero compara Apellidos, luego compara si hay cambios entre apellido y nombre, luego compara nombre y luego segundo nombre, para todo usa el algoritmo de distancia, por ultimo en caso de que no sea aprobado la comparación nombre a nombre, usa toda la cadena de nombres para comparar y dar el resultado final.
Recibe como parámetros de entrada Source1 = Nombre1+Nombre2+Apellido, y Source2 (igual que el anterior), estos los he puesto en una clase para enviarlo como parámetro.
Los resultados están en una clase que devuelve, MENSAJE, LOG, y un boolean indicando el resultado.
Copio solo el código del Algoritmo, la implementación del mismo estará para descargar.
Cualquier comentario me escriben.
Acá ejemplos:
{int coste = 0;{}{}{{);}}}