8

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

令我大吃一惊

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

运行（匹配失败）比

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

（匹配成功）。为什么？？？？两者都应该首先吞噬所有的a，然后第二个立即成功，而第一个则必须一遍又一遍地回溯，以失败。

4

2 回答 2

8

Perl 正则表达式被优化为尽可能早地失败，而不是尽可能快地成功。在浏览大型日志文件时，这很有意义。

有一个优化首先寻找字符串的一个常数部分，在这种情况下，一个“浮动”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"

您可以使用编译指示debug选项获得此类输出。re

严格来说，找到borbb是不必要的，但它可以让匹配更早地失败。

于 2013-10-24T23:56:54.310 回答
6 
/a*bb/

基本上是

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

注意两者*。除了优化之外，它是二次的。在最坏的情况下，（所有的字符串a），对于长度为 N 的字符串，它会检查当前字符是否为aN*(N-1)/2 次。我们称之为 O(N 2 )。

值得在开始匹配之前扫描字符串 (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

    在这里，您可以看到该检查的动作。

于 2013-10-25T00:17:41.043 回答