正则表达式负向回顾和前瞻：等价性和性能

Question

正则表达式负向回顾和前瞻：等价性和性能

regexregex-lookaroundsnegative-lookbehind

9

我需要一个正则表达式，只选择不以特定扩展名结尾的URL字符串，例如.png或.css。

我测试了以下内容：

1）使用负回顾后者的正则表达式：

(?<!\.png|\.css)$

https://regex101.com/r/tW4fO5/1

2) 使用负向先行断言的另一种正则表达式：

^(?!.*[.]png|.*[.]css$).*$

https://regex101.com/r/qZ7vA4/1

两种方法都可以正常工作，但是第一种（负回顾）需要处理436步（请参见链接），而第二种（负预测）只需要处理173步。

那么我的问题是：这是什么意思？这会对性能产生影响吗？

最后，这两个正则表达式真的具有等效功能吗？

编辑：解决方案摘要

为了总结一下，考虑通过正则表达式来排除完整的字符串结尾列表（典型情况是Web服务器设置，其中静态资源由apache提供，而动态内容由不同的引擎提供 - 在我的情况下：php-fpm）。

可以使用PCRE正则表达式有两个选项：

1）负回顾

$(?<!\.(?:ico|gif|jpg|png|css|rss|xml|htm|pdf|zip|txt|ttf)$|(?:js|gz)$|(?:html|woff)$)

https://regex101.com/r/eU9fI6/1

请注意，我使用了多个OR-ed回顾，因为负回顾需要一个固定宽度的模式（即：您不能混合不同长度的模式）。这使得这个选项稍微更难写。此外，这会降低性能。

2）负预测

^(?!.*[.](?:js|ico|gif|jpg|png|css|rss|xml|htm|html|pdf|zip|gz|txt|ttf|woff)$).*$

https://regex101.com/r/dP7uD9/1

预测比回顾稍快。这是进行100万次迭代的测试结果：

时间回顾= 18.469825983047秒
时间预测= 14.316685199738秒

如果没有变量长度模式的问题，我会选择回顾，因为它看起来更简洁。无论哪种方法都可以。最后，我选择了预测：

<LocationMatch "^(?!.*[.](?:js|ico|gif|jpg|png|css|rss|xml|htm|html|pdf|zip|gz|txt|ttf|woff)$).*$">
    SetHandler "proxy:unix:/var/run/php5-fpm.sock|fcgi://www/srv/www/gioplet/web/public/index.php"
</LocationMatch>

- Timido

你在哪种正则表达式引擎、平台和数据集上运行了测试？ - Ricardo

1

我在Linux上使用php（PREG）进行了简单的循环测试。当时我使用的是php 5。数据集是一堆具有不同结尾的url（字符串）。 - Timido

2个回答

4

第二个或者lookahead更快。记住步数不是正确的方式。参见Stackoverflow问题: 原子组清晰度。

我已经在Python上使用了timeit进行了测试。脚本如下：

import timeit
s1="""
import re
re.findall(r"^.*(?<!\.png|\.css)$",x,re.M)"""

s2="""
import re
re.findall(r"^(?!.*[.]png$|.*[.]css$).*$",x,re.M)"""

print timeit.timeit(s1,number=1000000,setup='x="""http://gioplet/articles\nhttp://gioplet/img/logo.png\nhttp://gioplet/index.php\nhttp://gioplet/css/main.css"""')

print timeit.timeit(s2,number=1000000,setup='x="""http://gioplet/articles\nhttp://gioplet/img/logo.png\nhttp://gioplet/index.php\nhttp://gioplet/css/main.css"""')

输出：

8.72536265265
7.09159428305

- vks

2

感谢您的测试并提供有用的脚本。好的链接建议也很棒！ - Timido

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Wiktor Stribiżew · Accepted Answer

这会对性能产生影响吗？

在大多数情况下，正则表达式需要的步骤越多，性能就越慢。尽管它还取决于您将在哪个平台上使用正则表达式（比如说，如果您在regex101.com上测试.NET中使用的正则表达式，并不意味着它会因为使用一个具有长文本的懒惰点匹配正则表达式而导致灾难性回溯）。

这两个正则表达式真的是功能等价的吗？

不是的。 (?<!\.png|\.css)$ 查找一行末尾不是以 .png 或 .css 开头的位置。 ^(?!.*[.]png|.*[.]css$).*$ 则查找不包含 .png 的行或不以 .css 结尾的行。如果要使它们“等价”（也就是说，如果您希望确保不会匹配以 .png 或 .css 结尾的行），请使用以下正则表达式：

^(?!.*[.](?:png|css)$).*$
         ^^^^^^^^^^^^

请确保在负向先行断言中，$ 在 png 和 css 两者之后都被选中。

这两个正则表达式仍然有所不同：第一个只匹配行尾，而第二个匹配整行。

有没有一种方法可以加速后瞻解决方案？

请注意，在 Pattern 1 中的后瞻会在字符串内的每个位置进行检查。Pattern 2 中的先行只在字符串的开头检查一次。这就是为什么锚定的先行解决方案将更快，但有一个条件——如果您不能使用 RightToLeft 修改器，这只在少数正则表达式中可用（例如 .NET）。 $(?<!\.(?:png|css)$) 后瞻解决方案比 Pattern 1 更快，因为后瞻模式只在到达字符串/行的末尾时检查一次。尽管如此，这需要更多步骤，因为后瞻的实现比先行更昂贵。

要真正找出哪个解决方案最快，您需要在自己的环境中设置性能测试。