Búscalo aquí:

Distancia de Levenshtein [código]


La distancia de Levenshtein es una herramienta muy potente y aplicada en diferentes correctores ortograficos de editores de texto. La distancia de Levenshtein, que también es conocida como la generalización de la distancia de Hamming, determina la medida de similitud entre dos cadenas de caracteres.



Este algoritmo fue propuesto por Vladimir Levenshtein en 1965 y desde entonces ha sido ampliamente usado para realizar el matching entre cadenas de caracteres con diferente longitud.

La implementación eficiente de éste algoritmo requiere del uso de la programación dinámica puesto que implementa el uso de una matriz de tamaño (n + 1) × (m + 1), donde n y m son las longitudes de los cadenas que se comparan. Su implementación es sencilla y se las presento a continuación.

El código de la distancia de Levenshtein en Java es el siguiente:

  1. package Levenshtein;
  2. /**
  3. *
  4. * @author Jorge Valverde
  5. */
  6. //para calcular la distancia entre dos cadenas
  7. public class DistanciaLevenshtein {
  8. private String texto;
  9. private String patron;
  10. private String TokenMin;
  11. public DistanciaLevenshtein(String texto, String patron)
  12. {
  13. this.texto = texto;
  14. this.patron = patron;
  15. this.TokenMin = "";
  16. }
  17. public int getDistLev(String s, String t)
  18. {
  19. int n = s.length();
  20. int m = t.length();
  21. int[][] d = new int[n + 1][ m + 1];
  22. if (n == 0)
  23. {
  24. return m;
  25. }
  26. if (m == 0)
  27. {
  28. return n;
  29. }
  30. for (int i = 0; i <= n; d[i][0] = i++)
  31. { }
  32. for (int j = 0; j <= m; d[0][j] = j++)
  33. { }
  34. for (int i = 1; i <= n; i++)
  35. {
  36. for (int j = 1; j <= m; j++)
  37. {
  38. int costo;
  39. if(t.charAt(j-1) == s.charAt(i-1))
  40. costo = 0;
  41. else
  42. costo = 1;
  43. d[i][j]=Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),
  44. d[i-1][j-1] + costo);
  45. }
  46. }
  47. return d[n][m];
  48. }
  49. public int getDistanciaMinima()
  50. {
  51. String[] tokens = texto.split(" ");
  52. String cadmin = "";
  53. int distminima = 99999;
  54. for(int i=0; i<tokens.length; i++)
  55. {
  56. //obtenemos la distancia por cada palabra del texto total
  57. int dist = this.getDistLev(tokens[i],patron);
  58. if(dist<distminima)
  59. {
  60. distminima = dist;
  61. cadmin = tokens[i];
  62. }
  63. }
  64. this.TokenMin = cadmin;
  65. return distminima;
  66. }
  67. public String getTokenMin()
  68. {
  69. return this.TokenMin;
  70. }
  71. }

-->

Espero que les sea de utilidad, saludos.


Quieres leer más post como éste???...suscribete aquí!!!




3 comentarios:

  1. Creo que tienes algunos errores en el codigo
    linea 73
    linea 78
    y la declaracion del metodo ya que no le pusiste String

    ResponderEliminar
  2. Hola Francisco, los errores no son de código, sino errores de tags al pasar el código de java a html, pero ya estan corregidos, las disculpas del caso, gracias por leer el blog

    ResponderEliminar
  3. hola amigo me podrias explicar este tema es que la vdd no le entinedo mucho

    ResponderEliminar

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...