Algoritmo Distancia Hamming Levenshtein en C#

El algoritmo Distancia de Hamming compara uno por uno los caracteres para ver cambios de uno con respecto al otro.

El algoritmo de Distancia de Levenshtein calcula numero de operaciones para convertir una cadena a otra.


Distancia de Hamming en C#
public static int HammingDistance(String s1, String s2)
        {
            int counter = 0;
            for (int k = 0; k < s1.Length; k++)
            {
                if (s1.ElementAt(k) == s2.ElementAt(k)) counter++;
            }
            return counter;
        }

Distancia de Levenshtein en C#
static int LevenshteinDistance(string s, string t, out double porcentaje)
        {
            porcentaje = 0;

            // d es una tabla con m+1 renglones y n+1 columnas
            int costo = 0;
            int m = s.Length;
            int n = t.Length;
            int[,] d = new int[m + 1, n + 1];

            // Verifica que exista algo que comparar
            if (n == 0) return m;
            if (m == 0) return n;

            // Llena la primera columna y la primera fila.
            for (int i = 0; i <= m; d[i, 0] = i++) ;
            for (int j = 0; j <= n; d[0, j] = j++) ;

            /// recorre la matriz llenando cada unos de los pesos.
            /// i columnas, j renglones
            for (int i = 1; i <= m; i++)
            {
                // recorre para j
                for (int j = 1; j <= n; j++)
                {
                    /// si son iguales en posiciones equidistantes el peso es 0
                    /// de lo contrario el peso suma a uno.
                    costo = (s[i - 1] == t[j - 1]) ? 0 : 1;
                    d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1,  //Eliminacion
                        d[i, j - 1] + 1),  //Inserccion 
                        d[i - 1, j - 1] + costo);  //Sustitucion
                }
            }
            /// Calculamos el porcentaje de cambios en la palabra.
            if (s.Length > t.Length)
                porcentaje = ((double)d[m, n] / (double)s.Length);
            else
                porcentaje = ((double)d[m, n] / (double)t.Length);
            return d[m, n];
        }

Comentarios

Publicar un comentario

Entradas populares de este blog

Instalar programa como servicio Windows

Ejecutar programa como servicio windows server 2008

Habilitar Ping Firewall Windows 2008