正規表現の実装方法
基本的には有限オートマトン(FA; Finite Automaton)として実装されることが多い。
文字を1文字読むことが状態遷移と同等と考えれば、有限オートマトンと考えることができる。
有限オートマトンが目的の状態に到達した時に、マッチしたと判定することができる。
目的の状態に到達しないまま文字が尽きた場合(なお、EOFも文字の一種とすることで同じ遷移の中で扱える)、あるいは何らかのアンマッチ状態に到達した時にアンマッチと判定することができる。
有限オートマトンは演算することができる。これにより簡約化(より単純な形式に変換すること)ができる。
理論的には、だいたい以下の方法で実装されている
NFA (非決定性有限オートマトン)
DFA (決定性有限オートマトン)
バックトラック(バックトラッキング)
NFAとDFAの違い
次の状態が必ず1つなのがDFA
次の状態が複数あり得るのがNFA
NFAから必ずDFAが作ることができるのは、「次はどれかだがまだ未確定」という状態を1つの状態として作り出すことができるから。
バックトラック方式
マッチしなかったら、別の候補を試す。
試す数(組み合わせ)が爆発的に増えるとその分速度が低下する。
人間が見ると自明に見えても、コンピュータは1文字ずつ地道に読むしかなく、その1文字が以前どう取り扱われたかを記憶して判断することができない。(できないことはないが、それ自体がデータアクセスを引き起こすため遅くなる。)
後方参照
以前現われた部分文字列と同じ文字列を検索する、という処理
例えば、(.) = $1 + 1 とすると、a = a + 1, b = b + 1 とマッチする。
先読み
期待する文字列かどうかを現在の文字位置より先まで読み込んで確認する。これは有限オートマトンの考え方からすると反則になってしまう。
そもそも有限オートマトンと読んだ文字ごとの遷移という考え方自体がたぶん間違い。(それをやりたいのは、数学をやりたい人であって、実務がやりたい人ではない)
結局の所、どうしたら早くできるのか?
バックトラックを減らす。可能であればなくす。
理論的に可能か?
判断結果により飛ばせる物は飛ばす。
abc のマッチに対して、ababc があった場合、2文字目からマッチし直すよりは3文字目からマッチし直すのが最速になる。
正規表現で可能か?
同じ処理はまとめる。
(ab|ac) であれば、a(b|c)とする。
NFA, DFA ではこれが簡単なので採用される。
アンマッチを早く探す。あり得ない事が早く判明すれば、さっさと次を探すのが早い。
残りの文字数よりマッチする文字数の方が長いなら、もうそれ以上マッチさせる理由がない。
想定される範囲内にマッチする文字以外の文字があれば、スキップしてもよい。
abcを検索する場合、abxabc とマッチさせる時には、xを見つけた時点で、xの次から検索すればよい。
任意文字が入ると困難になるかも?
組み合わせ爆発を防ぐようにする。
正規表現の仕組み上困難?
任意文字のマッチ(.)は本当のところどう解釈されるべきなのか?
1文字のみ(.)であれば、任意文字のままでよい。
長さ不定(.*)の場合、最長マッチとすると、「その次に続く文字列が現われる最後の文字列」を探す処理になる。(これがとても厄介)
a.*bcd とした時、abcdxbcdxbcdbcx は abcdxbcdxbcd としてマッチする。bcdを見つけただけで終らせられず、結局最後の最後まで読まないと確定できない。
巨大データの読み出しで大問題になる。
「bが見つかるまで伸ばす」にすると、結局バックトラック問題を引き起こす。
こう考えると、むしろ最短マッチの方が作りやすく運用しやすいはず。
「正規表現と言えば有限オートマトン」という「常識」が間違いを産み出しているのでは?
指定長さの任意文字の場合はどう実装されるべきか?
最大長から順にバックトラックするのが実装上は簡単。
2つ以上の長さ可変の任意文字が入ると、組み合わせが爆発しやすい。
バックトラックが起こる原因
頭から順に解釈してマッチさせる以上、最後の最後でアンマッチが発生すると、全部やり直しになる。
a*.*b のようにすると、人間が考えれば、0～任意個のaと、0～任意個の任意文字と、最後にbを見つければよい。
ここで問題なのは、任意文字にaとbが含まれるかどうなのかという問題。なぜか人間はその可能性を忘れてしまう。
機械的に考えれば、任意文字にaとbが含まれてしまうので、組み合わせが爆発してしまう。
最長マッチと最短マッチ
(最左)最長マッチは可能な限り長くマッチさせる。繰り返しがあれば、それをより長くする。
s<<<foo>>>m<<<bar>>>eに対して正規表現<.*>を適用すると<<<foo>>>m<<<bar>>>が得られる。(任意文字は<と>を含むため)
(最左)最短マッチは可能な限り短くマッチさせる。繰り返しがあっても見つけた最初の所で止める。
s<<<foo>>>m<<<bar>>>eに対して正規表現<.*?>を適用すると<<<foo>が得られる。
最長マッチの上で本来の期待通りに指定するには?
ほとんどの場合、任意文字と言いながら、利用者は本当の「任意文字」を期待していない。
HTMLのタグの検索のつもりで、<.*>という指定をしたりするが、これは期待通りにならない。
<.*>という指定は、pre<ta>ca</ta><tb>cb</tb>postとマッチさせると、<ta>ca</ta><tb>cb</tb>にマッチする。
期待通りにさせるには<[^>]*> (開きタグだけを検索するなら<[^/][^>]*>)とする必要がある。
DFA ではなぜダメなのか?
受け入れる文字があらかじめ完全に決定されているのが DFA
DFA はその分高速になるが、後方参照(PCRE の $1 のようなもの)は使えない。