2

我正在尝试执行正则表达式来匹配文档中的多个 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')]

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

  • 此外，速度/效率非常重要（我正在解雇数以万计的这些正则表达式），我可以做些什么来优化？我读过预编译正则表达式并没有多大作用，因为无论如何都会缓存“即时”编译的正则表达式，我可以采取任何（其他）明显的步骤来加速这些表达式吗？

4

1 回答 1

4

我不认为你可以用一个正则表达式来做到这一点。

你可以靠近一点

  • 使用前瞻断言至少找到那些不在同一位置开始的重叠匹配
  • 按长度降序对 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 列表拆分为没有任何字符串以相同单词开头的列表，并按顺序应用这些正则表达式。我怀疑这不会非常高效，但我看不到任何其他方式（除了检查每个单词在其自己的正则表达式中，而且这也不会很快）。

于 2012-10-23T09:02:48.403 回答