python - 在文本中查找大量短语的出现

Question

我正在构建后端并尝试解决以下问题。

• 客户端向后端提交文本(平均约 2000 个字符)
• 接收请求的后端端点必须对提交的文本应用短语突出显示

• 大约有 80k 个短语可以匹配。短语是一个简单的对象:

  {
      'phrase': 'phrase to match'
      'link': 'link_url'
  }
  

• 找到文本中存在的所有短语匹配后，后端将匹配的内容返回给客户端 - 基本上是一个映射:

  range in text -> phrase
  

大部分已完成。我即将解决短语匹配部分的编码问题。其他一切工作顺利。因为我不想重新发明轮子，所以我尝试通过谷歌搜索找到一个 Python 库，该库可以有效地在文本中查找短语(从巨大的列表中)。但是，我找不到任何东西。

我检查了 BlueSoup和 Natural Language Toolkit .然而，他们似乎并没有做我正在寻找的事情。

你们知道是否有一个图书馆可以帮助完成这样的任务吗？似乎是一个很常见的实现，如果有一个完善的库，我不想去定制。

Answer 1

要在匹配 80k 模式时获得合理的速度，您肯定需要对模式进行一些预处理，Boyer-Moore 等单次算法不会有太大帮助。

您可能还需要在编译代码(想想 C 扩展)中完成工作以获得合理的吞吐量。关于如何预处理模式 - 一种选择是状态机，如 Aho-Corasick 或一些通用的 finite state transducer .下一个选项类似于基于 suffix array 的索引，我想到的最后一个是倒排索引。

如果您的匹配是精确的并且模式遵守单词边界，那么即使在纯 Python 中，一个实现良好的单词或单词-ngram 键控 倒排索引 也可能足够快。该索引不是一个完整的解决方案，它会为您提供一些候选短语，您需要使用这些短语与普通字符串匹配进行检查以获得完整匹配。

如果你需要近似匹配，character-ngram倒排索引是你的选择。

关于实际实现 - flashtext如果您对仅限完整短语的限制没有问题，那么此处其他答案中提到的似乎是一个合理的纯 Python 解决方案。

否则，您可以使用支持多模式的通用正则表达式库获得合理的结果:最快的库之一应该是英特尔的 hyperscan - 甚至还有一些基本的python bindings可用。

其他选项是 Google 的 RE2与 Python bindings来自 Facebook 。在这种情况下，您想使用 RE2::Set。