VB.NET で正規表現を使用した検索でフリーズする

質問

VB.NET(2003)ですが、Regexを使った正規表現での検索時に検索パターンによっては、プログラムがフリーズして固まります。なにか情報はないでしょうか？

VBプログラムファイル内のコメントを一気に検索するつもりで、 (".*?"|[^"'])*('.*?)\r\n とするとＯＫですが、
(".*?"|[^"']+)*('.*?)\r\n とするとフリーズします。(+を一つ足した）

プログラムは、
pMatches = Regex.Matches(src, pat)
If pMatches.Count = 0 Then
MsgBox("マッチしません")
End If
といった感じで、
src=対象テキストを全行取込んだ文字列、pat=検索パターンです。

フリーズは、pMatches.Countの部分で起こっているようです。
Matchesの変わりにMatchとNextMatchを使うと、順に検索結果が得られますが、最後の結果にNextMatchを実行したところで固まります。

フリーズ中、タスクマネージャで見ている限りではCPU=100%(HTでは50%)、となりますが、使用メモリー量は変化ありません。

回答No.2

UKY · ベストアンサー

いやいや、バックトラッキングを甘く見ちゃいけないと思いますよ。
(a+)* という正規表現では、対象の文字列が一文字増えるたびにパタンの数が 2 倍になります。
手元で軽く実験して見ました。
(a+)*b という正規表現に対して、文字列 aaa....aaac を検索させると、a が 20 文字のときで約 1 秒、21 文字で約 2 秒、22 文字で約 4 秒、23 文字で約 8 秒、24 文字で約 15 秒でした。
それに対し、(a)*b という正規表現では a が 1000 文字でも 1 秒掛かりませんでした。

実際、(a+)*b のパタン数は a が 24 文字のとき 2 の 24 乗で 16777216 通りですが、(a)*b の方は 1000 文字でも 1001 * 1002 / 2 で 501501 通りしかありません。

ちなみに、(?>(a+)*b) のようにバックトラッキングを無効にすると、数千文字でも一瞬でした。

お礼

どうも甘く見ていたようです。
「ちなみ・・」のように
(?>(".*?"|[^"']+))*('.*?)\r\n や
(".*?"|(?>[^"']+))*('.*?)\r\n とすると検索できました。

よく考えると、パターンそのものは、テキストの先頭から最後のコメント部分までは全部、最長での一致範囲なのでバックトラックが発生しないが、最後のコメントからテキスト末尾にパターンが一致しないことを判定するのにバックトラックが発生して長考しているようです。
(".*?"|[^"']+)*(('.*?)\r\n|$) としてもフリーズしませんでした。

もうちょっと細部を確認したいので、来週まで保留にさせてください。

補足

perlでも実行して同様にフリーズすることを確認しました。
「バックトラックで長考している」で納得できました。
(?> ..)などで回避するようにします。

回答ありがとうございました。

回答No.1

UKY

例えば、(a)*b という正規表現に対し aaac という文字列を検索させると、次のように処理が進みます。

(a)(a)(a)c
(a)(a)ac
(a)aac
aaac

* 演算子や + 演算子は繰り返しの回数を変化させて可能性のあるパタンを全て試します。上の例では繰り返しの回数は 4 パタンあります。
正規表現が (a)*b ではなく (a+)*b だと、次のようになります。

(aaa)c
(aa)(a)c
(aa)ac
(a)(aa)c
(a)(a)(a)c
(a)(a)ac
(a)aac
aaac

+ を足しただけで可能性のあるパタンの数が増えています。ソースコードのように何千文字もある文字列を検索すれば、パタンの数は莫大になります。つまり、検索処理が半永久的に終わらなくなるのです。

補足

回答ありがとうございます。
「処理時間が非常にかかっている」というもの十分考えられるとおもいますが、今回の検索パターンではバックトラックはあまり発生しないと思いますので、それほどの時間はかからないはずと思います。（勝手な思い込みかもしれませんが）

また、Matchで検索結果を順番に取得した場合、最後の検索結果までは特に問題なく実行できます。
フリーズするのは、最後のその次をNextMatchで取得する時に発生しているようです。

プログラムでは次のような感じです。
dim ma as match = Regex.Match(src, pat)
do while ma.Success
xxxxx
ma = ma.NextMatch
loop

最後の次をNextMatchで取得するとSuccess=Falseになっているはずですが、これを取得するタイミングで戻ってきません。
いくつかの対象テキストで試しましたが、このタイミングは同じでした。
（数行程度のテキストでは確かにＯＫでした。しかし３０行程度でもＮＧです）

具体的なテキストとプログラムがあったほうが良さそうなので、用意してみます。