Paylaşım Noktası

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

C, JAVA, Algoritma Levenshtein; distance

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:

1. 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.
   
2. C dizisi, en soldaki birimden başlayarak n = n + (n-1) şeklinde artırılacak şekilde yeniden oluşturulur.
   
3. 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);
}

Ö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;
}

Kaynak:
en.wikipedia.org
net.pku.edu.cn

C, C++, Algoritma sıralama algoritmalaları, counting