Levenshtein Algoritması
Husamettin Elalmis
Last updated
Husamettin Elalmis
Last updated
Levenshtein Algoritması
Merhaba arkadaşlar, bu yazıda sizlere Levenshtein algoritmasından bahsecedeğim.
Levenshtein Algoritması Nedir?
Levenshtein Distance algoritması olarak bilinir
Vladimir Levenshtein tarafından geliştirilmiştir
Kelimelerin birbirleri ile benzerlik oranını hesaplar
Temelinde kaynak ve hedef kelime için, İki boyutlu matris kullanarak uzaklık ölçümü yapar
Karşılaştırılan kelimelerin maliyetinin en küçük olanı "aradığımız kelimeye" yakın olacağı varsayılır
"Bunu mu demek istemiştiniz?" (Did you mean?) algoritmaları bunu kullanır
Algoritmanın Tatbik Edilmesi
Bir web sayfamız olduğunu varsayalım ve arama yaptırdığımızı varsayalım
Kullanıcının girdiği cümleyi bir havuza ekliyoruz (arama yapılanlar havuzu)
Kullanıcının girdiği cümleyi daha önce girilenler havuzunda benzerlik oranını en büyükten küçüğe doğru sıralayarak gösteriyoruz
Böylece, "Bunu mu demek istemiştiniz?" yaklaşım önermelerini listeliyoruz
Program
Program Kodu
using System;
using System.Collections.Generic;
using System.Linq;
namespace StringSimilarityArge
{
class Program
{
static void Main(string[] args)
{
Console.BackgroundColor = ConsoleColor.White;
Console.ForegroundColor = ConsoleColor.Black;
Console.Clear();
// havuzumuzdaki daha önce yapılmış olan aramalar bunlar olsun var list = new List<string>();
list.Add("ARKSOFT Bilişim Hizmetleri");
list.Add("GittiGidiyor Online Satış");
list.Add("HepsiBurada E-Ticaret");
list.Add("N11 E-Ticaret");
list.Add("Kendi E-Ticaret Sitenizi Yapın");
list.Add("Bilişim Hizmetleri Sektörü");
list.Add("Sektörel Piyasalar");
list.Add("Piyasalarda Son Durum");
list.Add("Hava Durumu");
list.Add("Online Satış İşlemleri");
list.Add("Bankacılık ve Denetleme Kurumu");
list.Add("Bağımsız Denetleme Kuruluşu");
list.Add("Bağımsız Yapı Denetim");
list.Add("Arkastra Casantra Problemi");
list.Add("Ark Signature");
list.Add("Finger Print İşlemleri ve Singer Dikiş Makinası");
list.Add("İş Makinaları Sempozyumu");
list.Add("Pazarda Satış İşlemleri");
// kullanıcının girdiği örnek arama kelimeleri var searchList = new string[] { "soft", "arksoft", "soft bilişim", "arksoft bilişim", "arksoft hizmet", "satış", "ark", "makina", "ticaret", "bilişim", "denetim", "yapı", "piyasa", "durum", "online" }; // simule ediyoruz foreach (var search in searchList)
{
Console.WriteLine($"== "{search.ToUpper()}" arama sonuçları (Bunu mu demek istediniz?) ==");
List<Tuple<double, string>> dic = new List<Tuple<double, string>>();
foreach (var item in list)
{
var res = GetBenzerlik(search, item);
dic.Add(Tuple.Create<double, string>(res, item));
}
var resList = dic.Where(x => x.Item1 > 10).OrderByDescending(x => x.Item1).ToList(); foreach (var item in resList)
{
Console.WriteLine($"{search.ToUpper()} => {item.Item2} => {item.Item1}%");
}
Console.WriteLine();
}
Console.WriteLine("ok");
Console.ReadLine();
}
public static int Hesapla(string source, string target)
{
int n = source.Length; int m = target.Length; int[,] d = new int[n + 1, m + 1]; // Adım 1 if (n == 0)
{
return m;
}
if (m == 0)
{
return n;
}
// Adım 2 for (int i = 0; i <= n; d[i, 0] = i++)
{
}
for (int j = 0; j <= m; d[0, j] = j++)
{
}
// Adım 3 for (int i = 1; i <= n; i++)
{
// Adım 4 for (int j = 1; j <= m; j++)
{
// Adım 5 int cost = (target[j - 1] == source[i - 1]) ? 0 : 1; // Adım 6
d[i, j] = Math.Min(Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost);
}
}
// Adım 7 return d[n, m];
}
static double GetBenzerlik(string fullString1, string fullString2)
{
double res = 0; string[] arr1 = fullString1.ToUpper().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); string[] arr2 = fullString2.ToUpper().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); if (arr1.Length < arr2.Length)
{
string[] temp = arr2;
arr2 = arr1;
arr1 = temp;
}
int[,] scores = new int[arr1.Length, arr2.Length]; int[] bestWord = new int[arr1.Length]; for (int i = 0; i < arr1.Length; i++)
{
for (int j = 0; j < arr2.Length; j++) scores[i, j] = 1000;
bestWord[i] = -1;
}
int wordsMatched = 0; for (int i = 0; i < arr1.Length; i++)
{
string s1 = arr1[i]; for (int j = 0; j < arr2.Length; j++)
{
string s2 = arr2[j]; int levenshteinDistance = Hesapla(s1, s2);
scores[i, j] = levenshteinDistance;
if (bestWord[i] == -1 || scores[i, bestWord[i]] > levenshteinDistance) bestWord[i] = j;
}
}
for (int i = 0; i < arr1.Length; i++)
{
if (scores[i, bestWord[i]] == 1000) continue; for (int j = i + 1; j < arr1.Length; j++)
{
if (scores[j, bestWord[j]] == 1000) continue; if (bestWord[i] == bestWord[j])
{
if (scores[i, bestWord[i]] <= scores[j, bestWord[j]])
{
scores[j, bestWord[j]] = 1000;
int curBest = -1; int curScore = 1000; for (int k = 0; k < arr2.Length; k++)
{
if (curBest == -1 || curScore > scores[j, k])
{
curBest = k;
curScore = scores[j, k];
}
}
bestWord[j] = curBest;
}
else
{
scores[i, bestWord[i]] = 1000;
int curBest = -1; int curScore = 1000; for (int k = 0; k < arr2.Length; k++)
{
if (curBest == -1 || curScore > scores[i, k])
{
curBest = k;
curScore = scores[i, k];
}
}
bestWord[i] = curBest;
}
i = -1;
break;
}
}
}
for (int i = 0; i < arr1.Length; i++)
{
if (scores[i, bestWord[i]] == 1000)
{
res += arr1[i].Length;
}
else
{
res += scores[i, bestWord[i]];
if (scores[i, bestWord[i]] == 0) wordsMatched++;
}
}
int len = (fullString1.Replace(" ", "").Length > fullString2.Replace(" ", "").Length) ? fullString1.Replace(" ", "").Length : fullString2.Replace(" ", "").Length; if (res > len) res = len;
res = (1 - (res / len)) * 100;
// virgulden sonra 2 haneye yuvarla return Math.Round(res, 2);
}
}}
Sonuç
Bu dokumanda arama motorlarında kullanılan benzerlik algoritmasını uygulamalı görmüş olduk
Saygılarımla,
Hüsamettin ELALMIŞ – 11.06.2022
husamettin.elalmis@arksoft.com.tr
