Bolu Beyi tarafından yazıldı Aralık - 18 - 2013 4 Yorum

EkranGoruntusu1Google’ın “Bunu mu demek istediniz?” uygulamasını hepimiz biliriz. Bu uygulamayı yapmak içinde birçok farklı metot mevcuttur. Bu yazımda bu metotlardan biri olan Levenshtein Algoritmasını kısaca anlatarak C++ kodunu sizlerle paylaşacağım.

Levenshtein algoritmasında girdi olarak verilen bir kelime veya kelime öbeği, veritabanında kayıtlı kelimelerle matris üzerinde karşılaştırılması yapılmaktadır. Matrisin ilk satırına(veya sütununa) veritabanındaki kelime yerleştirilirken ilk sütununa(veya satırına) girilen kelime yerleştirilir. Sonrasında sırayla karşılaştırma yapılır. Eğer karakter uyuşuyorsa ve karakter sayısı eşitse sayı sabit kalır, değilse bir artırılarak devam eder. Bu şekilde matrisin sağ en alt köşesindeki rakam bize mesafeyi verir. Mesafe 3(veya farklı bir rakam) veya daha küçük çıkarsa program bize o kelimeyi döndürür ve “Bunu mu demek istediniz: ….” şeklinde karşımıza çıkar. Aşağıdaki örnek resimleri incelerseniz çok daha iyi anlaşılacaktır. Ayrıca buradan da detaylı bilgi edinebilirsiniz: Levenshtein Mesafe Algoritması

Örnek Levenshtein Mesafe Algoritma Şekillleri:

Levenshtein1

Levenshtein2
Levenshtein3

—————————————————-

#include<iostream>
#include<string>
#define MAX 100
int levenshtein(char[],char[],int,int);
int MinimumBul(int,int,int);
static int mesafe;
using namespace std;
int main()
{
static char GirilenKelime[MAX];
char KayitliKelime[MAX];
string Takimlar[5]={“real madrid”, “ac milan”, “manchester united”, “barcelona”, “bayern munih”};
cout << “Takim adi giriniz:\n”;
cout << “\n”;
cin.getline(GirilenKelime,MAX);
cout << “\n”;
for (int i=0; i < MAX; i++)
{
GirilenKelime[i] = tolower(GirilenKelime[i]);
}
for(int i=0;i<5;i++)
{
char *KayitliKelime = (char*)Takimlar[i].c_str();
int mesafe = levenshtein(GirilenKelime, KayitliKelime, ((int)strlen(GirilenKelime)+1), ((int)strlen(KayitliKelime)+1));if((int)strlen(GirilenKelime)<=20 && mesafe<=3)
cout << “Bunu mu demek istediniz?\n\n” << Takimlar[i] << “\n\n”;else if((int)strlen(GirilenKelime)>20 && mesafe <=5)
cout << “Bunu mu demek istediniz?\n” << Takimlar[i] << “\n\n”;
}
}
int levenshtein(char GK[], char KK[], int m, int n)
{
int Matris[MAX][MAX];
for(int i=0;i<m;i++)
Matris[i][0]=i;
for(int i=0;i<n;i++)
Matris[0][i]=i;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(GK[i-1]==KK[j-1])
{
Matris[i][j]=Matris[i-1][j-1];
mesafe=Matris[i][j];
}
else
{
Matris[i][j]=MinimumBul(Matris[i-1][j]+1, Matris[i][j-1]+1, Matris[i-1][j-1]+1);
mesafe=Matris[i][j];
}
}
}
return mesafe;
}
int MinimumBul(int a, int b, int c)
{
int minimum=a;
if(b<=minimum)
minimum=b;
if(c<=minimum)
minimum=c;
return minimum;
}

Bugüne kadar 4 yorum yapıldı

  1. Şeref dedi ki:

    Bolubeyi hocam, çok faydalı bir paylaşım. Emeğinize sağlık Bolubeyi hocam.

  2. Şeref dedi ki:

    Olur mu kardeşim, en az benimkiler kadar değerli yayınların. Adamın dibisin. 😀


Time limit is exhausted. Please reload CAPTCHA.