Levenshtein distance also known as edit distance is a measure of similiarity
/// between two strings where the distance is measured as the number of character
/// deletions, insertions or substitutions required to transform one string to
/// the other string.
/// This method takes in four parameters; two strings and their respective
/// lengths to compute the Levenshtein distance between the two strings.
/// The result is returned as an integer.
///
private int EditDistance(System.String s, System.String t, int n, int m)
{
if (e.Length <= n || e[0].Length <= m)
{
int[][] tmpArray = new int[System.Math.Max(e.Length, n + 1)][];
for (int i = 0; i < System.Math.Max(e.Length, n + 1); i++)
{
tmpArray[i] = new int[System.Math.Max(e[0].Length, m + 1)];
}
e = tmpArray;
}
int[][] d = e; // matrix
int i2; // iterates through s
int j; // iterates through t
char s_i; // ith character of s
if (n == 0)
return m;
if (m == 0)
return n;
// init matrix d
for (i2 = 0; i2 <= n; i2++)
d[i2][0] = i2;
for (j = 0; j <= m; j++)
d[0][j] = j;
// start computing edit distance
for (i2 = 1; i2 <= n; i2++)
{
s_i = s[i2 - 1];
for (j = 1; j <= m; j++)
{
if (s_i != t[j - 1])
d[i2][j] = Min(d[i2 - 1][j], d[i2][j - 1], d[i2 - 1][j - 1]) + 1;
else
d[i2][j] = Min(d[i2 - 1][j] + 1, d[i2][j - 1] + 1, d[i2 - 1][j - 1]);
}
}
// we got the result!
return d[n][m];
}
public override void Close()
{
base.Close();
searchTerm = null;
field = null;
text = null;
}
}
}