Damerau-Levenshtein algorithm in C#.

Levenshtein.cs

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;
		int (len_orig == 0 || len_diff == 0)
			return len_orig == 0 ? len_diff : 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 ("", ""));
	}
}

Hello, under what licence is this code released? Thanks!

Hey - I've fixed a typo and added a license file above. I don't remember what I originally wrote this for so long ago, but feel free to use it under the terms of MIT/X11.

Cheers,
Matt

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!