fuzzy string compare in .Net ?

[Tim Mackey]

hi,
when a user reaches a 404 page not found on my web site, i want to give them
one or more 'best guess' links to the page they are looking for (MS do this
on their site...). i have a list of all the available pages to compare the
requested url against.
i've hunted around on google and newsgroups like alt.comp.fuzzy, but i can't
find a nice .NET API that i can just call in my code to give me a closest
match. i would define closest match as the one with the smallest 'edit
distance' to the original, i.e. the one that requires the least amount of
insertions, deletions and edits to match it exactly. i can't see how a
regular expression could help (but i may of course be wrong) since i want to
be quite tolerant of variances in the strings.
if there isn't such an API, i would have the time to implement one, if
someone gave me a few pointers in the right direction. it would want to be
efficient also, because i can easily see an algorithm going into n cubed or
worse here.

thanks for reading this
tim

blog: http://tim.mackey.ie
67d0ebfec70e8db 3

[Gerald Hernandez]

Re: fuzzy string compare in .Net ?

You should try searching for "Levenshtei n" on Google.
This should get you a number of good resources on String Edit Distance
methodologies.
At one point, I came across a great dotNet implementation. However, I cannot
locate it at the moment, but I will keep looking.
While this is not really what you want, it is a good read and has some very
informative and helpful links:

http://www.codeproject.com/string/dmetaphone6.asp

it might also give you some ideas on maybe implementing a less resource
intensive version of what you want.

Gerald

"Tim Mackey" <tim@scootasp.n et> wrote in message
news:314hfuF38g i24U1@individua l.net...[color=blue]
> hi,
> when a user reaches a 404 page not found on my web site, i want to give[/color]
them[color=blue]
> one or more 'best guess' links to the page they are looking for (MS do[/color]
this[color=blue]
> on their site...). i have a list of all the available pages to compare[/color]
the[color=blue]
> requested url against.
> i've hunted around on google and newsgroups like alt.comp.fuzzy, but i[/color]
can't[color=blue]
> find a nice .NET API that i can just call in my code to give me a closest
> match. i would define closest match as the one with the smallest 'edit
> distance' to the original, i.e. the one that requires the least amount of
> insertions, deletions and edits to match it exactly. i can't see how a
> regular expression could help (but i may of course be wrong) since i want[/color]
to[color=blue]
> be quite tolerant of variances in the strings.
> if there isn't such an API, i would have the time to implement one, if
> someone gave me a few pointers in the right direction. it would want to[/color]
be[color=blue]
> efficient also, because i can easily see an algorithm going into n cubed[/color]
or[color=blue]
> worse here.
>
> thanks for reading this
> tim
>
> blog: http://tim.mackey.ie
> 67d0ebfec70e8db 3
>
>[/color]

[Tim Mackey]

Re: fuzzy string compare in .Net ?

hi Gerald
many thanks for the pointer. i've got a working prototype using a c#
levenshtein implementation, which is a good start. i think i need more
flexibility than what it provides though.
for example, i'm searching for a best guess for 'consortium', the results of
EditDistance() are shown below.
result format: <EditDistance > <Compared With>:
6 contact
6 conor ryan
7 motorola
7 joe morris
8 bocse 2004
8 consortium members

it's clear that contact does require fewer character changes to change to
consortium, but the fact that "consortium members" has the exact word match
in it should put it ahead of all the others. i can obviously start catering
for manual cases like this, but it would be buggy and it probably take a
long time to get a generic solution.

i'm very happy with the efficiency of this algorithm, i calculated the edit
distance of a 25 character string with 165 other strings of variable length
in .06 seconds. are there other alternatives that are a little more clever,
without getting into genetic programming?!

many thanks
tim

[Patrice]

Re: fuzzy string compare in .Net ?

You could perhaps take into account the length by dividing the edit distance
by the length to get an "mean edit distance per letter" result.

Patrice

--

"Tim Mackey" <tim@scootasp.n et> a écrit dans le message de
news:315q29F35j bokU1@individua l.net...[color=blue]
> hi Gerald
> many thanks for the pointer. i've got a working prototype using a c#
> levenshtein implementation, which is a good start. i think i need more
> flexibility than what it provides though.
> for example, i'm searching for a best guess for 'consortium', the results[/color]
of[color=blue]
> EditDistance() are shown below.
> result format: <EditDistance > <Compared With>:
> 6 contact
> 6 conor ryan
> 7 motorola
> 7 joe morris
> 8 bocse 2004
> 8 consortium members
>
> it's clear that contact does require fewer character changes to change to
> consortium, but the fact that "consortium members" has the exact word[/color]
match[color=blue]
> in it should put it ahead of all the others. i can obviously start[/color]
catering[color=blue]
> for manual cases like this, but it would be buggy and it probably take a
> long time to get a generic solution.
>
> i'm very happy with the efficiency of this algorithm, i calculated the[/color]
edit[color=blue]
> distance of a 25 character string with 165 other strings of variable[/color]
length[color=blue]
> in .06 seconds. are there other alternatives that are a little more[/color]
clever,[color=blue]
> without getting into genetic programming?!
>
> many thanks
> tim
>
>[/color]

[Tim Mackey]

Re: fuzzy string compare in .Net ?

hi Patrice
i was skeptical to go starting my own extensions to the algorithm, because i
could keep adding special cases till the cows come home, but i did what you
suggested and it works great! for the record, in my situation, a value below
0.60 is quite good. thanks for giving me the tip.
i've included the algorithm here and a sample usage below it to save anyone
looking it up.
many thanks
tim


public class Levenshtein
{
/// <summary>
/// Compute Levenshtein distance.
/// http://www.merriampark.com/ld.htm
/// </summary>
/// <returns>Distan ce between the two strings.
/// The larger the number, the bigger the difference.
/// </returns>
public static int CalcEditDistanc e (string s, string t)
{
int n = s.Length; //length of s
int m = t.Length; //length of t
int[,] d = new int[n + 1, m + 1]; // matrix
int cost; // cost
// Step 1
if(n == 0) return m;
if(m == 0) return n;
// Step 2
for(int i = 0; i <= n; d[i, 0] = i++);
for(int j = 0; j <= m; d[0, j] = j++);
// Step 3
for(int i = 1; i <= n;i++)
{
//Step 4
for(int j = 1; j <= m;j++)
{
// Step 5
cost = (t.Substring(j - 1, 1) == s.Substring(i - 1, 1) ? 0 : 1);
// Step 6
d[i, j] = System.Math.Min (System.Math.Mi n(d[i - 1, j] + 1, d[i, j - 1] +
1),
d[i - 1, j - 1] + cost);
}
}
// Step 7
return d[n, m];
}
}

// sample usage:
double distance = Levenshtein.Cal cEditDistance(s , input);
double meanDistancePer Letter = (distance / s.Length);