寻找短语共现矩阵的有效算法

我有一个包含大约 40,000 个短语的列表 L 和一个包含大约 1000 万个单词的文档。我想检查的是哪一对短语同时出现在 4 个单词的窗口内。例如，考虑 L=[“棕色狐狸”，“懒狗”]。该文件包含“一只敏捷的棕色狐狸跳过懒狗”的字样。我想看看，棕色狐狸和懒狗在四个单词的窗口中出现了多少次，并将其存储在文件中。我有以下代码来执行此操作：

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 元素）时，此方法的计算效率很低。有更好的方法吗？

你可以使用类似的东西Aho-Corasick 字符串匹配算法 https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm。从您的短语列表构建状态机。然后开始将单词输入状态机。每当发生匹配时，状态机都会告诉您匹配的是哪个短语以及匹配的单词编号。所以你的输出会是这样的：

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

您可以捕获所有输出并对其进行后处理，也可以在找到匹配项时对其进行处理。

构建状态机需要一点时间（40,000 个短语需要几秒钟），但之后输入标记的数量、短语的数量和匹配的数量呈线性关系。

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