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

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或一些通用的有限状态传感器.下一个选项就像一个suffix array基础索引,我想到的最后一个选项是倒排索引.

如果您的匹配是精确的并且模式遵循字边界,那么inverted index即使在纯Python 中,一个良好实现的单词或word-ngram键入的可能性也足够快.索引不是一个完整的解决方案,它宁愿给你一些候选短语,你需要检查正常的字符串匹配完全匹配.

如果您需要近似匹配,则可以选择character-ngram倒排索引.

关于真正的实现 - 这里的其他答案中提到的flashtext似乎是一个合理的纯Python解决方案,如果你可以使用全短语限制.

否则,您可以使用通用的多模式regexp库获得合理的结果:其中最快的应该是Intel的超级扫描 - 甚至还有一些基本的python 绑定可用.

其他选择是Google的RE2与Facebook的Python绑定.你想RE2::Set在这种情况下使用.

Answer 2

我在自己的聊天页面系统中遇到了几乎完全相同的问题.我希望能够添加指向文本中存在的多个关键字(略有变化)的链接.我只有200左右phrases才能检查.

我决定尝试使用标准的正则表达式来查看问题的速度.主要瓶颈在于构建正则表达式.我决定预先编译它,发现短文的匹配时间非常快.

以下方法采用列表phrases,其中每个包含phrase和link键.它首先构造一个反向查找字典:

{'phrase to match' : 'link_url', 'another phrase' : 'link_url2'}

接下来,它以下面的形式编译正则表达式,这允许在单词之间包含不同数量的空格的匹配:

(phrase\s+to\s+match|another\s+phrase)

然后,对于每个文本(例如每个2000个单词),它用于finditer()获得每个匹配.该match对象使您可以.span()给出匹配文本的开始和结束位置,并group(1)提供匹配的文本.由于文本可能有额外的空格,re_whitespace因此首先应用它来删除它并将其带回存储在reverse字典中的表单.有了这个,就可以自动查找所需的link:

import re

texts = ['this is a phrase   to    match', 'another phrase this  is']
phrases = [{'phrase': 'phrase to match', 'link': 'link_url'}, {'phrase': 'this is', 'link': 'link_url2'}]

reverse = {d['phrase']:d['link'] for d in sorted(phrases, key=lambda x: x['phrase'])}
re_whitespace = re.compile(r'\s+')
re_phrases = re.compile('({})'.format('|'.join(d['phrase'].replace(' ', r'\s+') for d in phrases)))

for text in texts:
    matches = [(match.span(), reverse[re_whitespace.sub(' ', match.group(1))]) for match in re_phrases.finditer(text)]
    print(matches)

这将显示两个文本的匹配:

[((0, 7), 'link_url2'), ((10, 30), 'link_url')]
[((15, 23), 'link_url2')]

为了测试它如何扩展,我通过导入英文单词列表nltk并自动创建80,000两到六个单词短语以及唯一链接来测试它.然后我在两个适当长的文本上定时:

import re
import random
from nltk.corpus import words
import time

english = words.words()

def random_phrase(l=2, h=6):
    return ' '.join(random.sample(english, random.randint(l, h)))


texts = ['this is a phrase   to    match', 'another phrase this  is']
# Make texts ~2000 characters
texts = ['{} {}'.format(t, random_phrase(200, 200)) for t in texts]

phrases = [{'phrase': 'phrase to match', 'link': 'link_url'}, {'phrase': 'this is', 'link': 'link_url2'}]
#Simulate 80k phrases
for x in range(80000):
    phrases.append({'phrase': random_phrase(), 'link': 'link{}'.format(x)})

construct_time = time.time()    

reverse = {d['phrase']:d['link'] for d in phrases}
re_whitespace = re.compile(r'\s+')
re_phrases = re.compile('({})'.format('|'.join(d['phrase'].replace(' ', r'\s+') for d in sorted(phrases, key=lambda x: len(x['phrase'])))))

print('Time to construct:', time.time() - construct_time)
print()

for text in texts:
    start_time = time.time()
    print('{} characters - "{}..."'.format(len(text), text[:60]))
    matches = [(match.span(), reverse[re_whitespace.sub(' ', match.group(1))]) for match in re_phrases.finditer(text)]
    print(matches)
    print('Time taken:', time.time() - start_time)        
    print()

这需要大约17秒来构造正则表达式和反向查找(只需要一次).然后每个文本大约需要6秒钟.对于非常短的文本,每个文本需要约0.06秒.

Time to construct: 16.812477111816406

2092 characters - "this is a phrase   to    match totaquine externize intoxatio..."
[((0, 7), 'link_url2'), ((10, 30), 'link_url')]
Time taken: 6.000027656555176

2189 characters - "another phrase this  is political procoracoidal playstead as..."
[((15, 23), 'link_url2')]
Time taken: 6.190425715255737

这至少会给你一个与之比较的想法.

Answer 3

也许你应该试试flashtext。
据作者介绍，它比 Regex 快得多。

作者甚至为这个图书馆发表了一篇论文。

我亲自为我的一个项目尝试过这个库，在我看来它的 API 非常友好和可用。

希望能帮助到你。