How to do high performance string matching when comparing unordered sets of tokens [closed]

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?

• 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.
– D.W.
Jan 12, 2015 at 23:01
• 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. Jan 12, 2015 at 23:05
• 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.
– D.W.
Jan 12, 2015 at 23:08