使用regexp时CPU使用率为100%，具体取决于输入长度

Question

我正在尝试用Python编写一个regexp，它必须匹配任何字符，但要避免三个或更多连续的逗号或分号。换句话说，最多只允许两个连续的逗号或分号。

这就是我目前所拥有的：

^(,|;){,2}([^,;]+(,|;){,2})*$

它看起来像预期的那样工作：

>>> r.match('')
<_sre.SRE_Match object at 0x7f23af8407e8>
>>> r.match('foo,')
<_sre.SRE_Match object at 0x7f23af840750>
>>> r.match('foo, a')
<_sre.SRE_Match object at 0x7f23af8407e8>
>>> r.match('foo, ,')
<_sre.SRE_Match object at 0x7f23af840750>
>>> r.match('foo, ,,a')
<_sre.SRE_Match object at 0x7f23af8407e8>
>>> r.match('foo, ,,,')
>>> r.match('foo, ,,,;')
>>> r.match('foo, ,, ;;')
<_sre.SRE_Match object at 0x7f23af840750>

但是随着我开始增加输入文本的长度，regexp似乎需要更多的时间来给出响应。

>>> r.match('foo, bar, baz,, foo')
<_sre.SRE_Match object at 0x7f23af8407e8>
>>> r.match('foo, bar, baz,, fooooo, baaaaar')
<_sre.SRE_Match object at 0x7f23af840750>
>>> r.match('foo, bar, baz,, fooooo, baaaaar,')
<_sre.SRE_Match object at 0x7f23af8407e8>
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,')
<_sre.SRE_Match object at 0x7f23af840750>
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,,')
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,,,')
>>> r.match('foo, bar, baz,, fooooo, baaaaar, baaaaaaz,,,,')

最后，它完全停留在这个阶段，CPU使用率上升到100%。

我不确定regexp是否可以优化，或者还有其他相关的东西，感谢您的帮助。

Answer 1

你遇到catastrophic backtracking了。

这样做的原因是您已经将分隔符设置为可选的，因此您的正则表达式的[^,;]+部分(它本身在一个重复组中)将尝试加载(baaaaaaaz的)排列，最后在遇到两个以上的逗号时不得不承认失败。

在正则表达式引擎使用最后一个测试字符串执行1.000.000步之后，RegexBuddy将中止匹配尝试。Python将继续尝试。

想象一下字符串baaz,,,

尝试使用正则表达式时，正则表达式引擎必须检查所有这些内容：

1. baaz,,<failure>
2. baa + z,,<failure>
3. ba + az,,<failure>
4. ba + z,,<failure>
5. b + aaz,,<failure>
6. b + z,,<failure>
7. b + az,,<failure>
8. b + +z,,<failure>

+ a + aa + a + a + a

在宣布整体失败之前。看看它是如何随着每个额外的字符呈指数增长的？

这样的行为可以通过所有格量词或原子组来避免，遗憾的是，Python当前的正则表达式引擎不支持这两种方法。但是你可以很容易地做一个反向检查：

if ",,," in mystring or ";;;" in mystring:
    fail()

根本不需要正则表达式。如果,;,和类似的东西也可能发生并且应该被排除，那么使用安德鲁的解决方案。

Answer 2

我认为以下内容应该能满足您的需求：

^(?!.*[,;]{3})

如果字符串在一行中包含三个或更多,或;，则此操作将失败。如果您真的希望它与字符匹配，则在末尾添加一个.。

这利用了negative lookahead，如果正则表达式.*[,;]{3}匹配，则会导致整个匹配失败。

Answer 3

试试这个正则表达式：

^([^,;]|,($|[^,]|,[^,])|;($|[^;]|;[^;]))*$

它重复匹配：

• 一个既不是,也不是;的单个字符，或者
• 不跟另一个,或不跟另一个< , >D10,, >或
• 一个不跟另一个;或;;的;;

直到到达终点。它的效率非常高，因为它在早期失败，而不需要做太多的回溯。