Mostrar los tags: Levenshtein

Este algortimo también es conocido como distancia de edición. La similaridad entre dos cadenas de texto A y B se basa en el conjunto mínimo de operaciones de edición necesarias para transformar A en B, o viceversa. Hay tres operaciones de edición, las cuales son destrucción, inserción y substitución. Entre más cerca de cero es la distancia de Levenshtein más parecidas son las hileras.


El algoritmo es el siguiente:

- El tamaño de la hilera A es x, y el tamaño de la hilera B es y. Si x = 0, retornar y; si y = 0 retornar x.
- Construir una matriz con y + 1 filas y x + 1 columnas. Inicializar la primer fila de la matriz con la secuencia 0, 1, 2, ..., x; y la primer columna de la matriz con la secuencia 0, 1, 2, ..., y.
- Colocar cada carácter de la hilera A en su correspondiente celda i (i va de 1 a x).
- Colocar cada carácter de la hilera B en su correspondiente celda j (j va de 1 a y).
- Si A(i) es igual a B(j) el costo de la celda es 0.
- Si A(i) es diferente de B(j) el costo de la celda es 1.
- El valor de la celda d(i,j) es el mínimo de:
- La distancia es la celda d(x,y)

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: