algorithm - 快速检查集合是否是存储集合的超集

Question

问题

我得到了 N 个 C bool 值数组。我想将它们组织成一个数据结构，使我能够尽快执行以下操作:给定一个新数组，如果该数组是任何存储数组的“超集”，则返回 true。对于超集，我的意思是:如果 A[i] 对于 B[i] 为真的每个 i 都为真，则 A 是 B 的超集。如果 B[i] 为假，那么 A[i] 可以是任何东西。

或者，用集合代替数组:

将 N 个集合(每个集合都有 C 个可能的元素)存储到数据结构中，这样您就可以快速查找给定集合是否是任何已存储集合的超集。

构建数据结构可以花费尽可能长的时间，但查找应该尽可能高效，并且数据结构不能占用太多空间。

一些上下文

我认为这本身就是一个有趣的问题，但对于我真正要解决的问题，您可以假设如下:

• N = 10000
• C = 1000
• 存储的数组是稀疏的
• 查找的数组是随机的(所以不是稀疏的)

到目前为止我想出了什么

1. 对于 O(NC) 查找:只需迭代所有数组。不过这太慢了。

2. 对于 O(C) 查找:我在这里有很长的描述，但正如 Amit 在评论中指出的那样，它基本上是一个 BDD .虽然这具有很高的查找速度，但它的节点数量呈指数级增长。 N 和 C 如此之大，这会占用太多空间。

我希望在这个 O(N*C) 和 O(C) 解决方案之间，可能有一个不需要指数级空间的 O(log(N)*C) 解决方案。

编辑:我想出了一个新主意

• 对于 O(sqrt(N)C) 查找:将数组存储为 prefix trie .查找数组 A 时，如果 A[i]=0 则转到相应的子树，但如果 A[i]=1 则访问两个子树。

  我的直觉告诉我，如果您假设存储的数组是随机的，这应该使查找的(平均)复杂度为 O(sqrt(N)C)。但是: 1. 他们不是，数组是稀疏的。 2. 这只是直觉，我无法证明。

我将尝试这个新想法和 BDD 方法，看看两者中哪一个效果最好。

但是与此同时，这个问题不是更频繁地出现了吗？它没有名字吗？之前没有研究过吗？感觉就像我在这里重新发明轮子。

Answer 1

只是为了给prefix trie解决方案补充一些背景信息，最近我发现了以下论文:

I.Savnik:用于快速子集和超集查询的索引数据结构。 CD-ARES, IFIP LNCS, 2013.

论文提出了set-trie数据结构(容器)，使用trie数据结构为集合集合的高效存储和查询提供支持，支持查找所有超集/子集等操作一组集合中的给定集合。

对于任何对实际实现感兴趣的 python 用户，我想出了一个部分基于上述论文的 python3 包。它包含一个基于 trie 的集合容器以及一个映射容器，其中键是集合。您可以在 github 上找到它.