algorithm - 从包含在集合 D 中的集合 C 的集合中有效地找到所有集合 S

Question

我从一组 C 目标集开始。每组包含单词(或不带空格的字符串)。当我遍历句子时，我可以将句子视为一组观察到的单词 D。我的问题是，对于每个句子，我想在 C 中找到所有 S 集，这样 D 包含 S。换句话说，我想在 C 中找到所有单词集，它们的所有单词都在句子中。

例如，考虑C的以下内容:

  {fell, ate}
  {cat, snail, tiger}
  {tree, bush, jalepeno}
  {pen, paperclip, stapler}

现在，如果我看到“这棵树因为吃了墨西哥辣椒而倒在灌木丛上。”这句话，我会想要退回以下两套。

  {fell, ate}
  {tree, bush, jalepeno}

这看起来有点类似于 trie。然而，它只是相似的，因为我没有匹配句子中的所有单词，而是匹配任何子集。一个想法是在类似 trie 的数据结构中用 Map[String, PseudoTrie] 在每个级别表示集合 C，并在我迭代时遵循多个路径通过它按排序顺序覆盖句子中的单词。

我知道这类似于搜索查询。但是，如果我需要遍历所有句子也没关系，只要每个句子的计算速度很快即可。在 C 中迭代每个集合并执行包含太慢。

更新

我认为人们可能会对我的一些结果感兴趣。这些时间是在 100000 个句子上，D 中的每个目标集 C 大约有 4 或 5 个单词。

1. 原始申请。遍历所有目标集，看看它们是否包含在句子中，其中句子由一组单词表示。 227秒

2. 按词汇过滤。与原始过程相同，除了句子由该句子中也在某些目标集中的单词集表示。优点是我们在进行比较时只需要考虑句子中的一部分单词。 110秒

3. 字符串被转换为从 0 开始的整数键。这也包括必要的试验 #2 中的过滤。 86秒

4. 添加倒排索引。 4秒

我还尝试了带有倒排索引的 BitSet。花了 20 秒，所以我没有坚持下去。我不确定为什么速度变慢了——我可能做错了什么。

此外，我认为我最初的想法很棒(多层倒排索引)但它相当复杂，而且我已经有了很好的加速!

Answer 1

我们将从您要搜索的句子语料库开始:

val corpus = Seq(
  Set("fell", "ate"),
  Set("cat", "snail", "tiger"),
  Set("tree", "bush", "jalapeno"),
  Set("pen", "paperclip", "stapler")
)

一种相当有效的表示方式是将其表示为位表，其中词汇类型作为列，句子作为行。我们定义了几个函数来转换为这种表示:

import scala.collection.immutable.BitSet

def vocabulary(c: Seq[Set[String]]) = c.reduce(_ union _).zipWithIndex.toMap

def convert(s: Set[String], v: Map[String, Int]) = (BitSet.empty /: s) {
  (b, w) => v.get(w).map(b + _).getOrElse(b)
}

还有一个函数，用于在语料库 c 中搜索给定句子 s 包含的所有句子:

def search(s: BitSet, c: Seq[BitSet]) = c.filter(x => (x & s) == x)

这会非常快，因为它只是按位“与”和语料库中每个句子的相等比较。我们可以测试:

val vocab = vocabulary(corpus)
val table = corpus.map(convert(_, vocab))

val sentence = convert(
  "The tree fell over on the bush because it ate a jalapeno".split(" ").toSet,
  vocab
)

val result = search(sentence, table)

这给了我们 List(BitSet(2, 6), BitSet(5, 7, 10))。确认这是我们想要的:

val bacov = vocab.map(_.swap).toMap
result.map(_.map(bacov(_)))

根据需要，这是 List(Set(fell, ate), Set(jalapeno, tree, bush))。