使用非贪婪限定符还是前瞻,哪个更好?

6
我有一个可能很大的文本块,需要寻找包含[[...]]的所有实例,其中...可以是任何内容,包括其他括号(但它们不能嵌套; ]][[之后的第一个实例会结束匹配)。
我可以想到两种方法来匹配这个文本:
  • 使用非贪婪限定符:/\[\[.+?\]\]/
  • 使用前瞻:/\[\[(?:(?!\]\]).)+\]\]/
从性能的角度来看,哪一种选择更好呢(我认为第一种可能更易读)?我记得曾经读过不要使用非贪婪限定符,但现在找不到来源了。
4个回答

6
在这种情况下,最好使用非贪婪量词。以这个示例字符串“[[a]b]]”为例。
非贪婪量词:
\[\[.+?\]\] Atom # 1 2 3 4 5
1. 原子#1 \[匹配。 2. 原子#2 \[匹配。 3. 原子#3 .+?匹配 "a" 。 4. 原子#4 \]匹配。 5. 原子#5 \]失败,返回#3但保留字符串位置。 6. 原子#3 .+?匹配 "]" 。 7. 原子#4 \]失败,返回#3但保留字符串位置。 8. 原子#3 .+?匹配 "b" 。 9. 原子#4 \]匹配。 10. 原子#5 \]匹配。 11. 成功。
前瞻:
\[\[(?:(?!\]\]).)+\]\] Atom # 1 2 3 4 5 6 7
1. 原子#1 \[匹配。 2. 原子#2 \[匹配。 3. 原子#4 (?!\]\])立即在 "a" 处成功(即不匹配),继续。 4. 原子#5 .匹配 "a" ,返回#3。 5. 原子#4 (?!\]\]) "]" 处实现部分匹配。 6. 原子#4 (?!\]\]) "b" 处成功(即不匹配),继续。 7. 原子#5 .匹配 "]" ,返回#3。 8. 原子#4 (?!\]\])立即在 "b" 处成功(即不匹配),继续。 9. 原子#5 .匹配 "b" ,返回#3。 10. 原子#4 (?!\]\]) "]" 处实现部分匹配。 11. 原子#4 (?!\]\]) "]" 处实现完全匹配,因此:#4失败,退出#3。 12. 原子#6 \]匹配。 13. 原子#7 \]匹配。 14. 成功。

看起来非贪婪量词的工作量要少一些。

免责声明:这只是一个人工示例,实际性能可能会有所不同,取决于输入、实际表达式和正则表达式引擎的实现。我只有98%的把握认为我在这里概述的是实际发生的事情,因此我愿意接受纠正。另外,就像所有性能提示一样,不要轻信这个结果,如果你想确定,可以进行自己的基准比较。


3
另一种变体:/\[\[((?:\]?[^]])+)]]/ 该正则表达式既不使用非贪婪量词也不使用先行断言,它允许在任何非 ] 字符之前有一个单独的 ]。如果有两个连续的 ],那么内部的重复将停止,并且匹配也会结束。
这个模式最好与 FSA 编译的正则表达式引擎一起使用。在回溯引擎上,它可能比非贪婪变体更慢。

这也很可能是最符合问题思路的模式。 - Thom Smith

1
你使用的正则表达式是哪种?如果它支持占有量词,那么有一个更好的替代方案:
\[\[(?:[^\]]++|\](?!\]))*+\]\]

[^\]]++会吞噬除了]以外的任何字符,并且不保存状态信息,因此无法回溯。如果它看到一个],它会进行前瞻来查看是否还有另一个]。将整个内容包装在另一个占有量词中意味着只有在看到]时才进行前瞻,并且仅回溯一次:当它找到闭合的]]时。

Java、JGSoft、PCRE(PHP)、Oniguruma(Ruby 1.9)和Perl 5.12都支持占有量词。所有这些语言也支持原子组,可以用于实现相同的效果:

\[\[(?>(?:(?>[^\]]+)|\](?!\]))*)\]\]

.NET版本支持原子组,但不支持占有量词。


0

我认为最好使用非贪婪限定符。你确定你读的那篇文章不是在说“小心贪婪匹配”吗?


1
也许警告是因为非贪婪匹配会导致大量回溯。 - Daniel Brückner
是的。上下文不同,这是一个使用特定否定字符类而不是.*?的论点。 - Daniel Vandersluis

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接