正则表达式优化

Question

我需要优化这个正则表达式。

^(.+?)|[wd]+?s+?(dd/dd/dddds+?dd:dd:dd.ddd)[sd]+?s+?(d+?)s+?d+?s+?(d+?)$

输入如下所示：

-tpf0q16|856B             11/20/2014      00:00:00.015    0          0          0          0          0          689        14         689        703        702          701        700

我已经用懒惰的比赛替换了所有准备好的比赛，但这没有帮助。我用过 DOTALL，但它也没有帮助。我使用python和PCRE（re模块），我知道re2，但我不能使用它:(

Answer 1

第一步是摆脱不必要的不情愿（又名"懒惰"）量词。 根据正则表达式好友，您的正则表达式：

^(.+?)|[wd]+?s+?(dd/dd/dddds+?dd:dd:dd.ddd)[sd]+?s+?(d+?)s+?d+?s+?(d+?)$

。需要 6425 个步骤来匹配示例字符串。 这个：

^(.+?)|[wd]+s+(dd/dd/dddds+dd:dd:dd.ddd)[sd]+s+(d+)s+d+s+(d+)$

。需要 716 步。

不情愿的量词通过预先做更多的工作来减少回溯。 您的正则表达式不容易出现过多的回溯，因此不情愿的量词增加了很多工作量。

此版本将其减少到 237 个步骤：

^([^|]+)|w+s+(dd/dd/dddds+dd:dd:dd.ddd)(?:s+d+)+s+(d+)s+d+s+(d+)$

它还消除了一些噪音，如/之前的反斜杠;和[wd]，这与w完全相同。

Answer 2

更优化一点。

>>> import re
>>> s = "-tpf0q16|856B             11/20/2014      00:00:00.015    0          0          0          0          0          689        14         689        703        702          701        700"
>>> re.findall(r'(?m)^([^|]+)|[wd]+?s+?(d{2}/d{2}/d{4}s+d{2}:d{2}:d{2}.d{3})[sd]+?(d+)s+d+s+(d+?)$', s)
[('-tpf0q16', '11/20/2014      00:00:00.015', '702', '700')]

演示