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

@jfroom jfroom commented Jun 13, 2012

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

@wickedshimmy

This comment has been minimized.

Copy link
Owner Author

@wickedshimmy wickedshimmy 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

@hrzafer hrzafer 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

@AnimeshShaw AnimeshShaw commented May 20, 2014

@hrzafer Yes you're right about the code

@BlackForest2417

This comment has been minimized.

Copy link

@BlackForest2417 BlackForest2417 commented Apr 1, 2016

Thanks!!!

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