非贪婪搜索和否定字符集的区别

Question

在启用单行模式的情况下，这两个正则表达式模式a.*?b和a[^b]*b有什么区别？它们在性能方面有什么不同吗？

- mpen

---

@raina77ow 不，怎么会呢？如果你知道一个字符串可以匹配一个而不匹配另一个，那就是我需要的答案。 - mpen

在性能方面，a[^b]*b 的得分将优于 a.*?b。 - anubhava

@Mark 当然没有。是的，我确实明白在这两种情况下引擎都应该足够聪明，只需查找下一个 b。问题是，它是直接按照这种方式进行搜索 - 还是从开头（第一种情况）/ 末尾（第二种情况）检查每个字母。 - raina77ow

由于 a.*?b 中涉及到回溯，因此...... - anubhava

是的，我也查看了这个教程。 - raina77ow

Answer 1

a.*?b 必须在每个已消费的字符上检查是否匹配模式（即下一个字符是否为b）。这就是所谓的回溯。

对于字符串a12b，执行过程如下：

• 消耗a
• 消耗接下来的0个字符。下一个是b吗？不是。
• 消耗下一个字符（a1）。下一个是b吗？不是。
• 消耗下一个字符（a12）。下一个是b吗？是的！
• 消耗b
• 匹配

a[^b]*b 消耗任何不是b的内容而无需自问自答，因此在处理较长字符串时速度更快。

对于字符串a12b，执行过程如下：

• 消耗a
• 消耗后面的任何不是b的字符。（a12）
• 消耗b
• 匹配

RegexHero 有一个基准测试功能，可以演示 .NET 正则表达式引擎的性能差异。

除了性能差异之外，在您的示例中它们匹配相同的字符串。

但是，在字符串aa111b111b中有一些情况存在差异：

(?<=aa.*?)b 匹配两个 b，而(?<=aa[^b]*)b 只匹配第一个。

- dee-see

---

很好，但真正的问题是：如果第一种形式和第二种形式注定要产生相同的结果，那么正则表达式引擎是否足够聪明，能够将其转换为第二种形式？ - raina77ow

在这种情况下，它们是等效的。但在一个look-behind或look-ahead中使用相同的标记，情况可能会改变。引擎可能需要更长的时间来确定是否存在差异，而不是执行你使用的任何操作。 - dee-see

@raina77ow 我已经更新了我的答案，并提供了一个示例，其中有所不同。 - dee-see

好的，你能否解释一下上面答案中链接的结果？ - raina77ow

啊，具有非确定长度的反向预查。当然，在正则表达式中拥有这个特性是很好的。但遗憾的是，我所使用的许多工具都没有这个功能。 - raina77ow

Answer 2

我已经测试了您的两个正则表达式，将它们命名为：

NONGREEDY = /a.*?b/;
GREEDY = /a[^b]*b/;

我将负面正则表达式称为GREEDY，但这只是一个名称。

您可以在JsPerf上检查test-non-greedy-vs-greedy-performance并运行测试以自行查看。随意修改字符串以执行不同的测试用例。

您可以检查其他人添加的不同测试，并且基准测试结果取决于输入字符串。

以下测试针对字符串：ab

以下测试是针对字符串：axb 以下测试是针对字符串：afdkjsklfjsdlkfjsdlkfjsdlkjflskdjflsdfjjflksdjfb 在这些测试之后，性能似乎取决于您正在解析的字符串。

希望这个测试可以帮助回答这个问题。

- Federico Piazza

---

就此而言，负字符集正则表达式在.NET引擎中大约快了2.5倍。 - dee-see

现在请查看这个测试。那正是我所评论的内容。 - raina77ow

你有证据表明在这种情况下JsPerf特别相关还是普遍可比PCRE等等吗？ - ajm475du

@ajm475du 我的朋友，没有人这么说过。我喜欢这个问题，所以我提供了一个可共享的测试用例，让大家可以使用、修改和尝试。这只是帮助社区的另一个选择。实际上，我从Vache的回答中学到了更多。 - Federico Piazza

@Fede 谢谢。我的意思是，我想象大多数正则表达式引擎在许多功能上都是相似的，也许特别是这个功能。但我不知道。您已经展示了洞察力，说明进行经验测试并提供一个特定引擎的结果并不难。 - ajm475du