algorithm - super 集搜索

我正在寻找在合理的时间内解决以下问题的算法。

给定一组集合，找到作为给定集合的子集的所有此类集合。

例如，如果您有一组搜索项，例如[“stack stack”，“foo bar”，...]，然后在给定文档D的情况下，找到所有单词都出现在D中的所有搜索项。

我找到了两个合适的解决方案:

使用位向量列表作为索引。要查询给定的超集，请为其创建一个位向量，然后在列表上进行迭代，并对列表中的每个向量执行按位“或”运算。如果结果等于搜索向量，则搜索集合是当前向量表示的集合的超集。该算法是O(n)，其中n是索引中的集合数，并且按位或运算非常快。插入是O(1)。警告:要支持英语中的所有单词，位向量的长度必须为几百万个位，并且单词的总顺序必须没有间隔。

使用前缀树(trie)。对集合进行排序，然后将其插入到trie中。搜索给定集合时，请先对其进行排序。遍历搜索集的元素，激活匹配的节点(如果它们是根节点的子节点或先前激活的节点的子节点)。从激活节点到叶子的所有路径都代表搜索集的子集。该算法的复杂度为O(a log a + ab)，其中a是搜索集的大小，而b是索引集的数量。

您有什么解决方案？

最佳答案

如果集合与总词汇量相比稀疏，则前缀trie听起来像是我会尝试的东西。不要忘记，如果两个不同前缀的后缀集相同，则可以共享表示后缀集的子图(这可以通过散列约束而不是任意DFA最小化来实现)，从而提供DAG而不是树。尝试按最小或最频繁的顺序对您的单词进行排序(我敢打赌，一个或另一个要好于某些随机或字母顺序)。

对于第一种策略的变体，您用一个非常大的整数(位向量)表示每个集合，请使用稀疏有序集合/整数映射(比特序列上的特里树，跳过连续的0的游程)-http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452(在http://www.scala-lang.org/docu/files/api/scala/collection/immutable/IntMap.html中实现)。

如果您的(一组)引用集是固定的，并且您想要找到其中许多包含其他集的引用集，我将计算立即包含关系(具有从a-> b的路径的有向无环图，如果b是包含在a中，并且没有多余的弧a-> c，其中a-> b和b-> c)。分支因子不超过集合中元素的数量。从给定集合可到达的顶点恰好是其子集的那些顶点。

关于algorithm - super 集搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1263524/