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

Question

问题

我得到N个C布尔阵列.我想将这些组织成一个数据结构,允许我尽可能快地执行以下操作:给定一个新数组,如果此数组是任何存储数组的"超集",则返回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)查找:将数组存储为前缀trie.查找数组A时,如果A [i] = 0,则转到相应的子树,但如果A [i] = 1 ,则访问两个子树.

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

我将尝试这个新想法和BDD方法,看看哪两个最好.

但与此同时,这个问题不会经常发生吗？它没有名字吗？还没有以前的研究吗？我真的觉得我在这里重新发明轮子.

Answer 1

只是为前缀trie解决方案添加一些背景信息,最近我发现了以下文章:

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

本文提出了set-trie数据结构(容器),它使用trie数据结构为有效存储和查询集合提供支持,支持诸如从集合集合中查找给定集合的所有超集/子集的操作.

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

Answer 2

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

\n\n

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

\n\n

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

\n\n

IE ：B \xe2\x8a\x82 A \xe2\x87\x92 h(B) \xe2\x89\xba h(A)

\n\n

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

\n