c# Levenshtein Algoritması

Bu Makalamizde pek bilinmeyen fakat inanılmaz işe yarayan Levenshtein Algoritmasının mantığını ve kullanımını öğreneceğiz.

Google,de arama yaparken yazdığımız yazı eksik ya da yanlış olduğunda bize doğru halini bunumu demek istediniz yazarak gösterir.

genel olarak Levenshtein bu işimize yarıyor.

Resimdenden anladığımız gibi yazdığımız yazıya en yakın metni tahmin olarak karşımıza çıkarıyor.

şöyle bir parantez içi bilgi de vermek gerekirse , google bizim yazdığımız yazıya göre değil kendi tahminine uygun sayfaları karşımıza çıkartıyor.

Levenshtein | Distance, iki metin ya da cümlecik arasında karşılaştırma da yapar. bu karşılaştırma bana profesyonel gelmediği için kendim bir algoritma yazdım. ilerleyen zamanlarda sizinle paylaşacağım.

bana profesyonel gelmemesinin sebebi ise matris olayı ile karşılaştırma yapması.

geleceğin mumyalaması muhendisarsivi.com 

mumyalama ile ilgili mühendislik

bu iki kelime birbirinin yanından bile geçmemesine rağmen Levenshtein %60’a yakın benzerlik tespit eder. sebebiyse matris!

Arama mantığı yukaridaki şekilde.

using System;
 
namespace UsingLevenshtein 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            TestMethod("rest", "test"); 
            TestMethod("google", "yahoo!"); 
            TestMethod("mike", "mayk"); 
            TestMethod("samantha", "sam"); 
            TestMethod("puzzle", "pzzel"); 
        }
 
        private static void TestMethod(string Source,string Target) 
        { 
            int[,] matrix3 = new int[Source.Length, Target.Length]; 
            int distance3 = Source.FindLevenshteinDistance(Target, out matrix3); 
            Console.WriteLine("{0} vs {1}\nDistance : {2}\n",Source,Target, distance3); 
            WriteToConsole(matrix3); 
        } 
        static void WriteToConsole(int[,] Matrix) 
        { 
            for (int i = 0; i < Matrix.GetLength(0); i++) 
            { 
                for (int j = 0; j < Matrix.GetLength(1); j++) 
                { 
                    Console.Write("\t{0}  ", Matrix[i, j]); 
                } 
                Console.WriteLine(); 
            } 
            Console.WriteLine(); 
        } 
    }
 
    public static class StringExtensions 
    { 
        // Genişletme metodu, karşılaştırma matrisini de out parametresi olarak döndürmektedir. 
        public static int FindLevenshteinDistance(this string Source, string Target,out int[,] Matrix) 
        { 
            int n = Source.Length; 
            int m = Target.Length;
 
            Matrix = new int[n + 1, m + 1]; // Hesaplama matrisi üretilir. 2 boyutlu matrisin boyut uzunlukları ise kaynak ve hedef metinlerin karakter uzunluklarına göre set edilir
 
            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) // Yukarıdaki durum hedefin karakter içermemesi halinde de geçerlidir 
                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 
        }        
    } 
}

ekran resmi

bu makalemiz bukadar. takıldığınız bir yer olur yada ayrıntılı bilgi isterseniz info@muhendisarsivi.com’a mail atabilir yada gönderinin altına yorum yapabilirsiniz.

iyi çalışmalar..