Levenshteinova razdalja/Implementacija (Java)

Iz MaFiRaWiki

  1. public class RazdaljaMedNizi{
  2. // Minimum treh vrednosti za izracun minimalnega števila operacij,
  3. // ki jih potrebujemo za preoblikovanje enaga niza v drugega.
  4. private static int minimum (int x, int y, int z) {
  5. int mi;
  6. mi = x;
  7. if (y < mi){
  8. mi = y;
  9. }
  10. if (z < mi){
  11. mi = z;
  12. }
  13. return mi;
  14. }
  15. // Razdalja med nizi
  16. public static int razdalja (String s, String t) {
  17. int d[][]; // matrika d
  18. int n; // dolzina niza s
  19. int m; // dolzina niza t
  20. int i; // i tece po s
  21. int j; // j tece po t
  22. char s_i; // i-ti znak niza s
  23. char t_j; // j-ti znak niza t
  24. int cost;
  25. n = s.length();
  26. m = t.length();
  27. // ce je n enak 0, vrne dolzino niza t,
  28. if (n == 0){
  29. return m;
  30. }
  31. //ce je m enak 0, vrne dolzino niza s
  32. else if (m == 0){
  33. return n;
  34. }
  35. d = new int[n+1][m+1];
  36. // za vsak i enak 0 in i manjsi ali enak n,
  37. // se i v vrstici matrike povecuje za 1.
  38. for (i = 0; i <= n; i++){
  39. d[i][0] = i;
  40. }
  41. // za vsak j enak 0 in j manjsi ali enak m,
  42. // se j v stolpcu matrike povecuje za 1.
  43. for (j = 0; j <= m; j++){
  44. d[0][j] = j;
  45. }
  46. // za vsak i enak 1 in i manjsi ali enak n,
  47. // i-ti znak niza s postane (i-prvi) znak niza s.
  48. for (i = 1; i <= n; i++){
  49. s_i = s.charAt(i - 1);
  50. // za vsak j enak 1 in j manjsi ali enak m,
  51. // j-ti znak niza t postane (j-prvi) znak niza t.
  52. for (j = 1; j <= m; j++) {
  53. t_j = t.charAt (j - 1);
  54. // ce sta i-ti znak niza s in j-ti znak niza t
  55. // enaka, razdalja dobi vrednost 0,
  56. if (s_i == t_j) {
  57. cost = 0;
  58. }
  59. // drugace dobi razdalja vrednost 1.
  60. else {
  61. cost = 1;
  62. }
  63. // izracun razdalje med nizoma
  64. d[i][j] = minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
  65. }
  66. }
  67. // vrne matriko d
  68. return d[n][m];
  69. }
  70. //test
  71. public static void main(String[] args){
  72. String s = "torba";
  73. String t = "borba";
  74. System.out.println("Razdalja med nizoma je: " + razdalja(s,t));
  75. String p = "Mojca";
  76. String r = "Matija";
  77. System.out.println("Razdalja med nizoma je: " + razdalja(p,r));
  78. }
  79. }
Osebna orodja