有没有人知道可以有效处理以下问题的特定数据结构/算法:
给定一个集合 A 和一组集合 S = {X,Y,Z..} 我想计算 A 和所有集合之间的交集的大小S 中的集合利用了它们中的大多数是非不相交的事实，即共享数字。
例如:给定 A = {1,2...10}，X = {1,3,4,5,7} 和 Y = {2,4,5,7,9,10}，计算 A 和 X intersect Y 的交集效率更高，A 和X - X 与Y 相交，A 和Y - X 与Y 相交 并将结果相加。
一个实际的例子可能是在共享一段文本的大量文档中查找关键字的出现次数(不是总数，而是每个文档。)
请注意，与 Map-Reduce 的唯一区别是文档共享部分文本，并且这些部分应该只解析一次。
如果这有任何帮助，我现在对这个问题的推理方式是一个图形/树，其中节点是重叠区域，其 O(n) 遍历给出了大小A 和 S 的所有元素之间的交集。我面临的问题是如何找到要使用的最佳节点集。但也许已经有现成的解决方案。
最佳答案
如果您期望有很大的重叠，那么可能值得将这些集合存储为具有唯一节点表示的树丛。如果重叠足够大，这应该比其他任何方法都快。
关于algorithm - 非不相交集之间的高效交集操作，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28128668/