2

有谁知道有效处理以下问题的特定数据结构/算法:

给定一个集合A和一组集合,S = {X,Y,Z..}我想计算 A 和 S 中的所有集合之间的交集的大小,利用它们中的大多数是非不相交的事实,即共享数。

例如:给定A = {1,2...10},X = {1,3,4,5,7}Y = {2,4,5,7,9,10}, 计算AX intersect Y,AX - X intersect Y, Aand之间的交集Y - X intersect Y和对结果求和会更有效。

一个实际的例子可能是在共享一段文本的大量文档中查找关键字的出现次数,(不是总数,而是每个文档。)

请注意,与 Map-Reduce 的唯一区别是文档共享部分文本,并且这些部分应该只解析一次。

如果这有任何帮助,我现在对问题的推理方式是一个图/树,其中节点是重叠区域,其O(n)遍历给出了 A 和 S 的所有元素之间的交集大小。我面临的问题是如何找到要使用的最佳节点集。但也许已经有现成的解决方案了。

4

1 回答 1

0

如果您期望有很大的重叠,那么可能值得将集合存储为具有唯一节点表示的树。如果重叠足够大,这应该比其他任何方法都快。

请参阅以下答案: https ://cs.stackexchange.com/a/18006/10483

于 2015-02-06T22:51:10.447 回答