Created
June 23, 2010 07:05
-
-
Save wickedshimmy/449595 to your computer and use it in GitHub Desktop.
Damerau-Levenshtein algorithm in C#.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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]; | |
} |
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
!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hello, under what licence is this code released? Thanks!