朧の.Netの足跡
問合せ先:support@oborodukiyo.info サイト内検索はこちら
正規表現 バックトラックについて





.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-1の保存ステートです。これは途中経過で、.+が最後の.のところまで進んだところでそれ以上文字がないので"があるかチェックしますが文字がないので失敗します。 すると、先ほどの保存ステートを右側から順に戻って行っていきます。tのところに戻ってきて後ろの文字が"かチェックしますが、.であるので失敗します。 そしてまた左隣に戻ってiの次が"かチェックしますがtなので失敗します。
これを繰り返して!のところまで戻ってきて右隣りが"であることを見つけますので、ここで成功します。
得られる結果は、"This book is very fun." and "Read it. It's useful for you!"となります。

例1-1)He said "保存ステートT保存ステートh保存ステートi保存ステートs保存ステート 保存ステートb保存ステートo保存ステートo保存ステートk保存ステート 保存ステートi保存ステートs保存ステート 保存ステートv保存ステートe保存ステートr保存ステートy保存ステート 保存ステートf保存ステートu保存ステートn保存ステート.保存ステート"保存ステート 保存ステートa保存ステートn保存ステートd保存ステート 保存ステート"保存ステートR保存ステートe保存ステートa保存ステートd保存ステート 保存ステートi保存ステートt保存ステート.保存ステート 保存ステートI保存ステートt保存ステート'保存ステートs保存ステート 保存ステートu保存ステートs保存ステートe保存ステートf保存ステートu保存ステートl保存ステート 保存ステートf保存ステートo保存ステートr保存ステート 保存ステートy保存ステートo保存ステートu保存ステート!保存ステート"保存ステート 保存ステートI保存ステート 保存ステートi保存ステートn保存ステートt保存ステートe保存ステートn保存ステートd保存ステート 保存ステートt保存ステートo保存ステート 保存ステートb保存ステートu保存ステートy保存ステート 保存ステートi保存ステートt保存ステート.

次に例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 "L保存ステートa保存ステートd保存ステートy保存ステート 保存ステートG保存ステートa保存ステートg保存ステートa保存ステート, 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?" 保存ステートH保存ステートe保存ステート 保存ステートh保存ステートa保存ステートp保存ステートp保存ステートi保存ステートl保存ステートy保存ステート 保存ステートr保存ステートe保存ステートp保存ステートl保存ステートi保存ステートe保存ステートd保存ステート 保存ステート"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こでも良いのですが貪欲なので 一気に最後の"のところまで進みます。その時、他の選択肢の保存ステートは全ての文字の間に置かれます。
保存ステートL保存ステートa保存ステートd保存ステートy保存ステート 保存ステートG保存ステートa保存ステートg保存ステートa保存ステート,保存ステート 保存ステートT保存ステートh保存ステートe保存ステート 保存ステートP保存ステートr保存ステートe保存ステートs保存ステートi保存ステートd保存ステートe保存ステートn保存ステートt保存ステート,保存ステート 保存ステートa保存ステートn保存ステートd保存ステート 保存ステートw保存ステートh保存ステートi保存ステートc保存ステートh保存ステート 保存ステートi保存ステートs保存ステート 保存ステートg保存ステートr保存ステートe保存ステートa保存ステートt保存ステート?保存ステート"保存ステート 保存ステートH保存ステートe保存ステート 保存ステートh保存ステートa保存ステートp保存ステートp保存ステートi保存ステートl保存ステートy保存ステート 保存ステートr保存ステートe保存ステートp保存ステートl保存ステートi保存ステートe保存ステートd保存ステート 保存ステート"保存ステートL保存ステートa保存ステートd保存ステートy保存ステート 保存ステートG保存ステートA保存ステートG保存ステートA保存ステート!保存ステート"
つまり、アトミックグループの中だけを考える時はバックトラックがあるということです。 そして、そのままではアトミックグループ内にある[?]の部分が一致できないので左にバックしていって、「great?」の?にマッチして、アトミックグループの外に出て、その時に左側にある残りの保存ステートが全て捨てられます。









良いやや良い普通やや悪い悪い

投稿日時評価コメント