CSharp_ LevenshteinDistance_distance_ MeasureOfSimilarityBetweenTwoStrings.cs

CSharp_ LevenshteinDistance_distance_ MeasureOfSimilarityBetweenTwoStrings.cs

//Inspired By: http://www.dotnetperls.com/levenshtein
void Main()
{
	Console.Write(string.Format("distance(aunt,aunt): {0} \n",LevenshteinDistance.Compute("aunt", "ant"))); 
	Console.Write(string.Format("distance(Sam,Samantha): {0} \n",LevenshteinDistance.Compute("Sam", "Samantha"))); 
	Console.Write(string.Format("distance(flomax,volmax): {0} \n",LevenshteinDistance.Compute("flomax", "volmax"))); 
	//Out:
	//distance(aunt,aunt): 1 
	//distance(Sam,Samantha): 5 
	//distance(flomax,volmax): 3 
}

static class LevenshteinDistance
{
    /// <summary>
    /// Compute the distance between two strings.
    /// </summary>
    public static int Compute(string s, string t)
    {
	int n = s.Length;
	int m = t.Length;
	int[,] d = new int[n + 1, m + 1];

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

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

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

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

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

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