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
Counting sort veri kümesinde (sayılardan oluşuyor) yer alan elemanların aralığını kullanarak sıralama yapan vir sıralama algoritmasıdır. 1954 yılında Harold H. Seward tarafından yarılmıştır. Counting sort çalışması sırasında giren dizi haricinde 2 tane boş dizi yaratır. A: Sıralanacak elemanların bulunduğu dizi B: Sıralanmış dizi C: A dizisindeki tekrarlanan eleman sayısını tutan dizi   Algoritmanın uygulanışı şu şekildedir: A dizisindeki elemanlar tek tek dolaşılarak B dizisi doldurulur. Mesela; A dizinde 1 elemanında 2 tane bulunmaktadır, 2 elamanından hiç yoktur. C dizisi, en soldaki birimden başlayarak n = n + (n-1) şeklinde artırılacak şekilde yeniden oluşturulur. Bu adımda A dizisinin elemanları sondan başlayarak taranmaya başlanır. Her elemanın içeriği kontrol edilerek C dizisindeki karşılığı bulunur. Bu karşılık A dizinden aldığımız elemanı B dizisinin hangi gözüne yazmamız gerektiğini gösteriyor.   İşlem sonucunda B dizimiz şu şekilde oluşmuştur:     Örnek C kodu: void counting_sort(int *array, int size) { int i, min, max; min = max = array[0]; for(i = 1; i < size; i++) { if (array[i] < min) min = array[i]; else if (array[i] > max) max = array[i]; } int range = max - min + 1; int *count = (int *) malloc(range * sizeof(int)); for(i = 0; i < range; i++) count[i] = 0; for(i = 0; i < size; i++) count[ array[i] - min ]++; int j, z = 0; for(i = min; i <= max; i++) for(j = 0; j < count[ i - min ]; j++) array[z++] = i; free(count); } .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; } Örnek C++ kodu: #include <iostream> #include <vector> using namespace std; void countingSort(vector<int>& Array) { int Min, Max; Min = Max = Array[0]; for(int i = 1; i < Array.size(); i ++) { if(Array[i] < Min) Min = Array[i]; if(Array[i] > Max) Max = Array[i]; } int Range = Max - Min + 1; vector<int> Count; Count.resize(Range); for(int i = 0; i < Range; i ++) Count[i] = 0; for(int i = 0; i < Array.size(); i ++) Count[Array[i] - Min] ++; int Index = 0; for(int i = Min; i <= Max; i ++) for(int j = 0; j < Count[i - Min]; j ++) Array[Index ++] = i; } .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; } Kaynak: en.wikipedia.org net.pku.edu.cn Tags: , | Categories: C | C++ | Algoritma