計算理論の基礎 [原著第2版] 1.オートマトンと言語
例1.51
算術においては、演算の選択肢があるときは演算 ✕ を演算 + より先に行い、✕ は + に優先するという。よって、2 + 3 ✕ 4 においては、3 ✕ 4 を加算より先に行う。加算を先に行うためには、(2 + 3) ✕ 4 のように括弧を追加しなくてはならない。正規表現では、通常の順序を変えるための括弧が使われない限り、スター演算が最初に行われ、つぎに連結演算、最後に和集合演算が行われる。
つまり正規表現では、
- スター演算（*, +, ?, {m,n} などの量指定子がある部分）
- 連結演算（ab のように通常の文字リテラルやパターンが連結されている部分）
- 和集合演算（ab|cd のようにパイプによって or で指定された部分）
の順番で演算が行われると理解できる。
さて、僕たちが普段使っている正規表現エンジンもこの順番になっているのだろうか？と気になって、詳説 正規表現 第3版
4.2 マッチの基本原則
正規表現全般に当てはまる原則は次の2つしかない。
- 最初にマッチしたもの（最も左にあるもの）が優先される。
- 標準の量指定子（「*」、「+」、「?」、「{m,n}」）は欲張りである。
ふむ。実際の正規表現エンジンは確かにそうだ（散々使い倒してみれば嫌でも分かる）。
とにかくパターンの出だしの部分が何であれ、検索対象の文字列の中でとにかく最初にマッチする部分を見つけ出し、そこにアンカーを置くことから全てが始まる。
言ってみれば、前者はオートマトンの計算理論上の優先順位、後者は正規表現エンジン上（特にNFA – 非決定性有限オートマトンを採用したエンジン）の特性と観ることができる。
正規表現エンジンはとにかくパターンがマッチしなければ始まらないから、まずもってマッチできる箇所を探す。
標準の量指定子は貪欲だから、マッチできる限りのところまでマッチする。
標準の量指定子のマッチが尽きたら連結演算で消化できるリテラルやパターンにアンカーを置ける場所を探す。
和集合演算は or つまり選択肢が発生する = バックトラックが発生しやすいから後回しで処理される。
現実的な話をすれば、
- パターン内にリテラルで固定できる箇所があるなら固定したほうがいい。マッチの効率がぐっと上がる
- 貪欲な量指定子を避けて、控えめな量指定子を使える箇所がパターンの中にないか考えてみる
- 選択肢が少ないほどマッチは速い。だから無駄に | での和集合演算を多用しないほうがよい
Perl で例を書いてみよう。
文字列の中の「Copyright 20**.」（** には「12」とか「13」のような数字が入る）にマッチしたいとする。
表記として、「Copy right」だったり「Copy-right」だったりする可能性があるとしよう。
# $str に対象の文字列全体が入っている
# 「Copyright」「Copy right」「Copy-right」に
# 当たる部分全体を . と量指定子を使って表現してしまうと・・・
$str =~ m{.+ 20\d\d\.};
# なんと文字列の先頭から、半角スペースをひとつ置いて
# 「20\d\d\.」に着く当たるところまでがマッチしてしまう！
# この方が懸命だ（でも完全ではない）。
$str =~ m{Copy.+ 20\d\d\.};
# 上のやり方だと、マッチの先頭は「Copy」にアンカーが置かれるので
# ずいぶん改善したが、それでも、
# 「DON'T Copy this image. Copyright 2014. 」の
# アンダーラインで示したような部分があった場合にもマッチしてしまう。
# ちなみに $str =~ m{Copy.+? 20\d\d\.}; としたところで
# 結果は同じだ。
# 僕なりに改善してみると、こんな感じ
$str =~ m{Copy[^a-zA-Z]*?right 20\d\d\.};
「Copy」と「right」はリテラルとして固定できると分かっているなら、その間に入っちゃまずいもの（この場合アルファベット）を除外してやったのが [^a-zA-Z]*? の部分だ。
でもこれだって完璧じゃない。
もし誰かが居眠りしながら作成した文書があって、「Copy*[-)”6@@@*right 2012.」みたいになってたらマッチしてしまう（まぁあらぬ間違いを見付けられるから嬉しい副作用かも知れないけど・・・）。
堅実な方法は、
$str =~ m{Copy(?: |-)*?right 20\d\d\.};
のようにすることだろう。
(?: |-) このくらいの選択肢の少なさ（若しくは対象とする文字列がそれほど長文でない）なら、パターンの中に | で選択肢を植え込んでもそれほどスピードに差は出ない。
でも何かしらの理由で処理を早くしたいなら（Perl の場合だけど）この方が速い。
$str =~ m{Copyright 20\d\d\.}
or $str =~ m{Copy right 20\d\d\.}
or $str =~ m{Copy-right 20\d\d\.};
この例からも分かるように、何でもかんでも正規表現のパターンの中で解決するするよりも、プログラミング言語の力を借りちゃったほうが速いこともあるっていうのを時には思い出したほうがいい。
今回テストの為に書いたスクリプトを載せておく。
#! /usr/bin/perl
use warnings;
use strict;
sub execute_regex {
my ($str, $regex) = @_;
if ( $str =~ m{($regex)} ) {
print "Pattern: $regex\nMatched: $1\n\n";
return 1;
}
else {
return 0;
}
}
my $str = "DON'T Copy this image. Copy-right 2014.";
execute_regex($str, '.+ 20\d\d\.');
execute_regex($str, 'Copy.+ 20\d\d\.');
execute_regex($str, 'Copy[^a-zA-Z]*?right 20\d\d\.');
execute_regex($str, 'Copy(?: |-)*?right 20\d\d\.');
execute_regex( $str, 'Copyright 20\d\d\.' )
or execute_regex( $str, 'Copy right 20\d\d\.' )
or execute_regex( $str, 'Copy-right 20\d\d\.' );
実行結果:
$ regex_test.pl Pattern: .+ 20\d\d\. Matched: DON'T Copy this image. Copy-right 2014. Pattern: Copy.+ 20\d\d\. Matched: Copy this image. Copy-right 2014. Pattern: Copy[^a-zA-Z]*?right 20\d\d\. Matched: Copy-right 2014. Pattern: Copy(?: |-)*?right 20\d\d\. Matched: Copy-right 2014. Pattern: Copy-right 20\d\d\. Matched: Copy-right 2014.
