String Comparison Threshholds

[Travis]

I understand its possible to locate substrings within a string (http://
www.cplusplus.com/reference/string/string/find.html) but is it
possible to compare two strings for a particular threshold of
similarity. Like saying return true if string1 and string2 are say,
80% alike?

 

[Hans Mull]

I understand its possible to locate substrings within a string (http://
www.cplusplus.com/reference/string/string/find.html) but is it
possible to compare two strings for a particular threshold of
similarity. Like saying return true if string1 and string2 are say,
80% alike?

I don't think STL can do this, but there are many libraries with such
algorithms.

Best regards

 

[Travis]

Travis schrieb:> I understand its possible to locate substrings within a string (http://

I don't think STL can do this, but there are many libraries with such
algorithms.

Best regards

I figured there might be I was just trying to get some
recommendations. I know I have boost installed but can't seem to find
the functions to fit.

Thanks for the info.

 

[Juha Nieminen]

is it possible to compare two strings for a particular threshold of
similarity. Like saying return true if string1 and string2 are say,
80% alike?

Of course it's *possible*. However, if what you wanted to ask is
whether there exists a standard library function to do that, then the
answer is no. If you want such a function you'll have to write it
yourself (or find a third-party library which has such a function).

 

[AnonMail2005]

I understand its possible to locate substrings within a string (http://www..cplusplus.com/reference/string/string/find.html) but is it
possible to compare two strings for a particular threshold of
similarity. Like saying return true if string1 and string2 are say,
80% alike?

Check out the definition of Levenshtein distance:
http://en.wikipedia.org/wiki/Levenshtein_distance

The article has many good pointers to other definitons
of distance or likeness.

You can find an implementation on google by searching
for the above along with the term C++.

HTH

 

[Phil Endecott]

I understand its possible to locate substrings within a string (http://
www.cplusplus.com/reference/string/string/find.html) but is it
possible to compare two strings for a particular threshold of
similarity. Like saying return true if string1 and string2 are say,
80% alike?

Maybe "edit distance" is the thing you need to search for?

My own (GPL) implementation is here:

https://svn.chezphil.org/anyterm/trunk/common/diff.cc

If you search for "edit distance" in the Boost mailing list archive I
think you'll find at least one implementation proposed. (IIRC, I
complained that it was not optimal; the author them presented a much
better version.)


Phil.