logo标签列表

Atomic groups clarity

regexpcrebacktracking
12

考虑这个正则表达式。

a*b

在输入 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac 时，这段代码将会失效。

在调试器中，运行这段代码需要 67 步才会失效。

现在考虑以下正则表达式。

(?>a*)b

在出现 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac 的情况下，这将会失败。

在调试器中，需要经过 133 步才能失败。

最后是这个正则表达式：

a*+b  (a variant of atomic group)

在出现 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac 的情况下，这个会失败。

在调试器中需要经过 67 步骤才能失败。

当我检查基准测试时，原子组 (?>a*)b 的表现快了 179%。

现在原子组可以禁用回溯。所以匹配的性能很好。

  1. 但是为什么步骤数更多呢？有人能解释一下吗？

  2. 为什么两个原子组 (?>a*)b 和 a*+b 的步骤数不同。

它们的工作方式不同吗？


你的意思是 a*+b 是一个原子组吗？ - Avinash Raj
2
几点说明：1. a*+b 中的 *+ 是 贪婪 的，它并不会使其原子化。2. 步骤数量更多是因为引擎回溯以匹配。这直接需要正则表达式优化来防止过度回溯和潜在的 ReDoS。3. (?>a*) =/= (?>a)*。 - Unihedron
@AvinashRaj a*+b 不是原子操作，但可以防止回溯。所以我尝试了那个。 - vks
@Unihedron 引擎进行回溯，是因为我已经禁用了优化吗？原子组是引擎优化的一部分吗？ - vks
@vks希望你现在已经明白了。我也卡在同一个点上了。你能否解释一下为什么即使指定为原子组，回溯仍然会发生呢？ - Mohan
@Mohan请阅读https://dev59.com/lV8e5IYBdhLWcg3wF3SV#26141971。 - vks
3个回答
11

什么是回溯？

引擎默认使用贪婪量词。贪婪量词会匹配所有可能的内容，然后根据需要进行回溯，从而实现高效匹配。

参考贪婪 vs. 勉强 vs. 占有量词：

贪婪量词首先尽可能多地匹配。所以 .* 匹配整个字符串。然后匹配器尝试匹配其后面的 f，但没有剩余字符。因此它“回溯”，使贪婪量词少匹配一个内容（留下字符串末尾的 "o" 未匹配）。这仍然无法匹配正则表达式中的 f，因此它再次“回溯”一步，使贪婪量词再次少匹配一个内容（留下字符串末尾的 "oo" 未匹配）。这仍然无法匹配正则表达式中的 f，因此它再次回溯一步（留下字符串末尾的 "foo" 未匹配）。现在，匹配器最终匹配了正则表达式中的 f，接下来的 o 和下一个 o 也被匹配了。成功！[...]

a*+b 与回溯有什么关系？

在 /a*+b/ 中：

  • a 表示字面字符 "a"。
  • *+ 表示零个或多个，占有量词。
  • b 表示字面字符 "b"。

参考贪婪 vs. 勉强 vs. 占有量词：

占有量词与贪婪量词非常相似，但它不会回溯。因此，它使用 .* 匹配整个字符串，没有留下未匹配的内容。然后，它无法与正则表达式中的 f 匹配。由于占有量词不回溯，匹配失败。

为什么这很重要？

机器本身无法意识到它是否进行了（不）高效的匹配。这里有一个不错的例子：当匹配正则表达式时程序运行时间无限长。在许多情况下，快速编写的正则表达式可能不是很高效，并且在部署中可能会出现问题。

什么是原子组？

在原子组匹配完成后，它将永远不会放手。看这个例子：

Pattern: (?>\d\w{2}|12)c
Matching string: 12c

看起来完全合法，但这场比赛失败了。步骤很简单：原子组的第一个交替项完全匹配-\d\w{2}消耗了12c。该组然后完成其匹配-现在这是我们的指针位置：

Pattern: (?>\d\w{2}|12)c
                   ^
Matching string: 12c
                    ^

模式在前进。现在我们尝试匹配 c，但没有 c。与其尝试回溯（释放 \d\w{2} 并消耗 12），匹配失败。

这样做不好啊！为什么要防止回溯，Unihedron？

