regex - 在步骤和时间上优化多行匹配的正则表达式

Question

正则表达式 - 应该匹配换行符并且应该在特定格式的第一次出现时结束

引用 Regex - should match newlines as well as should end at the first occurence of a particular format

我正在尝试从日志中读取邮件正文(其中一些超过 500 行)。
示例数据如下所示:BodyOftheMail_Script = [ BEGIN 500 lines END ]
我试过以下正则表达式:

+-----------------------------------------------------------------------+----------+--------+
|                                Regexp                                 |   Steps  | Time  |
+-----------------------------------------------------------------------+----------+--------+
| BodyOftheMail_Script\s=\s[\sBEGIN\s{0,}((?s)[\s\S]*?)(?=\s{1,}END\s]) | 1015862  | ~474ms |
| BodyOftheMail_Script\s=\s[\sBEGIN\s{0,}((?s)[\w\W]*?)(?=\s{1,}END\s]) | 1015862  | ~480ms |
| BodyOftheMail_Script\s=\s[\sBEGIN\s{0,}((?s).*?)(?=\s{1,}END\s])      | 1015862  | ~577ms |
| BodyOftheMail_Script\s=\s\[\sBEGIN\s{0,}((.|\n)*?)(?=\s{1,}END\s\])   | 1681711  | ~829ms |
+-----------------------------------------------------------------------+----------+--------+

有没有更快的方法(更优化的正则表达式)来匹配这个？

Answer 1

增强图案
5 种表达中最有效的结果是

BodyOftheMail_Script\s=\s\[\sBEGIN\s*(\S*(?:\s++(?!END\s])\S*)*)\s+END\s]

见 regex demo
我修改的部分是 \S*(?:\s++(?!END\s])\S*)* :

\S* - 0 个或多个非空白字符

(?:\s++(?!END\s])\S*)* - 0 次或多次出现

\s++(?!END\s]) - 1+ 空格字符(匹配 所有格 以便在所有 1+ 空格匹配后只能执行一次先行检查)后面没有 END , 1 个空格和 ]字符

\S* - 0 个或多个非空白字符

为什么不只是一个 BodyOftheMail_Script\s=\s\[\sBEGIN\s*(.*?)\s+END\s] 与 re.DOTALL ? \s*(.*?)\s+END\s]将按如下方式工作:将立即匹配 0+ 个空格，然后 (.*?)第一次会跳过，然后 \s+END\s]模式将被尝试。如 \s+END\s]不匹配， .*?将抓取一个字符并再次让后续模式尝试匹配字符串。等等。可能需要很多回溯步骤才能到达匹配的结尾(如果它在那里，否则它可能迟早会以超时结束)。
性能对比
由于 regex101.com 上的步骤数不能直接证明某种模式比另一种模式更有效，因此我决定使用 Python PyPi regex library 运行性能测试。 .请参阅下面的代码。
在具有 16GB RAM、Intel Core i5-9400F CPU 的 PC 上获得的结果，使用 PyPi regex 版本 2.5.77 和 2.5.82 获得一致的结果:

┌──────────┬─────────────────────────────────────────────────────────────────┐
│   Regex  │  Time taken                                                     │
├──────────┼─────────────────────────────────────────────────────────────────┤
│   OP 1   │  0.5606743000000001                                             │
│   OP 2   │  0.5524994999999999                                             │
│   OP 3   │  0.5026944                                                      │
│   OP 4   │  0.7502984000000001                                             │
│   WS_1   │  0.25729479999999993                                            │
│   WS_2   │  0.3680949                                                      │ 
└──────────┴─────────────────────────────────────────────────────────────────┘

结论 :

最糟糕的 OP 正则表达式包含一个臭名昭著的 (.|\n)*?模式，它是我在正则表达式生活中见过的最低效的模式之一，它总是会导致所有语言的问题。请不要在您的模式中使用它

前三个 OP 模式具有可比性，但比 . 的常见解决方法要清楚匹配任何字符，[\w\W]和 [\s\S] , 如果有办法使 . 应该避免匹配任何带有修饰符的字符，例如 (?s)或 regex.DOTALL . (?s). native 解决方案效率更高一点。

我的建议似乎比最佳 OP 模式的速度快两倍，因为它以块的形式匹配从左侧分隔符到右侧分隔符的字符串，仅在抓取空白块后才停止检查右侧分隔 rune 本和它们后面的空格。

.*?每次一个字符不是右侧分隔符的开头时，构造都会扩展，字符串越长，其效率就会降低。

Python 测试代码 :

import regex, timeit
text = 'BodyOftheMail_Script = [ BEGIN  some text\nhere and\nhere, too       \nEND ]'

regex_pattern_1=regex.compile(r'BodyOftheMail_Script\s=\s\[\sBEGIN\s{0,}((?s)[\s\S]*?)(?=\s{1,}END\s])')
regex_pattern_2=regex.compile(r'BodyOftheMail_Script\s=\s\[\sBEGIN\s{0,}((?s)[\w\W]*?)(?=\s{1,}END\s])')
regex_pattern_3=regex.compile(r'BodyOftheMail_Script\s=\s\[\sBEGIN\s{0,}((?s).*?)(?=\s{1,}END\s])')
regex_pattern_4=regex.compile(r'BodyOftheMail_Script\s=\s\[\sBEGIN\s{0,}((.|\n)*?)(?=\s{1,}END\s\])')
regex_pattern_WS_1=regex.compile(r'BodyOftheMail_Script\s=\s\[\sBEGIN\s*(\S*(?:\s++(?!END\s])\S*)*)\s+END\s]')
regexp_patternWS_2 = regex.compile(r'BodyOftheMail_Script\s=\s\[\sBEGIN\s*(.*?)\s+END\s]', regex.DOTALL)

print(timeit.timeit("p.findall(text)", 'from __main__ import text, regex_pattern_1 as p', number=100000))
# => 0.5606743000000001
print(timeit.timeit("p.findall(text)", 'from __main__ import text, regex_pattern_2 as p', number=100000))
# => 0.5524994999999999
print(timeit.timeit("p.findall(text)", 'from __main__ import text, regex_pattern_3 as p', number=100000))
# => 0.5026944
print(timeit.timeit("p.findall(text)", 'from __main__ import text, regex_pattern_4 as p', number=100000))
# => 0.7502984000000001
print(timeit.timeit("p.findall(text)", 'from __main__ import text, regex_pattern_WS_1 as p', number=100000))
# => 0.25729479999999993
print(timeit.timeit("p.findall(text)", 'from __main__ import text, regexp_patternWS_2 as p', number=100000))
# => 0.3680949