String matching algorithm

Question

Say I have 3 strings. And then 1 more string.
Is there an algorithm that would allow me to find which one of the first 3 strings matches the 4th string the most?
None of the strings are going to be exact matches, I'm just trying to find the closest match.
And if the algorithm already exists in STL, that would be nice.

Thanks in advance.

You might take a look at the "string similarity measures" category of Wikipedia articles and see which of them is closest to what you have in mind. — ruakh
– ruakh, Commented Jan 13, 2012 at 16:28

NPE · Accepted Answer · 2012-01-13 16:27:38Z

8

You don't specify what exactly you mean by "matches the most", so I assume you don't have precise requirements. In that case, Levenshtein distance in a reasonable metric. Simply compute the Levenshtein distance between each of the three strings and the fourth, and pick the one that gives the lowest distance.

answered Jan 13, 2012 at 16:27

NPE

503k114 gold badges970 silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sergey Kalinichenko · Accepted Answer · 2012-01-13 16:27:48Z

1

You can implement the Levenshtein Distance algorithm, it provides a very nice measure of how close a match between two strings you have. It measures how many keystrokes you need to make in order to turn one string into the other. You can find a C++ implementation here.

Compute Levenshtein Distance between string #4 and the three strings that you have. Pick the string with the smallest distance.

answered Jan 13, 2012 at 16:27

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

2 Comments

xaxxon Over a year ago

Awkwardly, the levenshtein distance to a c++ program in that implementation isn't 0. However, I believe fixing the typedef to be a vector<vector<int>> makes it correct.

Dirk is no longer here Over a year ago

That link to the code is now dead, but this may help: github.com/ekg/freebayes/blob/master/src/levenshtein.cpp

Yakov Galka · Accepted Answer · 2012-01-13 16:31:04Z

1

There's nothing ready in the STL, but what you need is some kind of string metric.

Use Levenshtein distance if the strings are similar up to some typos, e.g. Hello vs Helol.
Use Jaccard distance/Dice's coefficient on the set of n-grams if the strings might change more drastically, like hello world versus world hello.

answered Jan 13, 2012 at 16:31

Yakov Galka

72.9k16 gold badges149 silver badges226 bronze badges

Comments

Aleksandar Vucetic · Accepted Answer · 2012-01-13 16:48:23Z

0

You have approximate string matching problem. Depending on what kind of matching you want to perform, you will use different algorithm. There are many..SOUNDEX, Jaro-Winkler, Levenstein Distance, metaphore... etc. Regarding STL, I don't know any functions that implement those algorithms, but you can take a look here for some soource using c++. Also, note that if you are getting your strings from a database, it is very likely that your database engine implements some of those algorithms (most likely SOUNDEX).

edited Jan 13, 2012 at 16:48

answered Jan 13, 2012 at 16:31

Aleksandar Vucetic

15k9 gold badges57 silver badges56 bronze badges

Collectives™ on Stack Overflow

String matching algorithm

4 Answers 4

Comments

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related