Levenshtein Algoritması

Levenshtein Algoritması

İki dizilim arasındaki benzerliği derecelendirmek için kullanılır. Pratikte arama sonuçlarında kelimeler arasındaki benzerliği derecelendirmek için kullanılmaktadır.

Basitçe, iki dizi, iki kelime, iki cümle gibi varlıklar arasındaki değiştirme ve ekleme işlemlerini tutar.

Örneğin;

Oyun- Ayan kelimeleri arasındaki mesafe 2 ‘dir çünkü ilk ve ikinci o harfleri a harfi ile değişmiştir.

Arap – araba kelimeleri arasındaki mesafe 2′dir çünkü p harfi b ile değişmiş ve a harfi eklenmiştir.

Konu ile ilgili detaylı bilgi için  http://en.wikipedia.org/wiki/Levenshtein_distance

Bununla  ilgili ufak bir uygulama gerçekleştirdim. arama yapacağınız kelimeyi, sözlük içersinde aramakta ve yakın olan kelimeleri karşımıza getirmektedir. Kolaylıkla yapıyı dilediğiniz arama motorlarına, kelime eşleştirme, doğru kelime girişini ölçmek için ve benzeri uyarlamalarda kullanabilir, geliştirebilirsiniz.

Örnek kelime kütüphanemiz;

source = new List<string>() {"araba","peugeot","fiat","motor","kaya öner","öner kaya", "volvo","wosvagen","mercedes","bmw","audi","dacia", "hyundai","honda","lada","lotus","alfa romeo", "land rover","renault","volkswagen","tata","nissan","opel","mazda" ,"kia","jeep","jaguar","isuzu","citroen"};

Ana yordamımız;

 public static int FindLevenshteinDistance(this string Source, string Target)
        {
            int n = Source.Length;
            int m = Target.Length;
            int[,] Matrix = new int[n + 1, m + 1]; // Hesaplama matrisi üretilir. 
            if (n == 0) // Eğer kaynak metin yoksa zaten hedef metnin tüm harflerinin değişimi söz konusu olduğundan, hedef metnin uzunluğu kadar bir yakınlık değeri mümkün olabilir 
                return m;

            if (m == 0)   
                return n;

            // Aşağıdaki iki döngü ile yatay ve düşey eksenlerdeki standart 0,1,2,3,4...n elemanları doldurulur 
            for (int i = 0; i <= n; i++)
                Matrix[i, 0] = i;

            for (int j = 0; j <= m; j++)
                Matrix[0, j] = j;

            // Kıyaslama ve derecelendirme operasyonu yapılır 
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                {
                    int cost = (Target[j - 1] == Source[i - 1]) ? 0 : 1;
                    Matrix[i, j] = Math.Min(Math.Min(Matrix[i - 1, j] + 1, Matrix[i, j - 1] + 1), Matrix[i - 1, j - 1] + cost);
                }

            return Matrix[n, m]; // sağ alt taraftaki hücre değeri döndürülür 
        }

Kelimelerin benzerlik durumlarının derecesini ben dinamik olarak kelime uzunluğuna göre ayarlamaktayım. 

Benzerliğin liste olarak döndürülmesi;

public IEnumerable GetSimilarWords(string sourceWord)
        {
            IEnumerable tmp;
            tmp = source.Where(s => sourceWord.FindLevenshteinDistance(s) <= dynamicLimit(s.Length));
            return tmp;
        }

şimdi asıl işlemi yapan, benzerliği hesaplıyan algoritmamıza gelelim. bunun için ufak bir extention yazarak gerçekleştirdim.

   public static int FindLevenshteinDistance(this string Source, string Target)
        {
            int n = Source.Length;
            int m = Target.Length;
            int[,] Matrix = new int[n + 1, m + 1]; // Hesaplama matrisi üretilir.
            if (n == 0) // Eğer kaynak metin yoksa zaten hedef metnin tüm harflerinin değişimi söz konusu                            olduğundan, hedef metnin uzunluğu kadar bir yakınlık değeri mümkün olabilir
                return m; 

            if (m == 0) 
                return n; 

            // Aşağıdaki iki döngü ile yatay ve düşey eksenlerdeki standart 0,1,2,3,4...n elemanları doldurulur
            for (int i = 0; i <= n; i++)
                Matrix[i, 0] = i; 

            for (int j = 0; j <= m; j++)
                Matrix[0, j] = j; 
            // Kıyaslama ve derecelendirme operasyonu yapılır
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                {
                    int cost = (Target[j - 1] == Source[i - 1]) ? 0 : 1;
                    Matrix[i, j] = Math.Min(Math.Min(Matrix[i - 1, j] + 1, Matrix[i, j - 1] + 1), Matrix[i - 1, j - 1] + cost);
                } 
            return Matrix[n, m]; // sağ alt taraftaki hücre değeri döndürülür
        }

Projeyi indirmek için ;  https://docs.google.com/file/d/0ByRFI3ULXVPuRkJNTXBXQjk4LW8/edit?usp=sharing

İyi günler ;)

Öner KAYA