具有给定集合的集合集合中的最大集合交集的算法/数据结构

Question

我有几百万套C的大集合.我的集合的元素来自大约2000个可能元素的宇宙.我需要知道,对于给定的集合,s,C中的集合与s的交集最大？(或者k在C中设置k个最大的交叉点).我将依次针对不同的s进行许多这些查询.

我知道这样做的显而易见的方法是循环遍历C中的每个集合并计算交集并取最大值.是否有任何智能数据结构/编程技巧可以加快我的搜索速度？如果我能比O(C)更快地做到这一点会很棒.

编辑:大致的答案也没关系

Answer 1

我没有看到任何方法可以在每个查询的 O(C) 以内完成此任务，但我对如何最大限度地提高效率有一些想法。这个想法基本上是为每个元素构建一个查找表。如果某些元素很罕见，有些元素很常见，则可以使用正查找表和负查找表：

s[i] // your query, an array of size 2 thousand, true/false
sign[i] // whether the ith element is positive/negative lookup. +/- 1
sets[i] // a list of all the sets that the ith element belongs/(doesn't) to

query(s):
  overlaps[i] // an array of size C, initialized to 0's
  for i in len(s):
    if s[i]:
      for j in sets[i]:
        overlaps[j] += sign[i]

  return max_index(overlaps)

特别是如果您的许多元素的概率差异很大（正如您所说），这种方法应该可以节省您一些时间：非常罕见或非常常见的元素几乎可以立即处理。

要进一步优化：您可以对结构进行排序，以便首先处理最常见/最罕见的元素。完成第一个（例如 3/4）后，您可以快速浏览一下，看看最接近的匹配集是否远远领先于下一组，以至于没有必要继续，尽管这是否值得再次取决于细节您的数据分布。

另一种改进：使sets[i]成为两种可能的结构之一：如果元素非常罕见或常见，则sets[i]只是第i个元素所在/不所在的集合的列表。但是，假设第i个元素元素在一半集合中。那么sets[i]只是一个索引列表，其长度是集合数量的一半，循环遍历它并增加重叠是浪费的。为sign[i]设置第三个值：如果sign[i]==0，则第i个元素相对接近50％的共同性（这可能意味着5％和95％之间，或其他任何值），而不是它出现的集合列表，它只是一个由 1 和 0 组成的数组，长度等于 C。然后您只需将整个数组添加到重叠中，这样会更快。