为什么Perl回溯匹配失败似乎比匹配成功花费更少的时间？

Question

我有一个巨大的文件aab.txt,其内容是aaa... aab.

令我惊讶的是

perl -ne '/a*bb/' < aab.txt

运行(匹配失败)比快

perl -ne '/a*b/' < aab.txt

(匹配成功).为什么？？？？两者都应首先吞噬所有的a,然后第二个立即成功,而第一个将不得不一遍又一遍地回溯,失败.

Answer 1

Perl regexes被优化为尽可能早地失败,而不是尽可能快地成功.在浏览大型日志文件时,这很有意义.

有一个优化,首先查找字符串的常量部分,在这种情况下,"浮动" b或bb.这可以相当有效地检查,而不必跟踪回溯状态.没有bb找到,比赛就在那里中止.

不是这样的b.找到浮动子字符串,并从那里构造匹配.这是正则表达式匹配的调试输出(程序是"aaab" =~ /a*b/):

Compiling REx "a*b"
synthetic stclass "ANYOF_SYNTHETIC[ab][]".
Final program:
   1: STAR (4)
   2:   EXACT <a> (0)
   4: EXACT <b> (6)
   6: END (0)
floating "b" at 0..2147483647 (checking floating) stclass ANYOF_SYNTHETIC[ab][] minlen 1 
Guessing start of match in sv for REx "a*b" against "aaab"
Found floating substr "b" at offset 3...
start_shift: 0 check_at: 3 s: 0 endpos: 4 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "a*b" against "aaab"
Matching stclass ANYOF_SYNTHETIC[ab][] against "aaab" (4 bytes)
   0 <> <aaab>               |  1:STAR(4)
                                  EXACT <a> can match 3 times out of 2147483647...
   3 <aaa> <b>               |  4:  EXACT <b>(6)
   4 <aaab> <>               |  6:  END(0)
Match successful!
Freeing REx: "a*b"

您可以使用pragma debug选项获得此类输出re.

严格来说,找到b或bb不必要,但它允许比赛更早失败.

Answer 2

/a*bb/

基本上是

/^(?s:.*?)a*bb/

注意这两个*.除了优化之外,它是二次的.在最坏的情况下,(一串全部a),对于长度为N的字符串,它将检查当前字符是否为aN*(N-1)/ 2次.我们称之为O(N ²).

在开始匹配之前,有必要扫描字符串(O(N))以查看它是否可能匹配.匹配需要更长的时间,但它将无法更快地匹配.这就是Perl所做的.

当您运行以下

perl -Mre=debug -e"'aaaaab' =~ /a*bb/"

1. 您将获得有关模式编译的信息:

   Compiling REx "a*bb"
   synthetic stclass "ANYOF{i}[ab][{non-utf8-latin1-all}]".
   Final program:
      1: STAR (4)
      2:   EXACT <a> (0)
      4: EXACT <bb> (6)
      6: END (0)
   floating "bb" at 0..2147483647 (checking floating) stclass ANYOF{i}[ab][{non-utf8-latin1-all}] minlen 2
   

   最后一行表示它将bb在开始匹配之前在输入中搜索.

2. 您将获得有关模式评估的信息:

   Guessing start of match in sv for REx "a*bb" against "aaaaab"
   Did not find floating substr "bb"...
   Match rejected by optimizer
   

   在这里,您会看到检查操作.