1
$\begingroup$

This is the problem:

I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one time in a string).

I want to know if a new string matches any of them without taking token order into account.

The metric I think about is something like this (comparing two strings at the time, this is the first thing that came to my mind when trying to solve the problem and don't know if it is already used), a matching percentage calculated like this:

Match_Metric(A, B) = number_of_matched_tokens(A, B) / max_number_of_tokens_in_any_of_two_strings(A,B) * 100. 

Example:

String 1: "abc, cde, ghi, adc, dca, aab"

String 2: "cd, r, a, x"
String 3: "aab, cde, ghi, abc, adc, dca" 
String 4: "aab, cde, ghi, abc, adc, dca, rrrm, a" 

1 vs 2 = 0%
1 vs 3 = 100%
1 vs 4 = 75%

What I am trying to avoid is to perform a one to one comparison between tokens, but I am finding that other techniques like edit distance won't give me an exact match in the case of 1 vs 3 unless I first order the tokens.

The problem can be extended to do a string search within the tokens, for example:

String 1: "abc, cde, ghi, adc, dca, aab"

String 2: "cd, r, a, x"

As "d" appears in one token in 2 and three tokens in 1, that can affect the metric. In this case an approximate string matching technique such as "edit distance" would be useful but in a token versus token approach. The formula would be more complicated in this case, instead of having an integer representing the number of matched tokens it would be a fraction number and could be calculated like this:

Comparing two tokens at the time one from the string A and one from the string B:

token_match(a,b) = 1 - edit_distance(a,b) / length_of_largest_token(a,b)

So the general metric would be:

String A = {a0, ..., an}
String B = {b0, ..., bm}

i = {0, ..., n}
j = {0, ..., m}

Match_Metric(A, B) = sum(token_match(ai, bj)) / max_number_of_tokens_in_any_of_two_strings(A,B) * 100

Any ideas on what technique/algorithm is more broadly adopted/used for this problem?

$\endgroup$
4
  • $\begingroup$ 1. Your question is unclear. Do you want to check whether a new string exactly matches something in the database? Do you want to look for an approximate match? If the latter, you'll need to define what distance measure is appropriate for your application. 2. What research have you done? Look at locality-sensitive hashing, k-nearest neighbors, approximate matching, and similar topics. As it stands this question is not well-defined enough ot be answerable. $\endgroup$
    – D.W.
    Jan 12, 2015 at 23:01
  • $\begingroup$ I think the problem is clear and I also gave an example, don't get distracted about if the strings are in a database that is not important. The problem is about matching strings which contain set of tokens, look at how the metric is working in the list of matches (1 vs 2, ...). The research I've done is about edit distance and some about token based pattern matching. Thanks. $\endgroup$
    – raspacorp
    Jan 12, 2015 at 23:05
  • $\begingroup$ For others to answer the question, it has to be clear to others who might answer -- and it's still not clear to me. Until you specify what distance metric to use, the question is not well-posed. What research have you done? Have you looked at similarity metrics? (e.g., en.wikipedia.org/wiki/Jaccard_index, en.wikipedia.org/wiki/Tversky_index, en.wikipedia.org/wiki/String_metric) Do any of them meet your needs? You might need to do more research before you can pose a well-specified question. An example is not a specification. $\endgroup$
    – D.W.
    Jan 12, 2015 at 23:08
  • $\begingroup$ Ok I added more information about the metric and also extended it from the top of my head. $\endgroup$
    – raspacorp
    Jan 13, 2015 at 20:40

1 Answer 1

2
$\begingroup$

So you want to use the Jaccard index as your metric of similarity. Well, the Wikipedia page for the Jaccard index (and which I linked to in the comments above) already has some hints on methods for finding close matches, more efficiently than comparing all pairs. For instance, you can use locality-sensitive hashing. Hint for the future: you might want to do more research in the future based on feedback from folks, as locality-sensitive hashing was already suggested in the comments and a relevant Wikipedia page was also mentioned in the comments.

If tokens are not too common, there's another alternative method you could also try. You could build an inverted index: an index that, for each token, lists all of the strings that contain it. Now given a new string S, it's easy to enumerate over all of the tokens in it, look each one up in the inverted index, find all other strings that share at least one token in common with S, compute the similarity between that string and S, and keep the best one. As long as no string contains too many tokens and no token is present in too large a fraction of strings, this will perform better than all-pairs comparison.


Your "extended" problem is different in nature and would probably be better asked as a separate question. It might be a much harder problem.

$\endgroup$
1
  • $\begingroup$ Well, I didn't know about Jaccard index until now, but it seems to be very similar to the metric I proposed. Both are very close to each other when comparing a string with small number of tokens with a big one because Jaccard uses the size of the union. But the one I proposed will also give more weight to strings that are similar in number of tokens, which in my opinion gives more information about similarity. $\endgroup$
    – raspacorp
    Jan 13, 2015 at 22:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.