La referencia del algoritmo la pueden encontrar en la siguiente ruta
http://en.wikipedia.org/wiki/Levenshtein_distance, es muy ejemplificante y
los links te llevan a algunas modificaciones que existen sobre el mismo algoritmo.
Un poco de teoria:
La distancia de levenshtein permite calcular diferenciala entre 2 cadenas de caracteres, es decir el minimo numero de
operaciones necesarias para que una palabra s se transforme en una palabra t.
La operaciones que necesarias para que esto ocurra son las siguientes:
Td
aba --------->aa eliminacion
Ti
aa ---------->aba inserccion
Ts
aba ---------> ada sustitucion
¿Que es esto? bueno si tienes la palabra:
1. PERRO ---> PERROS : La distancia es 1 por que la diferencia entre perro y perros es 1 que es (s) la operacion es insercción
2. MOTO ----> FOTO : La distancia es 1 por que la diferencia entre MOTO y FOTO es F la operacion es sustitución
1: public int LevenshteinDistance(string s, string t)
2: {3: // d is a table with m+1 rows and n+1 columns
4: int costo = 0;
5: int m = s.Length;
6: int n = t.Length;
7: int[,] d = new int[m + 1, n + 1];
8: 9: // Verifica que exista algo que comparar
10: if (n == 0) return m;
11: if (m == 0) return n;
12: 13: // Llena la primera columna y la primera fila.
14: for (int i = 0; i <= m; d[i, 0] = i++) ;
15: for (int j = 0; j <= n; d[0, j] = j++) ;
16: 17: 18: /// recorre la matriz llenando cada unos de los pesos.
19: /// i columnas, j renglones
20: for (int i = 1; i <= m; i++)
21: {22: // recorre para j
23: for (int j = 1; j <= n; j++)
24: {25: /// si son iguales en posiciones equidistantes el peso es 0
26: /// de lo contrario el peso suma a uno.
27: ///
28: costo = (s[i - 1] == t[j - 1]) ? 0 : 1;29: d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1, //Eliminacion
30: d[i, j - 1] + 1), //Inserccion
31: d[i - 1, j - 1] + costo); //Sustitucion
32: 33: } 34: }35: /// Calculamos el porcentaje de cambios en la palabra.
36: if (s.Length > t.Length)
37: porcentaje = ((double)d[m, n] / (double)s.Length);
38: else
39: porcentaje = ((double)d[m, n] / (double)t.Length);
40: return d[m, n];
41: } 42: 43: double _porcentaje = 0;
44: 45: 