检查子集是否包含给定子集列表的快速方法

Question

我的问题如下

我有一套K元素

这个集合的每个子集都由std::bitset的一个实例表示（第i位为真=子集中有元素i）

我有一个输入子集 I 和一个子集列表 S1...Sn

我想 return 来自 S1...Sn 的项目，这样 Si 就包含在 I 中。（也就是说，每次 Si 有一点为真，它必须在 I还有）

显然这可以在 K*n 中完成，方法是对每个 S 子集独立地进行相同的检查。

但是，有没有通用的方法可以做得更好？我很确定这是可能的，因为在我的例子中，子集列表 S1...Sn 始终相同并且可以进行预处理。我确定可以将子集存储在特定的数据结构（树？特里？）中，这样我就可以一次性丢弃很多相同的数据，等等

example :
K = 5

I = [1,1,0,1,0]

S1 = [1,0,0,0,0]
S2 = [1,1,0,1,0]
S3 = [1,1,1,0,0]

the ouput should return S1,S2 (not S3!)

我有一个常量集 S1,S2,...,Sn，并且运行对同一集 I 的不同查询。

编辑：我在说什么的例子：例如，如果 S1 包含在 S2 中：检查 S1 是否包含在 I 中：如果不包含，则 S2 不能包含在 I 中（无需检查）如果 S3 是 S1 和 S2 的并集：如果 S1 和 S2 包含在 I 中，那么 S3

也是

Answer 1

您可以使用 inverted index 方法。虽然它不会改善最坏情况下的性能，但它可能会加快平均情况下的速度，尤其是对于相对密集的查询向量。

为每个 j=1,2,...,k 创建一个排序列表，如果 j 在 S_i 中，则每个子集都在该列表中。这只在预处理中创建一次。

在您的示例中，它将类似于：

0 -> [S1,S2,S3]
1 -> [S2,S3]
2 -> [S3]
3 -> [S2]
4 -> []

现在，给定一个查询 I 查找包含 I 的 "down" 位之一的所有集合。这与信息检索中的 OR 查询相同。此查询的答案是不在结果中的子集。其余的。

在你的例子中，查询是2 OR 4，查询倒排索引的结果是：S3，所以结果是S1,S2。

这基本上就是搜索引擎所做的，如果查询包含的术语与可能性的数量相比非常少，则效率非常高。

Answer 2

用部分答案回答我的问题：

我们从 S1...Sn 构建一个子集树，使得根节点是空子集（bitset 中全为 0），并且每个 child 包含它的 parent 子集
对于算法，从根开始：
- 每个 child：
  - 如果该节点的子集包含在I中，则添加该子集并以该节点为根再次调用算法
  - 否则，转到下一个 child（永远不会处理此 child 的子树）

现在的问题是，如何从 1) 优化构建树？即具有最大深度和最小深度 "width" 例如，在我的示例中，"bad" 树将是 S1、S2 和 S3 来自根节点的 child。一棵"good"树就是根节点只有S1为child，而以S1为根的树有S2和S3为children。但是我不知道如何构建这棵树

Answer 3

构造一棵二叉树T，所有S1...Sn，其中每个级别k有两个儿子节点，取决于S是否有0或1 在位置 k。树的叶子都是你的S1...Sn.

给定一个输入子集 I 让我们取 Ik（位置 k 中的元素）：如果 Ik==0 你 select 级别 T 的子树K 对应于 0。如果 Ik==1 你 select T 的两个子树都在级别 K。在 T 上以这种方式进行，直到到达所有叶子。

~~在最坏的情况下，您对给定的 I 进行 O(n+k) 操作。~~

由于S1...Sn不会改变，构建树T是一次性操作。

编辑：我的回答太草率了。树 T 有超过 n 片叶子，它有 2^k=m 片叶子。但是我们可以移除不在 S1...Sn 中的叶子和死子树。这将成本分析带到 O(2^k) 但实际上我们将拥有更少的节点。现在分析变得更难了，它是否值得取决于 m 和 n 之间的比率；

我提出了一种不同的分析方法：认为在第k级我们在恒定时间内丢弃所有k级具有无效位的子集S，但我们必须在O(n) 每级子树。由于此操作重复 k 次，因此最大成本为 O(kn)，但实际上平均成本更低。

fast way to check if subset contains a given list of subsets