为什么 Negative Lookahead 使用 And/Or 管道超时

Question

我有一个 And/Or 正则表达式，即 (PatternA|PatternB)，如果 PatternB 不存在，我只采用 PatternA（PatternB 总是在 PatternA 之后，但更重要）所以我在PatternA 管道。

这适用于较短的文本块：

https://regex101.com/r/bU6cU6/5

但是在较长的文本块上超时：

https://regex101.com/r/bU6cU6/2

我不明白的是，如果我把 PatternA 和 Neg Look ahead 单独放在同一个长文本块中，只需要 32 步就可以拒绝它：

https://regex101.com/r/bU6cU6/3

如果我将 PatternB 单独放在同一个长文本块中，它只需要 18 个步骤就可以接受它：

https://regex101.com/r/bU6cU6/4

所以我不确定为什么需要 100,000+/timeout 来首先拒绝（32 步）然后接受（18 步）管道。有没有 another/better 的构建方式，所以它首先检查 PatternA 而不是 PatternB 因为现在它正在做一些我不明白的事情，从 50 步到 100k +。

Answer 1

与 "global" 正则表达式（匹配多次出现）一起使用的未锚定环视会导致过多的跑腿工作，而且效率低下。对于某些具体上下文，它们应该是 "anchored"。通常，它们在字符串的开头（前瞻）或结尾（后视）执行。

在你的情况下，你可以 "anchor" 它放在 Option1: 之后，以确保它只在 Option1: 完全匹配后执行。

Option1:(?!.*Option2)\*.*?(?P<Capture>Bob|David|Ted|Alice)|\*Option2 (?P<Capture2>Juan)
        ^^^^^^^^^^^^^

见this regex demo

更多答案：

What I don't understand is if I put PatternA with the Neg Look ahead alone in the same long text block it takes only 32 steps to reject it

是的，但您在启用内部优化的情况下对其进行了测试。禁用它们，你会看到

if I put PatternB alone in the same long text block it only takes 18 steps to accept it:

以一种非常有效的方式按预期找到了匹配项：

Answer 2

你的主要问题是前瞻的位置。 lookahead 必须在每个位置都尝试，并且每次都必须扫描所有剩余的字符。较长的测试字符串超过 3500 个字符；加起来。

如果您的正则表达式没有锚定，您应该始终尝试从一些具体的东西开始，这些东西会很快失败或成功——文字文本是最好的。在这种情况下，很明显您可以将前瞻移回：Option1:\*(?!.*Option2) 而不是 (?!.*Option2)Option1:\*。（请注意前瞻中缺少尾随 .*；您不需要它。）

但为什么单独匹配 PatternA 会快很多？内部优化。当正则表达式只是 (?!.*Option2.*)Option1:\*.*?(?P<Capture>(Bob|David|Ted|Alice)) 时，正则表达式引擎可以判断匹配必须以 Option1:* 开头，因此它会直接到该位置进行第一次匹配尝试。较长的正则表达式太复杂，没有发生优化。

您可以使用 Regex101 中的 "regex debugger" 选项进行测试，然后选中 DISABLE INTERNAL ENGINE OPTIMIZATIONS。步数回到 100,000 以上。

为什么 Negative Lookahead 使用 And/Or 管道超时

Why does Negative Lookahead times out with And/Or Pipe

python

regex

timeout

negative-lookahead