martes, marzo 17, 2009

Implementando algoritmo de la distancia de Levenshtein en C#

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: