regexp - possessive quantifier (独占的|絶対最大)量指定子とは何か?

入門正規表現
岩谷宏

ちがうよ!バグじゃないよ!

404 Blog Not Found:perl - Encode-2.31 Released, 2.30 zapped, regexp bug in 5.10.0

ちょっと調べてみると....

% perl5.10.0  -le 'print "perl" =~ /^\w{1,8}+$/'
1
% perl5.8.8   -le 'print "perl" =~ /^\w{1,8}+$/'
Nested quantifiers in regex; marked by 
 <-- HERE in m/^\w{1,8}+ <-- HERE $/ at -e line 1.

というわけで、Perl 5.10.0 の bug を偶然にも踏んでいたようです。

これは possessive quantifier というもの。「入門正規表現」は「独占的量指定子」、「詳説 正規表現 第3版」は「絶対最大量指定子」と訳しています。Javaには以前からあったものですが、Perlでは5.10から入りました。

どういうものかというと、こういうものです。

NAME regular expression regex regexp - search.cpan.org

By default, when a quantified subpattern does not allow the rest of the overall pattern to match, Perl will backtrack. However, this behaviour is sometimes undesirable. Thus Perl provides the "possessive" quantifier form as well.

    *+     Match 0 or more times and give nothing back
    ++     Match 1 or more times and give nothing back
    ?+     Match 0 or 1 time and give nothing back
    {n}+   Match exactly n times and give nothing back (redundant)
    {n,}+  Match at least n times and give nothing back
    {n,m}+ Match at least n but not more than m times and give nothing back

greedy quantifiers (最大量演算子)と似ていますが、最大の違いはバックトラックしないということです。例を説明しましょう。まず以下の表現を考えてみます。

"backtracking" =~ /([a-z]+)(ing)/;

このmatchは成功し、$1, $2はそれぞれbacktrack, ingとなります。この時 regexp エンジンは以下のような挙動を示します。

backtracking
^^^^^^^^^^^^ まずここまでmatch。でも"ing"がみつからない
backtracking
^^^^^^^^^^^< まだ見つからない
backtracking
^^^^^^^^^^<< まだ見つからない
backtracking
^^^^^^^^^<<< 見つかった!

要するに、見つけなおしているわけです。

次に、以下の例を考えてみましょう。

"backtracking" =~ /([a-z]++)(ing)/;

今度のmatchは失敗します。なぜなら[a-z]++はbacktrackingまでmatchした後、後戻りしないためingが見つからないからです。

"backtracking" =~ /([a-z]++)(?:ing)?/;

とすると、$1がbacktrackingとなってこのことがよく理解できます。

これに対して、例えば

'<img alt="backtrack" src="bt.png">' =~ /"([^\"]+)"/;

と

'<img alt="backtrack" src="bt.png">' =~ /"([^\"]++)"/;

は、どちらもbacktrackを見つけますが、後者の方が高速です。

実はこの量指定子は、以下の構文糖衣でもあり、以前のバージョンのPerlでも右に書き直すことで利用yすることが出来ます。

NAME regular expression regex regexp - search.cpan.org

    Quantifier Form     Bracketing Form
    ---------------     ---------------
    PAT*+               (?>PAT*)
    PAT++               (?>PAT+)
    PAT?+               (?>PAT?)
    PAT{min,max}+       (?>PAT{min,max})

この possessive quantifier に関しては、「入門正規表現」P. 38 と、「詳説 正規表現 第3版」の P. 247 で議論していますが、この点に関しては前者の方が充実した解説となっています。両方とも読んでいたので、存在は知っていたのですが Perl 5.10 に入ったことは失念していました。

Dan the Regular Expressionist

Comments

うーん、、、possessive quantifierってのを初めて知ったから
弾ちゃんの例を参考にどのくらい高速になるか計測してみたけど
計測毎に順位が変わっちゃう程度の誤差しかないな。
計測方法が間違ってるのかな？



ソース
----
#!/usr/local/bin/perl-5.10.0
require 5.010_000;
use feature qw(:5.10);
use strict;
use warnings;
use Benchmark qw(:all);
use Path::Class;
my $filepath = file "/path/to/sample.html";
my $fh = $filepath->open("<") or die "$!: $filepath";
$fh->binmode(":utf8");
my $str = do { local $/; <$fh> };
my $count = 50000000;
my @codes = (
'<([^>]+)>' => sub {
$str =~ /<([^>]+)>/gs;
return ();
},
'<([^>]+?)>' => sub {
$str =~ /<([^>]+?)>/gs;
return ();
},
'<([^>]++)>' => sub {
$str =~ /<([^>]++)>/gs;
return ();
}
);
my $result = timethese($count, { @codes });
cmpthese($result);
__END__



計測結果
----
Benchmark: timing 50000000 iterations of <([^>]+)>, <([^>]++)>, <([^>]+?)>...
<([^>]+)>: 42 wallclock secs (42.09 usr + 0.35 sys = 42.44 CPU) @ 1178133.84/s (n=50000000)
<([^>]++)>: 43 wallclock secs (42.27 usr + 0.29 sys = 42.56 CPU) @ 1174812.03/s (n=50000000)
<([^>]+?)>: 55 wallclock secs (52.97 usr + 0.44 sys = 53.41 CPU) @ 936154.28/s (n=50000000)
Rate <([^>]+?)> <([^>]++)> <([^>]+)>
<([^>]+?)> 936154/s -- -20% -21%
<([^>]++)> 1174812/s 25% -- -0%
<([^>]+)> 1178134/s 26% 0% --

Posted by 通りすがりのPerler at 2009年02月19日 06:20