用一个正则表达式匹配多个重叠的ngram

Question

我试图执行正则表达式来匹配文档中的多个n-gram。 我首先得到一个n-gram的列表，然后将它们编译成一个regex，如下所示：

sNgrams = '|'.join(('\s+'.join(re.escape(gram) for gram in nGram.split())) for nGram in aNgrams)

（将n-gram拆分为任何空白字符上的标记，重新逃逸这些标记并用'\s+'-es连接它们（这样我就可以用换行符、双空格、制表符等等来匹配ngrams），然后用'|'为regex连接n-grams）

我的正则表达式如下所示：

^{pr2}$

现在，这种方法在大多数情况下都很好，但是，当一个n-gram与另一个重叠时，只会找到一个匹配项：

doc = 'aap noot mies'

aNgrams = ['aap','noot','aap noot']
sNgrams = 'aap|noot|aap\\s+noot'
re.findall(reNgram,doc)
[('', 'aap'), (' ', 'noot')]

aNgrams = ['mies','aap noot']
re.findall(reNgram,doc)
[('', 'aap noot'), (' ', 'mies')]

• 有没有办法解决这个问题？返回匹配的所有（子）字符串 在文件里？

• 此外，速度/效率非常重要 （我要解雇数万个这样的正则表达式），有什么要我做的吗 能做什么来优化？我读过预编译正则表达式 做很多事情，因为“动态”编译的正则表达式无论如何都会被缓存，有没有什么（其他）明显的步骤可以加快这些表达式的速度？

Answer 1

我认为你用一个正则表达式是做不到的。在

你可以靠得更近一点

• 使用lookahead断言至少找到那些不在同一位置开始的重叠匹配
• 按长度递减排序n-gram，以确保先找到较大的匹配项

现在，可以找到实际的重叠匹配（noot在app noot之后开始）：

>>> sNgrams = '|'.join(('\s+'.join(re.escape(gram) 
...                    for gram in nGram.split())) 
...                    for nGram in reversed(sorted(aNgrams, key=len)))
>>> sNgrams
'aap\\s+noot|noot|aap'
>>> reNgrams = re.compile(r"(?<!\w)(?=(" + sNgrams + r")(?!\w))",
...                         flags=re.UNICODE|re.IGNORECASE)
>>> reNgrams.findall(doc)
['aap noot', 'noot']

但是它仍然不能同时找到aap和{}。正则表达式只能报告字符串中每个位置的一个匹配项，因此它必须匹配两个位置中的一个。在

为了解决这个问题，您必须将n-gram列表拆分为多个列表，其中没有任何字符串以相同的单词开头，然后按顺序应用这些正则表达式。我怀疑这不会很有效，但我看不到任何其他方法（除了在自己的正则表达式中检查每个单词之外，这也不会很快）。在