Take the 2-minute tour ×

Given two sets of keywords, where each keyword got start and end offset (e.g. keyword "abc" starts at offset 23 and ends at offset 25), I would like to efficiently find matching pairs between those sets. a matched pair is a keyword from set1 and a keyword from set2, where one keyword starts after the other keyword ends, but no more than MAX_PROXIMITY characters between the end of the one to the start of the other. in addition, each keyword can belong only to one pair (matched keyword cannot be reused for another match).

share|improve this question
Do you want to find the closest match? As it stands, the matching is ambiguous. You need additional constraints to make it unique. –  Björn Pollex Dec 22 '11 at 9:48
The result should be a maximized set of pairs. if you have a keyword from set1 that matches two keywords from set2, you should make the choice that would maximize the size of your final pairs set. –  user1111426 Dec 22 '11 at 9:59
The wording sounds like its an assignment. If so, please add the homework-tag. –  Björn Pollex Dec 22 '11 at 10:00

2 Answers 2

You could formulate it as maximum matching in a bipartite graph. Consider the two sets you have as two sets of vertices and generate edges between all the vertices from the first set to all the vertices in second set which satisfy your rule i.e. " where one keyword starts after the other keyword ends, but no more than MAX_PROXIMITY characters between the end of the one to the start of the other"

Once you have the graph in place run a maximum matching algorithm in a bipartite graph. http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs

share|improve this answer

You can use dynamic programming to solve this problem.

Suppose you have each set of keywords ordered by the offset at which they start. Let's define

set1_keyword[i] # i-th keyword in the first set (ordered by the start offset)
set2_keyword[j] # same for the second set
max_pairs[i][j] # number of pairs in optimal assignment between keywords 1..i from the first set and keywords 1..j from the second set

Of course max_pairs[n1][n2] is the answer to your problem (wheren1 and n2 are the sizes of the first and second keyword set respectively)

To compute max_pairs table use the following formula

if (set1_keyword[i] matches set2_keyword[j])
    max_pairs[i][j] = max_pairs[i-1][j-1] + 1
    max_pairs[i][j] = max(max_pairs[i-1][j], max_pairs[i][j-1])

This basically says that if you can match the keywords you do it, because for the problem with keywords 1..i and 1..j it's the best you can do. In the other case (i-th and j-th keywords don't match) you cannot have a solution in which both i-th and j-th keywords are paired to some different keywords. So in the optimal solution either i-th keyword or j-th keyword should be unpaired. That basically tells us to look at the (already computed) solutions for problems max_pairs[i-1][j] (without i-th keyword) or max_pairs[i][j-1] (without j-th keyword) and choose the better of the two.

If you compute this table in the correct order i.e

for (int i = 0; i < n1; ++i)
    for (int j = 0; j < n2; ++j)
        # compute max_pairs[i][j] here

the algorithm will have O(n1*n2) complexity, which is better than the assignment problem in bipartite graph (which runs in O(n^3))

For more on dynamic programming please refer to dynamic programming

share|improve this answer

Your Answer


