C# Levensthein Distance Algoritması

Herkese merhaba, C# yazılarımıza kaldığımız yerden devam ediyoruz. Bu yazımızda Levenstein Distance Algoritması’nı anlatacağım. Hadi başlayalım !

Tanımı

Levenshtein mesafesi, iki string arasındaki en az düzenleme işlemi sayısıdır. Düzenleme işlemleri, bir stringdeki bir karakterin ekleme, çıkarma veya değiştirme işlemleriyle diğer stringdeki karaktere eşleştirilmesi ile gerçekleştirilir.

C# Kodu

C# ile Levenshtein mesafesi hesaplamak için aşağıdaki kod örneği kullanılabilir:

public static int LevenshteinDistance(string s, string t)
{
    int n = s.Length;
    int m = t.Length;
    int[,] d = new int[n + 1, m + 1];

    if (n == 0)
        return m;

    if (m == 0)
        return n;

    for (int i = 0; i <= n; d[i, 0] = i++)
    {
    }

    for (int j = 0; j <= m; d[0, j] = j++)
    {
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;
            d[i, j] = Math.Min(
                Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                d[i - 1, j - 1] + cost);
        }
    }

    return d[n, m];
}

Kod Açıklamaları

Yukarıdaki kodda, Levenshtein mesafesi hesaplamak için bir LevenshteinDistance fonksiyonu tanımlanmıştır. Bu fonksiyon, iki string parametre alır: s ve t. Daha sonra, iki string arasındaki mesafeyi hesaplamak için iki boyutlu bir dizi d oluşturulur.

İlk olarak, n ve m değişkenleri s ve t stringlerinin uzunluğunu alır. Eğer n veya m sıfır ise, fonksiyon ilgili uzunluğu döndürür.

Sonra, for döngüsü kullanarak, dizi d nin ilk satırı ve ilk sütunu sıfırlarla doldurulur.

Daha sonra, bir ikinci for döngüsü kullanılarak, s ve t stringlerinin karakterlerinin karşılaştırılması yapılır. Eğer karakterler aynı ise, cost değişkeni sıfıra atanır. Aksi takdirde, cost değişkeni bir olarak atanır. Daha sonra, mesafe hesaplaması yapılır ve sonuç d[n, m] olarak döndürülür.

Bu örnekte, Math.Min fonksiyonu kullanılarak en düşük maliyetli düzenleme işlemi seçilir. Bu işlem, d[i – 1, j] + 1, d[i, j – 1] + 1 veya d[i – 1, j – 1] + cost olabilir. Bu üç seçenek arasından en düşük maliyetli olanı, d[i, j] hücresine atanır.

Bu algoritma, her karakterin maliyetini bir olarak kabul eder. Farklı karakterlerin farklı maliyetleri olduğu durumlarda, bu algoritma uygulanabilirliği azalabilir. Ancak, çoğu durumda bu algoritma yeterli sonuçlar sağlar.

Kullanımı

Levenshtein mesafesi hesaplama örneği aşağıdaki gibi kullanılabilir:

string s1 = "kitten";
string s2 = "sitting";
int distance = LevenshteinDistance(s1, s2);
Console.WriteLine("Levenshtein Distance: " + distance);

Bu örnekte, s1 ve s2 değişkenleri kitten ve sitting stringlerini içerir. LevenshteinDistance fonksiyonu kullanılarak, distance değişkenine iki string arasındaki mesafe atanır. Son olarak, sonucu yazdırmak için Console.WriteLine fonksiyonu kullanılır.

Sonuç

Bu makalede, C# programlama dilinde Levenshtein mesafesi algoritması hakkında bir örnek sunduk. Bu örnek, iki string arasındaki en az düzenleme işlemi sayısını hesaplar. Bu algoritma, özellikle metin işleme ve doğal dil işleme gibi alanlarda kullanışlıdır.

Evet C# ile Levenstein Distance Algoritması bu şekilde yapılmakta. Tüm C# yazılarımıza buraya tıklayarak ulaşabilirsiniz. Herkese hayırlı günler.