algorithm - 超集搜索

Question

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

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

例如，如果您有一组搜索词，例如 ["stack overflow", "foo bar", ...]，然后给定一个文档 D，找到所有单词都出现在 D 中的搜索词。

我找到了两个足够的解决方案:

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

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

你的解决方案是什么？

Answer 1

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

对于您的第一个策略的变体，您用一个非常大的整数(位向量)表示每个集合，使用一个稀疏有序的整数集/映射(一个关于跳过连续 0 的位序列的 trie) - 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)。分支因子不超过集合中元素的数量。从给定集合可达的顶点恰好是它的子集。