.Netの正規表現はNFAタイプのエンジンを使っています。このNFAとは非決定性有限オートマトンの頭文字で、正規表現の書き方に依存した動作をするので
うまい書き方をすると早く動き、下手な書き方をすると遅くなります。
NFAエンジンは可能性を持つ2つのオプションの中でどちらかを選ばなければいけなくなると、片方を選んで後で戻ってくる時があれば(つまり先に選択した方でマッチできなければという意味なので、必ず全てのパターンが試されるということはないということがわかります。)
そこに戻れるように、もう片方も覚えておきます。
例1を見てみましょう。
例1)He said "This book is very fun." and "Read it. It's useful for you!" I intend to buy it.
正規表現1:".+"例1-1)He said "This book is very fun." and "Read it. It's useful for you!" I intend to buy it.
次に例2を使って考えてみましょう。
例2)I asked him "Lady Gaga, The President, and which is great?" He happily replied "Lady GAGA!"
正規表現:"[^",]+"
上の正規表現は、"で始まって、"と,以外の文字が続いて、"で終わる部分を抜き出すというものです。
これを例2に適用すると、最初の"を見つけると次の文字が"と,以外の文字か見てLであるので次の文字もそれら以外の文字か見ていきます。その時に別の選択("にマッチするかという選択肢)もあるよという目印を置いていきます。
そして、どんどん見ていくと例2-2の状態になります。,の手前まで来たところで[^",]+のマッチが終了し、そして"でないので失敗です。そして、左隣に一文字戻りますが、aなので"ではないので失敗です。これをどんどん戻って行って、
最後はLの直後まで戻ってみるが隣はaなのでこの正規表現はここの部分は失敗です。
例2-2)I asked him "Lady Gaga, The President, and which is great?" He happily replied "Lady GAGA!"
先ほど失敗した,のところまで進んでスペースから再開します。"ではないのでどんどん進んで行って?の隣の"を見つけます。そして、右隣りもスペースなので[^",]+がどんどん進んで行って例2-3の状態になります。そして、repliedの後の"で[^",]+の部分がマッチしないので次の"にマッチするので、マッチが成功です。
よって結果は" He happily replied "となります。
例2-3)I asked him "Lady Gaga, The President, and which is great?" He happily replied "Lady GAGA!"
アトミックグループの場合はまた違います。
アトミックグループは貪欲で、バックトラックしません。つまり、別の選択肢を捨ててしまいます。例3を見てみましょう。
例3)I asked him "Lady Gaga, The President, and which is great?" He happily replied "Lady GAGA!"
正規表現:"(?>.*)[?]"
上記の正規表現を使うと、結果から言うと一致するものはありません。詳しく見ていきましょう。
正規表現の最初の"は最初に出てくる"でまず止まります。するとアトミックグループ((?>...)の部分)に入ります。正規表現が.*なので最後まで一致してしまいます。アトミックグループを出たところで別の選択肢であるは、アトミックグループの中については全て捨てられます。
ここで[?]"に一致できる部分はないので、マッチは失敗します。
では、次の正規表現ではどうでしょうか。
正規表現:"(?>.*[?])"
結果から言うと、"Lady Gaga, The President, and which is great?"が一致する部分です。このうち、アトミックグループの部分に一致するのは、
Lady Gaga, The President, and which is great?
ですが、アトミックグループ内だけの動作を見ると、おそらく次のようです。
アトミックグループ内に入ってきたときは、正規表現エンジンが注目しているのはLの左側です。アトミックグループの最初の正規表現部分が.*なので、一致するのが0こでも良いのですが貪欲なので
一気に最後の"のところまで進みます。その時、他の選択肢のは全ての文字の間に置かれます。
Lady Gaga, The President, and which is great?" He happily replied "Lady GAGA!"
つまり、アトミックグループの中だけを考える時はバックトラックがあるということです。
そして、そのままではアトミックグループ内にある[?]の部分が一致できないので左にバックしていって、「great?」の?にマッチして、アトミックグループの外に出て、その時に左側にある残りのが全て捨てられます。
良い | やや良い | 普通 | やや悪い | 悪い |
---|
投稿日時 | 評価 | コメント |
---|