Percentage Likeness between strings

[Travis]

Is there a way to determine the percentage likeness two strings share?
So that given an parameter string1 and a list of strings to search, I
could display only those values that are say, a 75% or more match?

 

[Victor Bazarov]

Is there a way to determine the percentage likeness two strings share?

Depending on your definition of "likeness", I am sure there is.

So that given an parameter string1 and a list of strings to search, I
could display only those values that are say, a 75% or more match?

What does that mean for them to be N% match? Please post your algorithm
if you have it, and we'll help you convert to C++. If you don't have
the algorithm, post to comp.programming.

V

 

[ekkehard.horner]

Is there a way to determine the percentage likeness two strings share?
So that given an parameter string1 and a list of strings to search, I
could display only those values that are say, a 75% or more match?

search for "edit distance" and/or "levenshtein"; e.g.

http://en.wikipedia.org/wiki/Levenshtein_distance
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

 

[Travis]

search for "edit distance" and/or "levenshtein"; e.g.

http://en.wikipedia.org/wiki/Levenshtein_distance
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

Good info. Thank you.

 

[Phil Endecott]

Is there a way to determine the percentage likeness two strings share?
So that given an parameter string1 and a list of strings to search, I
could display only those values that are say, a 75% or more match?

If you want a C++ implementation of an edit-distance algorithm, there's
one that I wrote here:

http://svn.chezphil.org/anyterm/trunk/common/diff.cc (and .hh)

It's GPL licensed. But you might find the comments useful, even if you
can't directly use the code.

If you want a fast method for ranking search results for a human, this
may not be what you want. But it will probably point you in the right
direction.


Phil.