短语共现矩阵的高效算法

Question

我有一个包含约40,000个短语的列表L和一个包含约10百万单词的文档。 我想要检查哪些这些短语对在4个单词的窗口内同时出现过。例如，假设L=["棕色的狐狸","懒狗"]。文档中包含单词"a quick brown fox jumps over the lazy dog"。我想知道棕色的狐狸和懒狗在窗口大小为四时出现的次数，并将其存储到文件中。以下是我用于完成此操作的代码:

content=open("d.txt","r").read().replace("\n"," ");
for i in range(len(L)):
 for j in range(i+1,len(L)):
  wr=L[i]+"\W+(?:\w+\W+){1,4}"+L[j]
  wrev=L[j]+"\W+(?:\w+\W+){1,4}"+L[i]
  phrasecoccur=len(re.findall(wr, content))+len(re.findall(wrev,content))
  if (phrasecoccur>0):
    f.write(L[i]+", "+L[j]+", "+str(phrasecoccur)+"\n")

基本上，对于列表L中的每一对短语，我会在文档内容中检查这些短语在4个单词的窗口内出现了多少次。然而，当列表L非常大时，例如有40K个元素时，这种方法在计算上效率低下。有没有更好的方法来做到这一点？

- rivu

---

重写你的算法，实现一个滑动窗口迭代器来遍历单词，并尝试使用dict或set而不是列表，因为查找时间更短。 - Joel Cornett

Answer 1

您可以使用类似Aho-Corasick字符串匹配算法的方法。根据短语列表构建状态机，然后开始将单词输入状态机。每当出现匹配时，状态机会告诉您哪个短语匹配以及在哪个单词编号上。因此，您的输出将类似于：

"brown fox", 3
"lazy dog", 8
etc.

你可以捕获所有输出并进行后处理，或者在找到匹配项时处理它们。

构建状态机需要一些时间（对于40,000个短语需要几秒钟），但之后输入令牌数、短语数和匹配数是线性的。

我使用类似的方法将5000万个YouTube视频标题与MusicBrainz数据库中的数百万首歌曲标题和艺术家名称进行匹配。效果很好。而且非常快。

- Jim Mischel

Answer 2

可以将你的40000个短语组装成一个大的正则表达式模式，并使用它来匹配你的文档。这可能不像一些更专业的工具那样快，但它确实有效。以下是我会做的方式：

import re

class Matcher(object):
    def __init__(self, phrases):
        phrase_pattern = "|".join("(?:{})".format(phrase) for phrase in phrases)
        gap_pattern = r"\W+(?:\w+\W+){0,4}?"
        full_pattern = "({0}){1}({0})".format(phrase_pattern, gap_pattern)

        self.regex = re.compile(full_pattern)

    def match(self, doc):
        return self.regex.findall(doc) # or use finditer to generate match objs

以下是如何使用它：

>>> L = ["brown fox", "lazy dog"]
>>> matcher = Matcher(L)
>>> doc = "The quick brown fox jumps over the lazy dog."
>>> matcher.match(doc)
[('brown fox', 'lazy dog')]

这个解决方案确实存在一些限制。其中一个是它无法检测到重叠的短语对。因此，在这个例子中，如果您将短语"jumps over"添加到短语列表中，您仍然只会得到一个匹配对，即("brown fox", "jumps over")，而会错过("brown fox", "lazy dog")和("jumps over", "lazy dog")，因为它们包含了一些相同的单词。

- Blckknght

Answer 3

在Joel的回答基础上，你的迭代器可以是这样的：

def doc_iter(doc):
  words=doc[0:4]
  yield words
  for i in range(3,len(doc)):
    words=words[1:]
    words.append(doc[i])
    yield words

将你的短语放入字典中，并在迭代文档时检查每个短语。这应该为您提供 O(n) 到 O(n*log(n)) 之间的性能。

- Bitwise