找出最佳的间隔匹配结果

本文关键字：结果 最佳 | 更新日期: 2023-09-27 18:11:44

在这个表单中我有两组数据:

x   |  y  |  z        x1   |   y1   |  z1
ab1 |  1  |  2        ab1  |   1    |  2
ab1 |  2  |  3        ab1  |   1.8  |  2
ab2 |  2  |  3        ab1  |   1.8  |  2

列数可以在1到30之间变化。两个集合的行数可能不同。每集的平均行数可以在几百到几百万行之间变化。对于每一列，将应用不同的匹配规则，例如:

x: perfect match
y: +/- 0.1
z: +/- 0.5

当满足所有条件时，两行是相等的。我的最终目标是找到第一盘中第二盘中没有匹配的行。

朴素算法可以是:

foreach a in SetA
{
    foreach b in SetB
    {
        if (a == b)
        {
            remove b from SetB
            process the next element in SetA
        }
    }
    log a is not in SetB
}
在这个阶段，我对算法的效率不是很感兴趣。我相信我可以做得更好，我可以减少复杂性。我更关心的是结果的正确性。让我们用一个非常简单的例子。两组数字: 
A       B
1.6    1.55
1.5    1.45
4      3.2

两个元素相等，如果:

b + 0.1 >= a >= b - 0.1

现在，如果我运行朴素算法，我将找到2个匹配。然而，算法的结果取决于两个集合的顺序。例如:

A       B
1.5    1.55
1.6    1.45
4      3.2

算法将只找到一个匹配项。

我想找到匹配行的最大数目。

我估计在现实世界的数据中，其中一列将存储id，因此可能的多重匹配的数量将是原始集合的一个小得多的子集。我知道我可以尝试在第一次扫描后的后处理来面对这个问题。然而，我不想重新发明轮子，我想知道我的问题是否等同于一些著名的，众所周知的，已经解决的问题。

PS:我也把问题标记为c++， c#和Java，因为我将使用其中一种语言来实现它。

找出最佳的间隔匹配结果

它可以被转换成一个图论问题。设X是一个集合，它在第一个集合中每行包含一个节点。设Y为另一个集合，它为第二个集合中的每一行包含一个节点。

图中的边定义为:对于x中的给定x和y中的给定y，如果x对应的行与y对应的行匹配，则存在一条边(x,y)。

一旦你建立了这个图，你可以在它上面运行"maximum-bipartite-matching"算法，你就完成了。

据我所知，您希望第一组中的行与第二组中的任何行不匹配(在错误范围内)。通过解析第一个集合中的元素并将它们与第二个集合中的元素进行比较，这显然可以用复杂度为O(n^2)的算法来完成。一个优化可以是这样的:

  • 对两个集合进行排序- O(n*ln(n))

  • 从第一个集合开始消除太小或太大(在误差范围内)的元素- O(n)

  • 在第二个集合中查找来自第一个集合的元素，使用二分查找(在误差范围内)- O(n*lg(2))，并消除那些不合适的

  • comlexity O (n * ln (n))

范围树?http://en.wikipedia.org/wiki/Range_tree我不太清楚，只是随便说说而已

来自语句"My final goal is find first set with no match in second set."我知道第一个集合中可能有多行与第二个集合中的同一行相匹配。在这种情况下，解决方案是从你的朴素算法中删除"remove b from SetB"这一行。

然而，如果你确实需要两个集合的元素之间一对一的匹配，那么Corey Kosak提供的"maximum-bipartite-matching"的答案就适用了。

考虑到你的约束条件，我没有办法在小于O(n^2)的时间内完成它。我可能会修改你的朴素算法，为表a中的每一行包括一个bool或count字段，然后标记它，如果它匹配表B中的一行。然后根据指示符使用std::partition对其进行后处理，将所有唯一行和非唯一行分组在一起。如果你进行计数，你可以得到"最不唯一"的行。bool会更有效，因为您可以在第一次匹配B时跳出循环。

Two rows are equivalent when all the criteria are satisfied. My final goal is to find the rows in the first set with no match in second set. 

foreach a in SetA
{
    foreach b in SetB
    {
        if (a == b) //why would you alter SetB at all
           go to next A
    }
    remove a from SetA  //log a is not in SetB
}

然而，你是对的，这个is equivalent to some famous, well known and already solved problem。这叫做"集差"。这是……这是集合论的主要部分。因为所有这些语言都有集合，它们也有那个算法。c++甚至有一个专门的函数。所有这些的近似复杂度为O(2(A+B)-1)。

c++标准算法函数:http://www.cplusplus.com/reference/algorithm/set_difference/

vector<row> Result(A.rows());
end = std::set_difference(A.begin(), A.end(), 
                          B.begin(), B.end(), 
                          Result.begin());
Result.resize(end-Result.begin());

或std::unordered_set可以这样做:http://msdn.microsoft.com/en-us/library/bb982739.aspx

std::unordered_set<row> Result(A.begin(), A.end());
for(auto i=B.begin(); i!=B.end(); ++i) {
    auto f = Result.find(*i);
    if (f != A.end())
        A.erase(f);
}

Java也可以:http://download.oracle.com/javase/tutorial/collections/interfaces/set.html

Set<row> Result = new Set<row>(A);
A.removeAll(B);

和c#: http://msdn.microsoft.com/en-us/library/bb299875.aspx

HashSet<row> Result = new HashSet<row>(A);
A.ExceptWith(B);
相关文章：