查找两个集合之间的接近匹配对

Question

给定两组关键字，其中每个关键字都有开始和结束偏移量(例如，关键字"abc“开始于偏移量23，结束于偏移量25)，我希望在这两组关键字之间有效地找到匹配对。匹配对是来自set1的关键字和来自set2的关键字，其中一个关键字在另一个关键字结束后开始，但从一个关键字的结尾到另一个关键字的开始之间不超过MAX_PROXIMITY个字符。此外，每个关键字只能属于一对(匹配的关键字不能重复用于另一个匹配)。

Answer 1

您可以将其表示为二部图中的最大匹配。将您拥有的两个集合视为两个顶点集合，并在从第一个集合到第二个集合中的所有顶点之间生成满足您的规则的边，即“其中一个关键字在另一个关键字结束后开始，但在一个关键字结束到另一个关键字开始之间不超过MAX_PROXIMITY字符”

一旦有了图，就可以在二分图中运行最大匹配算法。http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs

Answer 2

您可以使用动态编程来解决此问题。

假设每组关键字都是按照它们开始的偏移量排序的。让我们定义一下

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

当然，max_pairs[n1][n2]可以解决您的问题(其中n1和n2分别是第一个和第二个关键字集合的大小)

使用以下公式计算max_pairs表

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

这基本上是说，如果你能匹配关键字，你就会这样做，因为对于关键字1..i和1..j的问题，这是你能做的最好的。在另一种情况下(i-th和j-th关键字不匹配)，您不能有一个同时将i-th和j-th关键字与某些不同的关键字配对的解决方案。因此，在最优解决方案中，第i个关键字或第j个关键字应该是不成对的。这基本上告诉我们查看问题的(已经计算的)解决方案max_pairs[i-1][j] (不带第i个关键字)或max_pairs[i][j-1] (不带第j个关键字)，然后在两个中选择较好的一个。

如果您以正确的顺序计算此表，即

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

该算法的复杂度为O(n1*n2)，优于二部图中的指派问题(运行时间为O(n^3))

有关动态编程的更多信息，请参阅dynamic programming