java - 比较数字集之间相似性的有效算法？

Question

我有大量的数字集。每组包含 10 个数字，我需要删除与任何其他组有 5 个或更多数字(无序)匹配的所有组。

例如:

set 1: {12,14,222,998,1,89,43,22,7654,23}
set 2: {44,23,64,76,987,3,2345,443,431,88}
set 3: {998,22,7654,345,112,32,89,9842,31,23}

鉴于第 1 组和第 3 组上方的 3 组 10 个数字将被视为重复，因为它们有 5 个匹配数字。因此，在这种情况下，我会删除第 3 组(因为它被认为类似于第 1 组)。

我有 10000 多套要比较，我想非常有效地进行比较。我一直在研究这个问题，但我只是想不出一种有效的方法来执行这种比较(一次完成就很好)。

有什么想法吗？谢谢!

迈克

Answer 1

您应该重新考虑您的要求，因为事实上，该操作甚至没有明确定义的结果。例如，以这些集合为例:

set 1: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 
set 2: {6, 7, 8, 9, 10, 11, 12, 13, 14, 15} 
set 3: {11, 12, 13, 14, 15, 16, 17, 18, 19, 20}

如果您首先将 1 和 2 视为“重复项”并排除第 1 组，则 2 和 3 也是“重复项”并且您只剩下一组。但是，如果您先消除第 2 组，则第 1 组和第 3 组没有匹配项，您还剩下两组。

您可以轻松地将其扩展到完整的 10,000 个集合，这样根据您首先比较和排除的集合，您可能只剩下一个集合或 5,000 个集合。我不认为那是你想要的。

从数学上讲，你的问题是你试图找到 equivalence classes ，但是您用来定义它们的关系“相似性”不是 equivalence relation .具体来说，它是不可传递的。通俗地说，如果集合A与集合B“相似”，集合B与集合C“相似”，那么你的定义并不能确保A也与C“相似”，因此你不能有意义地消除相似集合。

在担心高效实现之前，您需要先明确处理此问题的要求。要么找到一种方法来定义传递相似性，要么保留所有集合并仅使用比较(或每个集合的相似集合列表)。