algorithm - 整数列表的子集计算

Question

我目前正在实现一种算法，其中一个特定步骤要求我按以下方式计算子集。

假设我有一组(可能有数百万组)整数。每个集合可能包含大约 1000 个元素:

Set1: [1, 3, 7]
Set2: [1, 5, 8, 10]
Set3: [1, 3, 11, 14, 15]
...,
Set1000000: [1, 7, 10, 19]

想象一个特定的输入集:

InputSet: [1, 7]

我现在想快速计算出这个 InputSet 是哪个子集。在这种特殊情况下，它应该返回 Set1 和 Set1000000。

现在，暴力破解它需要太多时间。我也可以通过 Map/Reduce 进行并行处理，但我正在寻找更智能的解决方案。此外，在某种程度上，它应该是内存高效的。我已经通过使用 BloomFilters 快速消除输入集永远不可能是其子集的集来优化计算。

我错过了什么聪明的技巧吗？

谢谢!

Answer 1

好吧 - 瓶颈似乎是集合的数量，所以不是通过迭代所有集合来找到一个集合，您可以通过从元素映射到包含它们的所有集合并返回包含所有集合的集合来提高性能您搜索的元素。

这与搜索 inverted index 时在 AND 查询中所做的非常相似在领域information retrieval .

在您的示例中，您将拥有:

1 -> [set1, set2, set3, ..., set1000000]
3 -> [set1, set3]
5 -> [set2]
7 -> [set1, set7]
8 -> [set2]
...

编辑:
在 IR 的倒排索引中，为了节省空间，我们有时会使用 d-gaps - 这意味着我们存储文档之间的偏移量，而不是实际的数字。例如，[2,5,10] 将变为 [2,3,5]。这样做并使用 delta encoding当涉及到空间时，表示数字往往会有很大帮助。
(当然也有一个缺点:你需要阅读整个列表才能找到其中是否有特定的集合/文档，并且不能使用二进制搜索，但有时值得这样做，特别是如果它是是否将索引放入 RAM 之间的区别)。