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

Question

我从一组C目标集开始.每个集合包含单词(或没有空格的字符串).当我迭代句子时,我可以将句子视为一组观察到的单词D.我的问题是,对于每一个句子,我想找到所有的套S中C,使得D包含S.换句话说,我想找到所有C单词都在句子中的所有单词集.

例如,请考虑以下内容C:

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

现在,如果我看到句子"树倒在灌木丛上,因为它吃了一个jalepeno.",我想要归还两套.

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

这似乎有点类似于特里.但是,它只是相似,因为我不匹配句子中的所有单词,而是任何子集.一个想法是将集合表示为C类似于trie的数据结构Map[String, PseudoTrie],每个级别都有一个,并且当我按照排序顺序迭代句子中的单词时,遵循多条路径.

我理解这类似于搜索查询.但是,如果我需要遍历所有句子,只要每个句子的计算速度很快就可以了.迭代每个集合C并执行包含太慢.

UPDATE

我认为人们可能会对我的一些结果感兴趣.这些定时都在100000个句子和每个目标设置C在D具有约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))所希望的.