根据输入长度导致100% CPU使用率的正则表达式

Question

我正在尝试在Python中写一个正则表达式，这个表达式需要匹配任何字符，但要避免出现三个或更多连续的逗号或分号。换句话说，只允许最多出现两个连续的逗号或分号。

这是我现在写的：

^(,|;){,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

试试这个正则表达式：

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

它会重复匹配：

• 一个不是 , 也不是 ; 的单个字符，或者
• 一个 ,，它后面要么没有另一个 ,，要么是 ,, 后面没有另一个 ,，或者
• 一个 ;，它后面要么没有另一个 ;，要么是 ;; 后面没有另一个 ;

直到到达结尾。这个方法非常高效，因为它能很早就失败，而不需要做很多回溯。

Answer 2

我觉得下面的代码应该能满足你的需求：

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

不过，如果字符串中有三个或更多的 , 或 ; 连在一起，这个代码就会出错。如果你想要它能匹配某个字符，可以在最后加一个 .。

这个代码使用了负向前瞻，意思是如果正则表达式 .*[,;]{3} 能匹配成功，那么整个匹配就会失败。

Answer 3

你遇到了一个叫做“灾难性回溯”的问题。

出现这个问题的原因是你把分隔符设置成了可选的，因此正则表达式中的 [^,;]+ 部分（它本身就在一个重复的组里）会尝试很多不同的组合（比如 baaaaaaaz），直到最后不得不承认失败，尤其是在遇到超过两个逗号的时候。

RegexBuddy 在你的最后一个测试字符串上尝试了 1,000,000 次后就放弃了匹配，而 Python 会继续尝试下去。

想象一下字符串 baaz,,,：

使用你的正则表达式时，正则引擎需要检查所有这些组合：

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

在最终宣布失败之前，正则引擎需要检查这么多组合。你能看到每增加一个字符，检查的组合是如何呈指数增长的吗？

这种情况可以通过使用占有量词或原子组来避免，但遗憾的是，Python 当前的正则引擎不支持这两种方式。不过，你可以很容易地进行反向检查：

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

完全不需要正则表达式。如果 ,;, 这样的组合也可能出现并且需要排除，那么可以使用 Andrew 的解决方案。