快速交集运算的数据结构？

Question

随机选择两个集合，每个集合都包含不同的键（一个键可能属于多个集合，一个集合永远不会包含重复的键）。

返回一个整数，表示属于两个集合的键的数量。

例如，intersect({1,2,3,4},{3,4,5})返回2。

我只需要交集的大小。我不需要知道交集中确切的键是什么。

是否有任何数据结构支持这种操作，使其时间复杂度小于O(n)？

编辑：

读取数据确实需要O(n)的时间，但这并不意味着你不能在小于O(n)的时间内执行交集操作。

想象一下这种情况：

我有N个集合，每个集合包含100个键。我读取它们，这是N * 100个操作。现在我想知道哪对集合有最大的交集，这是O(N²)个交集操作。因此，我想减少交集操作的复杂性。我并不真正关心读取和构建集合需要多长时间，最多为N * 100，与O(N²)个交集操作相比，这微不足道。

请注意，没有办法通过执行少于O(N²)个交集操作来找到具有最大交集的集合对，我可以证明这一点。你必须进行所有的交集操作。

（基本思想是，想象一个完全图，有N个顶点，每个顶点代表一个集合，和Nx（N-1）/2条边，每个边代表连接的一对的交集。现在随意给每条边赋非负权重（表示交集大小），我总是可以构造出N个集合满足这些Nx（N-1）/2边权。这证明了我的说法。）

- iouvxz

---

集合是否具有潜在的有用特性，例如，它们通常可以描述为几个范围的并集吗？ - harold

实现更好的复杂度的唯一方法是拥有更多关于数据的信息。即使如此，我也不确定您是否能够达到O(log n)。 - Nelfeal

无论你怎样切片，都必须阅读所有的项目。没有比O(n)更好的解决方案。 - Jim Mischel

@JimMischel，你的理由不足。 - iouvxz

@Nelxiost 唯一的限制是它们是32位整数，没有其他限制。 - iouvxz

Answer 1

I would advise you to take a look at the two possible alternatives, which work particularly well in practice (especially in case of the large sets).

1. Bloom Filter数据结构

Bloom Filter是一种基于位数组的高效率概率数据结构，用于测试元素是否为集合的成员。虽然存在误判，但不会漏判。

在False Positive rate和Bloom Filter的内存占用之间存在权衡。因此，可以根据不同的使用情况估计适当的Bloom Filter大小。

每个集合都可以与其自己的Bloom Filter相关联。很容易获得与不同集合的交集对应的Bloom Filter：可以使用按位AND操作组合与不同Bloom Filters相对应的所有位数组。

拥有与交集对应的Bloom Filter后，可以快速找到存在于所有交集集合中的元素。

除此之外，可以估计交集的基数而无需实际迭代整个集合：https://en.wikipedia.org/wiki/Bloom_filter#The_union_and_intersection_of_sets

2. 跳表数据结构

跳表是一种允许在有序元素序列中进行快速搜索和交集操作的数据结构。通过维护一个链接的子序列层次结构，每个层次跳过更少的元素，实现了快速搜索和交集。

简言之，跳表与普通的链表数据结构非常相似，但是跳表的每个节点都有几个额外的指向其他项的指针（这些指针“跳过”列表的其他节点）。

因此，为了获得交集，需要在所有被交集的跳表中维护指针。在交集期间，指针跳过不在所有被交集的跳表中出现的项。因此，通常交集操作的运行时复杂度比 O(N) 更快。

跳表的交集算法在《信息检索导论》一书中有详细描述，作者是Christopher D. Manning、Prabhakar Raghavan和Hinrich Schütze： http://nlp.stanford.edu/IR-book/html/htmledition/faster-postings-list-intersection-via-skip-pointers-1.html

跳表被广泛应用于高性能、功能齐全的文本搜索引擎库Apache Lucene（跳表被用于倒排索引组件内部）。

这里有一个关于Lucene中使用跳表的额外Stackoverflow问题：how lucene use skip list in inverted index?

- stemm

Answer 2

假设有一种算法可以在不到O(n)的时间内检查交集长度。现在让我们阅读输入的一部分。我们有两个选项：我们已经读取了整个集合和另一个集合的一部分，或者我们已经读取了第一组的一部分和另一组的一部分。

选项1）反例-让我们采取这样的输入，即存在一个元素被读入集合1中，但没有从集合2中读取，但它在集合2中-我们将收到不正确的结果。

选项2）反例-我们可以有这样的输入，其中存在一个元素在两个集合中，但至少有一个集合中没有被读取。我们会得到错误的结果。

好的，我们已经证明了，当我们没有读取整个输入时，没有这样的算法可以返回正确的结果。

让我们读取整个输入- n个数字。哎呀，复杂度是O(n)。

证明结束。

- xenteros

---

为什么我需要再读一遍呢？我已经有两个正确构建的集合，可以作为树或哈希映射或其他的东西。 - iouvxz

我已经将数据存储在内存中。我只需要进行一个快速测试，返回交集的大小即可。 - iouvxz

结构可能是两个集合，带有交集值的额外字段。然后时间复杂度将为 O(1)。只需在输入时计算交集即可。在什么时刻输入结束？ - xenteros

在一般情况下，确实无法拥有一个算法不读取两个集合中每个值的情况，因为一个未读取的值可能会改变输出结果。但如果我们对输入有特定的限制，则不是这样的。@iouvxz，你是否有这样的限制？ - Nelfeal

@Nelxiost 想象一下这个场景，我有N个集合，每个集合包含100个键。我读取它们，这是N100次操作。现在我想知道哪一对集合有最大的交集，那就是O(N²)的交集操作。所以我想要减少交集操作的复杂度。我并不在乎读取和构建集合需要多长时间，最多只有N100次操作，相比于O(N²)的交集操作来说那算不了什么。 - iouvxz