Apo*_*isp 9 language-agnostic algorithm indexing set data-structures
我正在寻找一种算法来在合理的时间内解决以下问题.
给定一组集合,找到作为给定集合的子集的所有这样的集合.
例如,如果您有一组搜索术语,如["堆栈溢出","foo bar",...],则给定文档D,找到所有搜索词,其所有词都出现在D.
我找到了两个足够的解决方案:
使用位向量列表作为索引.要查询给定超集,请为其创建位向量,然后迭代列表,对列表中的每个向量执行按位OR运算.如果结果等于搜索矢量,则搜索集是由当前矢量表示的集合的超集.该算法的O(n)位置n是索引中的集合数,而按位OR非常快.插入是O(1).警告:为了支持英语中的所有单词,位向量需要数百万位长,并且需要存在单词的总顺序,没有间隙.
使用前缀树(trie).在将它们插入到trie之前对它们进行排序.搜索给定集时,请先对其进行排序.迭代搜索集的元素,激活匹配的节点,如果它们是根节点的子节点或先前激活的节点的子节点.通过激活节点到叶子的所有路径表示搜索集的子集.该算法的复杂性O(a log a + ab),其中a是搜索集的大小和b被索引集的数目.
你的解决方案是什么？
如果集合与总词汇量相比比较稀疏，前缀特里树听起来像是我会尝试的东西。不要忘记，如果两个不同前缀的后缀集相同，则可以共享表示后缀集的子图（这可以通过 hash-consing 而不是任意 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 iff b 是包含在 a 中，并且没有冗余弧 a->c，其中 a->b 和 b->c)。分支因子不超过集合中元素的数量。从给定集合可到达的顶点正是其子集的顶点。