Código de Visual CSharp .NET - Agoritmo de Distancia de Levenshtein

Imágen de perfil
Val: 12
Ha mantenido su posición en Visual CSharp .NET (en relación al último mes)
Gráfica de Visual CSharp .NET

Agoritmo de Distancia de Levenshteingráfica de visualizaciones


Visual CSharp .NET

estrellaestrellaestrellaestrellaestrella(1)
Publicado el 7 de Diciembre del 2016 por Gustavo
1.645 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:

pic1
pic2
pic3

Requerimientos

Visual Studio 2015
FrameWork 4.5

1.0
estrellaestrellaestrellaestrellaestrella(1)

Actualizado el 21 de Diciembre del 2016 (Publicado el 7 de Diciembre del 2016)gráfica de visualizaciones de la versión: 1.0
1.646 visualizaciones desde el 7 de Diciembre del 2016
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private int Levenshtein(string s1, string s2)
{
    int coste = 0;
    int n1 = s1.Length;
    int n2 = s2.Length;
    int[,] m = new int[n1 + 1, n2 + 1];
 
    for (int i = 0; i <= n1; i++)
    {
        m[i, 0] = i;
    }
    for (int i = 1; i <= n2; i++)
    {
        m[0, i] = i;
    }
    for (int i1 = 1; i1 <= n1; i1++)
    {
        for (int i2 = 1; i2 <= n2; i2++)
        {
            coste = (s1[i1 - 1] == s2[i2 - 1]) ? 0 : 1;
            m[i1, i2] = Math.Min(
              Math.Min(
                m[i1 - 1, i2] + 1,
                m[i1, i2 - 1] + 1
              ),
              m[i1 - 1, i2 - 1] + coste
            );
        }
    }
    return m[n1, n2];
}
  • Archivos para descargar

Si alguno de los archivos de descarga no funciona, comentanos aquí el error.




Comentarios sobre la versión: 1.0 (1)

Imágen de perfil
9 de Diciembre del 2016
estrellaestrellaestrellaestrellaestrella
Interesante aporte, no había escuchado de que alguien desarrollase una solución así nunca para ese problema.
Responder

Comentar la versión: 1.0

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad

http://lwp-l.com/s3799