快速检查集合是否是已存储集合的超集。

Question

问题

给定 N 个包含 C 个布尔值的数组。我想把它们组织成一种数据结构，使得可以尽可能快地执行以下操作：给定一个新的数组，如果这个数组是任何存储的数组的“超集”，则返回 true。在此处，“超集”指：如果 B[i] 为真，则 A[i] 对于每个 i 都为真。如果 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)的查找：将数组存储为前缀树。当查找一个数组A时，如果A[i]=0，就进入合适的子树，但如果A[i]=1，则访问两个子树。

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

我将尝试使用这个新方法和BDD方法，看看哪一种最好。

但同时，这个问题是否更常见？它有没有名称？之前是否有相关研究？感觉自己在重新发明轮子。

- Migi

---

如果数组是静态的，你可以为每个可能的(a,b)对预先计算is_subset(a,b)。这将需要一个10K*10K位图:=100M/CHAR_BIT。查找显然是O(1)。 - wildplasser

@wildplasser：被查找的数组不是N个存储集合之一（否则结果总是真）。因此，对于查找，我不知道如何使用这个位图。此外，存储的集合中没有一个是另一个的子集，因为如果A是B的子集，那么我可以只存储A。 - Migi

抱歉，我读得太快了。通过一些否定逻辑，并将位集扩展到64位之外，也许可以改编这个（非常类似于BDD）：https://dev59.com/jWox5IYBdhLWcg3wYzQt#9295393 - wildplasser

你的方法实际上与BDD（二叉决策图）非常相似。至少知道这样的东西已经存在可以节省你的实施时间。请注意，BDD通常用于包含几百个变量的一般公式。 - amit

由于所需的结果应该是一个布尔值，因此这确实可以作为BDD实现。变量排序可能可以通过将频率（在sum（N）中）最接近1/2的位（在C中）靠近顶部来指导。 - wildplasser

Answer 1

为了对前缀字典树解决方案提供一些背景信息，最近我找到了以下论文：

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

该论文提出了一种集合字典树数据结构（容器），它利用字典树数据结构支持高效存储和查询集合的集合，支持操作，例如从集合的集合中查找给定集合的所有超集/子集。

对于任何有兴趣实际实现的Python用户，我基于上述论文开发了一个python3包。它包含一个基于字典树的集合容器，以及一个键为集合的映射容器。您可以在github上找到它。

- mmihaltz

Answer 2

我认为前缀树是一个很好的开始。

由于您的数组是稀疏的，因此我建议对它们进行批量测试。如果(B1 ∪ B2) ⊂ A，则两者都包含在内。因此，这个想法是将数组成对OR打包，然后重复这个过程，直到只剩下一个“根”数组（它只需要两倍的空间）。这允许您更早地回答您之前的问题，这对于如果您不需要知道实际包含的数组非常有用。

此外，您可以针对每个数组应用保留顺序的哈希函数。

例如： B ⊂ A ⇒ h(B) ≺ h(A)

将位运算组合在一起就是这样的函数，但您还可以在数组的适当分区中计算每个1位。在这里，您可以更快地消除候选项（对于特定数组回答'No'）。

- YvesgereY

Answer 3

你可以通过首先将你的集合列表简化为“最小”集合来简化问题: 仅保留不是任何其他集合的超集的集合。问题仍然相同，因为如果一些输入集A是你删除的某个集B的超集，那么它也是至少一个B的“最小”子集C的超集，而该子集未被删除。这样做的好处是你 tend to消除大型集合，从而使问题更少成本。

从那里，我会使用某种ID3算法或C4.5算法。

- mitchus

Answer 4

在字典树解决方案和@mmihaltz提到的论文基础上，我们也可以使用已经存在的高效Python字典树实现方法来查找子集。下面我使用datrie包。唯一的缺点是键必须转换为字符串，可以使用"".join(chr(i) for i in myset)完成。然而，这限制了元素范围约为110000。

from datrie import BaseTrie, BaseState

def existsSubset(trie, setarr, trieState=None):

    if trieState is None:
        trieState = BaseState(trie)

    trieState2 = BaseState(trie)
    trieState.copy_to(trieState2)
    for i, elem in enumerate(setarr):
        if trieState2.walk(elem):
            if trieState2.is_terminal() or existsSubset(trie, setarr[i:], trieState2): 
                return True
            trieState.copy_to(trieState2)
    return False

Trie可以像字典一样使用，但是必须在开始时提供可能元素的范围：

alphabet = "".join(chr(i) for i in range(100))
trie = BaseTrie(alphabet)

for subset in sets:
   trie["".join(chr(i) for i in subset)] = 0 # the assigned value does not matter

请注意，上面的Trie实现仅适用于大于（而不是等于）0的键。否则，整数到字符映射将无法正常工作。这个问题可以通过索引移位来解决。

可以在这里找到一个涵盖元素转换的Cython实现。

- Samufi