Overlapping findall in python

Question

我正在调试一些遗留代码，发现我们没有正确使用 re.findall。

所以我有一组关键字(也可以是一个短语(，我需要返回句子中出现的所有关键字。

keyWords = [keyword1, keyword2,...] # size around ~500
prog = re.compile(r'b(%s)b'%"|".join(keyWords)) # has to match the entire word, hence the word boundary b
prog.findall(sentence)

但在以下情况下它不起作用：

myKeywords = [A, A B]
mySentence = [A B]

"findall"只会返回 A，因为它是非重叠搜索。

然后我使用re.search回到了残酷的武力：

set(filter(lambda x: bool(re.search(r'b(%s)b'%x, sentence)), keyWords))

但是性能太慢了。大约有 ~500 个关键字和一个不到 10 个单词的句子，残酷的力量需要 10^-2 秒，而 findall 只需要 10^-4 秒。正则表达式编译确实需要 10^-2 秒，但超过 1M 个句子，可以忽略它。

是否有任何内置方法或更快的方法来执行此操作？

第二个想法：

经过进一步调查，我认为这与重叠或非重叠搜索无关，这意味着即使使用非重叠搜索，也无助于解决问题。它更多的是在句子问题中找到所有短语(短语可以是另一个短语的子字符串(。

Answer 1

我认为你想要最长的比赛。

为此，您可以按大小以相反的顺序对关键字进行排序(最长的在前(

import re
keywords = ['a', 'b', 'a b']
keywords.sort(key=lambda k: len(k), reverse=True)
regex = r'b{0}b'.format('|'.join(keywords))
findall_kw = re.compile(regex).findall

例如：

sentence = 'a, a b'
print(findall_kw(sentence))

你会得到：

['a', 'a b']

注意：如果您的关键字可能包含特殊字符，则可以考虑使用re.escape((对其进行转义。