python之使用单个正则表达式匹配多个重叠的 n-gram

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

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

(将 n-gram 拆分为任何空白字符上的标记，重新转义这些标记并将它们与 '\s+'-es 连接(这样我就可以在换行符、双空格、制表符等上匹配 ngram)，以及然后用'|'加入正则表达式的n-gram)

我的正则表达式是这样的:

reNgram = re.compile('(\A|\W+)(' + sNgrams + ')(?=\W+|\Z)',flags=re.UNICODE|re.IGNORECASE) 

现在，这对大多数情况都适用，但是，当一个 n-gram 与另一个 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')] 

• 有什么办法可以解决这个问题吗？返回所有匹配的(子)字符串 在文档中？

• 此外，速度/效率非常重要 (我发射了数以万计的这些正则表达式)，有什么我 可以做优化吗？我读过预编译正则表达式不会 做很多事情，因为无论如何都会缓存“即时”编译的正则表达式，我可以采取任何(其他)明显的步骤来加速这些表达式吗？

请您参考如下方法:

我不认为你可以用一个正则表达式来完成。

你可以靠近一点

• 使用先行断言至少找到那些不在同一位置开始的重叠匹配项
• 按长度降序排列 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 和aap noot。正则表达式只能报告字符串中每个位置的一个匹配项，因此它必须匹配两个中的一个。

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