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

Question

问题是

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

或者，就集合而不是数组而言：

将 N 个集合（每个集合有 C 个可能的元素）存储到数据结构中，以便您可以快速查找给定集合是否是任何存储集合的超集。< /strong>

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

在某些上下文中，

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

• 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 方法，看看这两种方法中哪一种效果最好。

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

Answer 1

只是为了向前缀特里解决方案添加一些背景信息，最近我发现了以下论文：

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

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

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

Answer 2

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

由于你的数组很稀疏，我还会对它们进行批量测试。如果 (B1 ∪ B2) ⊂ A，则两者都包含在内。因此，我们的想法是按对对数组进行“或”打包，并重复直到只有一个“根”数组（只需要两倍的空间）。它允许您提前对您的问题回答“是”，这在如果您不需要知道数组实际上是否包含时非常有用。

您可以独立地为每个数组应用一个保留排序的哈希函数。

即：B ⊂ A ⇒ h(B) ≺ h(A)

将位组合在一起就是这样一个函数，但您也可以在数组的适当分区中对每个 1 位进行计数。在这里，您可以更快地消除候选者（对于特定数组回答“否”）。

Answer 3

您可以通过首先将集合列表减少为“最小”集合来简化问题：仅保留那些不是任何其他集合的超集的集合。问题仍然是相同的，因为如果某个输入集 A 是您删除的某个集 B 的超集，那么它也是至少一个“最小”子集的超集< B 的 code>C 未删除。这样做的好处是你倾向于消除大集合，这使得问题的成本更低。

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

Answer 4

基于 trie 解决方案和 @mmihaltz 提到的论文，还可以通过使用 Python 现有的高效 trie 实现来实现查找子集的方法。下面我使用包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 实现 此处。