Damerau-Levenshtein algorithm in C#.

Levenshtein.cs

// Copyright (c) 2010, 2012 Matt Enright

// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

using System;
using System.Linq;

using NUnit.Framework;

[TestFixture]
public class Levenshtein {
	public static int EditDistance (string original, string modified)
	{
		if (original == modified)
			return 0;

		int len_orig = original.Length;
		int len_diff = modified.Length;

		if (len_orig == 0)
			return len_diff;

		if (len_diff == 0)
			return len_orig;

		var matrix = new int[len_orig + 1, len_diff + 1];

		for (int i = 1; i <= len_orig; i++) {
			matrix[i, 0] = i;
			for (int j = 1; j <= len_diff; j++) {
				int cost = modified[j - 1] == original[i - 1] ? 0 : 1;
				if (i == 1)
					matrix[0, j] = j;

				var vals = new int[] {
					matrix[i - 1, j] + 1,
					matrix[i, j - 1] + 1,
					matrix[i - 1, j - 1] + cost
				};
				matrix[i,j] = vals.Min ();
				if (i > 1 && j > 1 && original[i - 1] == modified[j - 2] && original[i - 2] == modified[j - 1])
					matrix[i,j] = Math.Min (matrix[i,j], matrix[i - 2, j - 2] + cost);
			}
		}
		return matrix[len_orig, len_diff];
	}

	[Test]
	public void EqualStringsNoEdits ()
	{
		Assert.AreEqual (0, EditDistance ("test", "test"));
	}

	[Test]
	public void Additions ()
	{
		Assert.AreEqual (1, EditDistance ("test", "tests"));
		Assert.AreEqual (1, EditDistance ("test", "stest"));
		Assert.AreEqual (2, EditDistance ("test", "mytest"));
		Assert.AreEqual (7, EditDistance ("test", "mycrazytest"));
	}

	[Test]
	public void AdditionsPrependAndAppend ()
	{
		Assert.AreEqual (9, EditDistance ("test", "mytestiscrazy"));
	}

	[Test]
	public void AdditionOfRepeatedCharacters ()
	{
		Assert.AreEqual (1, EditDistance ("test", "teest"));
	}

	[Test]
	public void Deletion ()
	{
		Assert.AreEqual (1, EditDistance ("test", "tst"));
	}

	[Test]
	public void Transposition ()
	{
		Assert.AreEqual (1, EditDistance ("test", "tset"));
	}

	[Test]
	public void AdditionWithTransposition ()
	{
		Assert.AreEqual (2, EditDistance ("test", "tsets"));
	}

	[Test]
	public void TranspositionOfRepeatedCharacters ()
	{
		Assert.AreEqual (1, EditDistance ("banana", "banaan"));
		Assert.AreEqual (1, EditDistance ("banana", "abnana"));
		Assert.AreEqual (2, EditDistance ("banana", "baanaa"));
	}

	[Test]
	public void EmptyStringsNoEdits ()
	{
		Assert.AreEqual (0, EditDistance ("", ""));
	}
}

I gues the line

if (i > 1 && j > 1 && original[i - 1] == modified[j - 2] && original[i - 2] == modified[j - 1])
    matrix[i,j] = Math.Min (matrix[i,j], matrix[i - 2, j - 2] + cost);

makes it Damareu-Levenshtein but not Levenshtein. Am I right?

@hrzafer Yes you're right about the code

Thanks!!!

On line 14, int should be if!