C# LevenshteinDistance Problems

Posted: October 9, 2014 in Algorithms, C#
Tags: , ,

Dinamik programlama olan bu algoritma , iki string ifadenin karşılıklı dönüşümlerini yapmak için gerekli işlem sayısının belirlenmesi.Bu algoritma ses tanımada,DNA analizinde,bir eserin çalıntı olup olmadığını algılanmasında kullanılabilir.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication10
{
static class LevenshteinDistance
{

public static int Compute(string s, string t)
{
int x = s.Length;
int y = t.Length;
int[,] d = new int[x + 1, y+ 1];

if (x == 0)
{
return y;
}

if (y== 0)
{
return x;
}

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

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

for (int i = 1; i <= x; i++)
{

for (int j = 1; j <= y; 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[x, y];
}
}

class Program
{
static void Main(string[] args)
{

Console.WriteLine("Compute the distance between two strings:");
Console.WriteLine("——————————————");
Console.WriteLine("aysu and aynur");
Console.WriteLine(LevenshteinDistance.Compute("aysu", "aynur"));

Console.WriteLine("——————————————");
Console.WriteLine("eker and eken");
Console.WriteLine(LevenshteinDistance.Compute("eker", "eken"));
Console.ReadLine();
}
}
}

Ekran çıktısı :

19

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s