How to do high performance string matching when comparing unordered sets of tokens 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?
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.