正则表达式的100%CPU使用率取决于输入长度

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>

但是当我开始增加输入文本的长度时,正则表达式似乎需要更多时间来给出响应.

>>> 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%.

我不确定是否可以优化正则表达式或者还有其他内容,任何帮助都会受到赞赏.

Answer 1

你正在遭遇灾难性的回溯.

这样做的原因是你已经使分隔符成为可选的,因此[^,;]+你的正则表达式的部分(它本身就是一个重复的组)将尝试加载排列(of baaaaaaaz),然后在面对两个以上的逗号时最终不得不承认失败.

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

想象一下这个字符串baaz,,,:

试试你的正则表达式,正则表达式引擎必须检查所有这些:

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

在宣布整体失败之前.看看每增加一个角色会如何呈指数增长？

使用占有量词或原子组可以避免这样的行为,Python的当前正则表达式引擎遗憾地不支持这两者.但您可以轻松地进行反向检查:

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

根本不需要正则表达式.如果,;,和喜欢也可以发生并且应该排除,那么使用安德鲁的解决方案.

Answer 2

我认为以下应该做你想要的:

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

如果字符串包含三个或更多,或;连续,则会失败.如果你真的希望它匹配一个角色.,最后添加一个.

这利用了负前瞻,如果正则表达式.*[,;]{3}匹配,将导致整个匹配失败.