现在想象一下我们正在操作一个 JSON 对象。这个文件不小。从结尾回溯会是个坏主意。

       "2597401":[{"jobID":"2597401",
                 "account":"TG-CCR120014",
                 "user":"charngda",
                 "pkgT":{"pgi/7.2-  5":{"libA":["libpgc.so"],
                 "flavor":["default"]}},          
                 "startEpoch":"1338497979",
                 "runTime":"1022",
                 "execType":"user:binary",              
                 "exec":"ft.D.64",
                 "numNodes":"4",
                 "sha1":"5a79879235aa31b6a46e73b43879428e2a175db5",
                 "execEpoch":1336766742,
                 "execModify":"Fri May 11 15:05:42 2012",
                 "startTime":"Thu May 31 15:59:39 2012",
                 "numCores":"64",
                 "sizeT":{"bss":"1881400168","text":"239574","data":"22504"}},  
                 {"jobID":"2597401",
                 "account":"TG-CCR120014",
                 "user":"charngda",
                 "pkgT":{"pgi/7.2-5":{"libA":["libpgc.so"],
                 "flavor":["default"]}},
                 "startEpoch":"1338497946",
                 "runTime":"33"  "execType":"user:binary",
                 "exec":"cg.C.64",
                 "numNodes":"4",
                 "sha1":"caf415e011e28b7e4e5b050fb61cbf71a62a9789",
                 "execEpoch":1336766735,
                "execModify":"Fri May 11 15:05:35 2012",
                "startTime":"Thu May 31 15:59:06 2012",
                "numCores":"64",
                "sizeT":{"bss":"29630984","text":"225749","data":"20360"}},
                {"jobID":"2597401",
                "account":"TG-CCR120014",
                "user":"charngda",
                "pkgT":{"pgi/7.2-5":  {"libA":["libpgc.so"],
                "flavor":["default"]}},
                "startEpoch":"1338500447",
                "runTime":"145",
                "execType":"user:binary",
                "exec":"mg.D.64",
                "numNodes":"4",
                "sha1":"173de32e1514ad097b1c051ec49c4eb240f2001f",
                "execEpoch":1336766756,
                "execModify":"Fri May 11 15:05:56 2012",
                "startTime":"Thu May 31 16:40:47 2012",
                "numCores":"64",
                "sizeT":{"bss":"456954120","text":"426186","data":"22184"}},{"jobID":"2597401",
                "account":"TG-CCR120014",
                "user":"charngda",
                "pkgT":{"pgi/7.2-5":{"libA":["libpgc.so"],
                "flavor":["default"]}},
                "startEpoch":"1338499002",
                "runTime":"1444",
                "execType":"user:binary",
                "exec":"lu.D.64",
                "numNodes":"4",
                "sha1":"c6dc16d25c2f23d2a3321d4feed16ab7e10c2cc1",
                "execEpoch":1336766748,
                "execModify":"Fri May 11 15:05:48 2012",
                "startTime":"Thu May 31 16:16:42 2012",
                "numCores":"64",
                "sizeT":{"bss":"199850984","text":"474218","data":"27064"}}],

哦糟糕...

现在你明白我的意思了吧？:P

我将让你自己找出其余部分，并尝试了解更多关于占有量词和原子组的内容；我不会在此帖子中再写任何东西。 这里是JSON来源，我几天前看到了答案，非常启发人： REGEX重新格式化。

另请阅读

这实际上很好。澄清了一些事情。但问题仍然存在。为什么在定义原子组时，调试器需要更多的步骤才能失败？ - vks
9

作者注:

    本回答针对赏金文本中提出的问题1，即“我期待知道为什么调试器需要更多步骤的确切原因。我不需要解释原子组是如何工作的。”；Jerry's answer 很好地解决了其他问题，而 我的另一个回答 则介绍了提到的结构、它们是如何工作以及它们为什么重要。为了全面了解，仅阅读本帖是不够的！

正则表达式中的每个组都需要进入和退出。

    什么？！
是的，我是认真的，请继续阅读...

首先，我想向您介绍量化非捕获组，没有这个组：

Pattern 1: (?:c)at
Pattern 2: cat

那么这里到底发生了什么？我们将在禁用优化的正则表达式引擎上，将模式与测试字符串"concat"进行匹配：

(?:c)atcat

在此之际，我向您介绍更多的组：

groups

    哦不！我要避免使用组！

但等等！ 请注意，匹配所需的步骤数与匹配性能没有相关性。 引擎优化掉了大部分我提到的“不必要的步骤”。原子组仍然是最有效的，即使在禁用优化的引擎上需要更多步骤。

也许相关：

4

我认为有些问题...

我不知道你是怎么做基准测试的，但a*+b和(?>a*)b应该是相同的。引用regular-expressions.info（重点在于我）：

基本上，不要使用X*+，而是使用(?>X*)。重要的是要注意到量化的标记X和量词都在原子组内。即使X是一个组，您仍然需要在其周围放置额外的原子组以达到相同的效果。(?:a|b)*+等效于(?>(?:a|b)*)，但不等于(?>a|b)*。后者是一个有效的正则表达式，但在作为较大正则表达式的一部分使用时将不具有相同的效果。

为了确认上述内容，我在ideone上运行了以下内容：

$tests = 1000000;

$start = microtime( TRUE );
for( $i = 1; $i <= $tests; $i += 1 ) {
    preg_match('/a*b/','aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac');
}
$stop = microtime( TRUE );

