Skip to content

Instantly share code, notes, and snippets.

@wickedshimmy
Created June 23, 2010 07:05
Show Gist options
  • Save wickedshimmy/449595 to your computer and use it in GitHub Desktop.
Save wickedshimmy/449595 to your computer and use it in GitHub Desktop.
Damerau-Levenshtein algorithm in C#.
// 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 ("", ""));
}
}
@jspinella
Copy link

On line 14, int should be if!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment