反向正则表达式模式比原始模式慢得多

Question

我有一个相当复杂的正则表达式搜索，最近我不得不将其扩展为“反向”模式。这很容易实现，但性能大约下降了 10 倍。

如果有任何关于如何改善此问题的提示，我将不胜感激，但我并不特别在意如何改善。例如，如果这比单一的、非常复杂的步骤更快，则可以使用两个或更多步骤。

原图

import regex

expression = regex.compile(
    fr"""
(?:{CUE})  # cue before targets. non capture (?:)
(?:{PADDING})  # text before the match.
(?:
(?:{ITEM_SEPARATION})?  # none or once
(?P<targets>{targets_as_regex})
)+
""",
    regex.VERBOSE,
)

需要知道：CUE 是一个相当短的选项列表，例如：

CUE = r"""word
|two\swords
|simple\soptions?
"""

大概有5-15个选项，比较简单（逆向的场景稍微简单一点）。

PADDING 实际上是任何值，但不超过 150。(PADDING = r".{0,150}?")。在相反的情况下它有点限制，只有 [,A-Za-z\d\s]

ITEM_SEPARATION 很简单：可选空格后跟逗号、带界的“y”和更多可选空格：

ITEM_SEPARATION = r"""
\s*          # optional spaces
(?:,|\by\b)  # non-capture, either comma, or 'y' (with bounds) 
\s*          # optional spaces
"""

最后，问题可能出在targets_as_regex，这是一个很大的有界名称列表。这很容易有成百上千个选项，尽管每次调用都会传递一个唯一的目标列表。

这个想法是匹配类似这样的东西：

This is a text, with a cue, then a bit more text and a match, other match y final match. And after the "." we stop matching.

而且表现足够好。但后来我们遇到了相反的情况：

反转模式

思路是这样搭配的：

This not a match, because of the stop. This is a match, another match y final match, because now we find a cue. Etc.

我自然地回收了我的图案：

expression = regex.compile(
    fr"""
(
(?P<targets>{targets_as_regex})
(?:{ITEM_SEPARATION})?  
)+
(?:{SIMPLE_PADDING})  # text before the match
(?:{CUE_AFTER})  # cue after targets
""",
    regex.VERBOSE,
)

它按预期工作，但当目标（很多）出现在提示（很少）之前时，性能非常差。

我试过的

我添加了一个基本检查，如果提示根本不在文本中，我们将忽略整个内容，但这并没有太大帮助。我测试过的另一个想法是搜索目标的所有匹配项（不管提示和所有这些），然后将仅包含这些匹配项的缩短列表 (targets_as_regex) 传递给慢速模式。这实际上有帮助，但帮助不大（仍然接近 10 倍的性能下降）。

还有其他有用的想法吗？

Answer 1

((?P<targets>{targets_as_regex})(?:{ITEM_SEPARATION})?)+是well-knowncatastrophic backtracking俯卧模式（类似于(a+b?)+缩减为(a+)+），越往左的模式，越危险。

您需要将 (a+b?)+ 等模式“展开”到 a+(?:ba+)* 中，使后续子模式仅在字符串内的不同位置匹配。

您需要的图案是

fr"""(?:{targets_as_regex})(?:{ITEM_SEPARATION}(?:{targets_as_regex}))*(?:{SIMPLE_PADDING})(?:{CUE_AFTER})"""

要加快速度，您需要一个从 targets_as_regex 构建的正则表达式 trie，请参阅。

反向正则表达式模式比原始模式慢得多

Reversed regex pattern much slower than original

python

regex