Levenshtein uzaklığı 2 karakter katarı arasında tanımlanmış, bir katardan diğer katara dönüşümde minimum değişim sayısını verir. dönüşüm işlemlerinde ekleme, silme ve katar içinde karakter değişimleri kabul edilmektedir. Aynı zamanda “değişim uzaklığı (edit distance)” olarak da bilinmektedir. Örn: levenstein_distance(samantha,Sam) = 5 Pseudo kodu int LevenshteinDistance(char s[1..m], char t[1..n]) { declare int d[0..m, 0..n] for i from 0 to m d[i, 0] := i for j from 0 to n d[0, j] := j for j from 1 to n { for i from 1 to m { if s[i] = t[j] then d[i, j] := d[i-1, j-1] else d[i, j] := minimum ( d[i-1, j] + 1, // deletion d[i, j-1] + 1, // insertion d[i-1, j-1] + 1 // substitution ) } } return d[m,n] }       C Kodu: #include <stdlib.h> #include <malloc.h> #include <string.h> int levenshtein_distance(char *s,char*t); int minimum(int a,int b,int c); int levenshtein_distance(char *s,char*t) { int k, i, j, n, m, cost, *d, distance; n = strlen(s); m = strlen(t); if(n!=0 && m!=0) { d = malloc((sizeof(int))*(m+1)*(n+1)); m++; n++; for(k=0;k<n;k++) d[k]=k; for(k=0;k<m;k++) d[k*n]=k; for(i=1;i<n;i++) for(j=1;j<m;j++) { if(s[i-1]==t[j-1]) cost=0; else cost=1; d[j*n+i]=minimum(d[(j-1)*n+i]+1,d[j*n+i-1]+1,d[(j-1)*n+i-1]+cost); } distance=d[n*m-1]; free(d); return distance; } else return -1; } int minimum(int a,int b,int c) { int min=a; if(b<min) min=b; if(c<min) min=c; return min; }   Java Kodu: public static int getLevenshteinDistance (String s, String t) { if (s == null || t == null) { throw new IllegalArgumentException("Strings must not be null"); } int n = s.length(); int m = t.length(); if (n == 0) { return m; } else if (m == 0) { return n; } int p[] = new int[n+1]; int d[] = new int[n+1]; int _d[]; int i; int j; char t_j; int cost; for (i = 0; i<=n; i++) { p[i] = i; } for (j = 1; j<=m; j++) { t_j = t.charAt(j-1); d[0] = j; for (i=1; i<=n; i++) { cost = s.charAt(i-1)==t_j ? 0 : 1; d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost); } _d = p; p = d; d = _d; } return p[n]; }   Kaynaklar: http://www.merriampark.com/ldc.htm http://www.merriampark.com/ldjava.htm .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } tweetmeme_source = 'makcura'; tweetmeme_service = 'bit.ly'; Tags: | Categories: C | JAVA | Algoritma