printf( "For /a*b/    : %1.15f per iteration for %s iterations\n", ($stop - $start)/$tests, $tests );
unset( $stop, $start );

$start = microtime( TRUE );
for( $i = 1; $i <= $tests; $i += 1 ) {
    preg_match('/(?>a*)b/','aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac');
}
$stop = microtime( TRUE );

printf( "For /(?>a*)b/: %1.15f per iteration for %s iterations\n", ($stop - $start)/$tests, $tests );
unset( $stop, $start );

$start = microtime( TRUE );
for( $i = 1; $i <= $tests; $i += 1 ) {
    preg_match('/a*+b/','aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac');
}
$stop = microtime( TRUE );

printf( "For /a*+b/   : %1.15f per iteration for %s iterations\n", ($stop - $start)/$tests, $tests );
unset( $stop, $start );

$start = microtime( TRUE );
for( $i = 1; $i <= $tests; $i += 1 ) {
    preg_match('/(?>a)*b/','aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac');
}
$stop = microtime( TRUE );

printf( "For /(?>a)*b/: %1.15f per iteration for %s iterations\n", ($stop - $start)/$tests, $tests );
unset( $stop, $start );

获得以下输出：
For /a*b/    : 0.000000879034996 per iteration for 1000000 iterations
For /(?>a*)b/: 0.000000876362085 per iteration for 1000000 iterations
For /a*+b/   : 0.000000880002022 per iteration for 1000000 iterations
For /(?>a)*b/: 0.000000883045912 per iteration for 1000000 iterations

现在，我并不是 PHP 专家，所以我不知道这是否是正确的基准测试方法，但它们都具有大致相同的性能，这种情况是可以预料的，因为任务的简单性。

还是从上面注意到了一些事情：

无论是 (?>a)*b 还是 (?>a*)b 都没有比其他正则表达式快 179%；以上所有正则表达式的性能相差不超过 7%。

回到实际问题

但为什么步骤数更多呢？有人能解释一下吗？

需要注意的是，步骤数并不直接代表正则表达式的性能。它是一个因素，但不是最终的决定因素。步骤更多是因为在进入组之前和之后都有步骤的拆分...

1   / (?> a* ) b/x    aaaaaaaaaaaaaaaaaaaa...
     ^
2   / (?> a* ) b/x    aaaaaaaaaaaaaaaaaaaa...
      ^^^^^^^^
3   / (?> a* ) b/x    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
          ^^
4   / (?> a* ) b/x    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
            ^
5   / (?> a* ) b/x    aaaaaaaaaaaaaaaaaaaaa...
               ^

因为加入了群组，所以这个过程比三个步骤多了两个步骤...

1   / a*+ b /x    aaaaaaaaaaaaaaaaaaaa...
     ^
2   / a*+ b /x    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
      ^^^
3   / a*+ b /x    aaaaaaaaaaaaaaaaaaaaa...
          ^

在IT技术中，你可以说a*b和(?:a*)b是相同的，但后者需要更多的步骤：

1   / (?: a* ) b/x    aaaaaaaaaaaaaaaaaaaa...
     ^
2   / (?: a* ) b/x    aaaaaaaaaaaaaaaaaaaa...
      ^^^^^^^^
3   / (?: a* ) b/x    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
          ^^
4   / (?: a* ) b/x    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac
            ^
5   / (?: a* ) b/x    aaaaaaaaaaaaaaaaaaaaa...

注意：即使在这里，你也可以看到regex101已经针对a*b的步骤进行了优化。
结论
占有量词和原子组的工作方式取决于如何使用它们。如果我采用正则表达式的例子并稍加调整： (?>a|b)*ac 可匹配 aabaac 但是 (?:a|b)*+ac 和 (?>(?:a|b)*)ac 无法匹配 aabaac。
我在regexhero.net上检查了性能问题。我所说的步骤差异是在a*b和(?>a*)b之间。在regex101.com上，当我们禁用优化时，存在差异。我正在尝试找出其原因。分别为67和133。 - vks
@vks 好的，但我不明白这如何改变我的答案步骤方面的内容。在性能方面，(?>a*)b是最快的，但不是`(?>a)*b。 - Jerry
这就是疑问所在。原子组的性能最快，但失败的步骤数更多。这正是我想要的 :( - vks
@vks 请阅读我的回答。我说：“需要注意的是，步骤数并不直接代表正则表达式的性能。这是一个因素，但不是最终决定因素。有更多的步骤是因为在进入组之前和之后，分解过程都有步骤…” - Jerry
@vks 再次从我的回答中解释，a*b 和 (?:a*)b 完全匹配，性能相同，但是 (?:a*)b 由于组的原因需要更多步骤。当你比较两个东西时，必须在相同的基础上进行比较（在这里，这两个正则表达式完全匹配）。 - Jerry
显示剩余2条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接