Mar*_*ell 7 set subset data-structures
我正在寻找一个抽象的数据结构,它表示集合的集合,这样集合中的任何集合都不是集合中另一个集合的子集.
这意味着在插入时将满足以下条件:
A.插入已经是另一个元素子集的元素将返回原始集合.
B.插入作为任何其他元素的超集的元素将导致添加超集的集合并移除子集.
假设对集合的元素进行排序,则可以使用前缀树来表示集合.这允许非常快速地处理条件A(即,不再检查条件而不是插入子集)但是满足条件B需要时间.
我想知道是否有数据结构允许B快速满足.
最简单的方法是保留一个集合列表，并对每个传入集合执行线性搜索（测试传入是否是子集）。
显然，线性搜索的运行时间为 O(n)，输入集的大小可能为 O(m)。因此，总时间为 O(n*m)（组数与每组大小）。
当然，最明显的优化是根据集合大小建立索引。然后，您只需针对相同或更大大小的传入集来测试每个传入集。（一个集合不能是任何较小集合的子集，呃！）。
我想到的下一个优化是在元素索引中创建。因此，对于每个传入的集合，您都会找到包含每个元素的每个集合的交集。换句话说，如果对于传入集合{a,b,c}，我们发现元素{a}存在于集合A、B和D中，元素{b}存在于B、E和F中，并且元素{c}存在于集合A、B和D中存在于 A、B 和 Z 中……则传入集合是 B 的子集（{A, B, D}、{B, E, F} 和 {A, B, Z} 的交集）。
所以，这对我来说听起来像是 O(m*log(n)) 复杂度。（我们必须对每个传入集合的每个元素执行哈希搜索）。插入也应该按照相同的顺序（将新集的 ID 插入到每个元素的映射中）。（当然，在 Big-O 分析中，2*O(m log(n)) 减少到 O(m log(n))）。