Levenshtein Mesafesi ile bulanık arama (fuzzy search)


14 Haziran 2012     Etiketler: C# Levenshtein-Mesafesi

Uygulamalarımızda imla hatalarına ve/veya ç-ı-ğ-ö-ş-ü gibi karakterlerin c-i-g-o-s-u şeklinde girilmesine rağmen aramaların doğru sonuçları vermesini sağlamak mümkün.


Rus bilimadamı Vladimir Levenshtein tarafından yazılan bu algoritma yardımıyla bulanık arama işlevi sağlamamız mümkün. Bunu aşağıdaki C# sınıfı yardımıyla gerçekleşirebiliriz. Bu sınıf bize iki metini bir örnek yapabilmek için gerekli kaç adet düzeltme gerekir bunu döndürecektir.


    public static class LevenshteinMesafesi
{
///
/// s ve t metinleri arasındaki mesafeyi hesapla.
///

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

// ADIM 1
if (n == 0)
{
return m;
}

if (m == 0)
{
return n;
}

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

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

// ADIM 3
for (int i = 1; i <= n; i++)
{
//ADIM 4
for (int j = 1; j <= m; j++)
{
// ADIM 5
int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

// ADIM 6
d[i, j] = Math.Min(
Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
d[i - 1, j - 1] + cost);
}
}
// ADIM 7
return d[n, m];
}
}


Şimdi bu statik sınıfı değişik senaryolarda nasıl kullanabiliriz bunu irdeleyelim.
LevenshteinMesafesi.Hesapla("eskişehir", "eskisehir"); //1 döndürür: s-ş düzeltmesi 
LevenshteinMesafesi.Hesapla("eskişehir", "eskşehir"); //1 döndürür: kş-kiş düzeltmesi
LevenshteinMesafesi.Hesapla("eskişehir", "eskşehi"); //2 döndürür: kş-kiş ve r düzeltmesi

Peki, arama işlevinin bir parçası olarak LevenshteinMesafesi sınıfını nasıl kullanabiliriz? Bunin için aşağıdaki Firma sınıfını örnek olarak tanımlayalaim.

public class Firma
{
public string Ad { get; set; }
public string Adres { get; set; }
}

Ve elimizde Firma'lardan oluşan bir List olsun:

List listeFirma = new List
{
new Firma {Ad = "Firma 1 Ltd.", Adres = "Abc Sitesi, Eskişehir"},
new Firma {Ad = "Firma 2 Ltd.", Adres = "Eskişehir Yolu, Ankara"},
new Firma {Ad = "Firma 3 Ltd.", Adres = "Sultanahmet, İstanbul"}
};

Şimdi listeFirma içinde Adres alanında "Eskisehir" metni geçen firmaları bulalım. ("Eskisehir" özellikle yanlış yazılmıştır)

string arananMetin = "Eskisehir";
var bulunanFirmalar = listeFirma.FindAll(f =>f.Adres.Contains(arananMetin));

arananMetin değişkeninde yapılan imla hatasından dolayı bu arama bize hiçbir sonuç döndürmeyecektir. Yukarıdaki kod parçasını şimdi LevenshteinMesafesi'yle yeniden yazalım.

string arananMetin = "Eskisehir";
var bulunanFirmalar = listeFirma.FindAll(f => f.Adres.Split(' ').Count(kelime=>LevenshteinMesafesi.Hesapla(kelime, arananMetin) < 2) > 0);

Burada yapılan işlemi biraz açalım. listeFirma üzerinde FindAll metodu ve f=> lambda ifadesi ile listeFirma içindeki Firma'ların Adres alanını boşluk karakteriyle ayırıp, ortaya çıkan kelimeler dizisinin içinde arananMetin ile Levenshtein Mesafesi 2'den az olan Firma'ları seçiyoruz.

Bu kod bize listeFirma'sindaki ilk iki Firma'yi verecektir. "Eskisehir" ifadesi yanlış yazıldığı halde, arama başarıyla yapılacakir.




Yorumlar


Levenshtein'i bilmiyordum.İşe yarar bir makale.Tşk.
Eralp @ 26.6.2012 10:53:07

Sizin yorumunuz

Email


Adınız







F5 Dergi © 2017