Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Damerau-Levenshtein algorithm in C#.
public static int EditDistance (string original, string modified)
{
int len_orig = original.Length;
int len_diff = modified.Length;
var matrix = new int[len_orig + 1, len_diff + 1];
for (int i = 0; i <= len_orig; i++)
matrix[i,0] = i;
for (int j = 0; j <= len_diff; j++)
matrix[0,j] = j;
for (int i = 1; i <= len_orig; i++) {
for (int j = 1; j <= len_diff; j++) {
int cost = modified[j - 1] == original[i - 1] ? 0 : 1;
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];
}
@jfroom

This comment has been minimized.

Copy link

commented Jun 13, 2012

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

@wickedshimmy

This comment has been minimized.

Copy link
Owner Author

commented Jun 13, 2012

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

@hrzafer

This comment has been minimized.

Copy link

commented Feb 13, 2014

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?

@AnimeshShaw

This comment has been minimized.

Copy link

commented May 20, 2014

@hrzafer Yes you're right about the code

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.