VB.NET(2003)ですが、Regexを使った正規表現での検索時に検索パターンによっては、プログラムがフリーズして固まります。なにか情報はないでしょうか?
VBプログラムファイル内のコメントを一気に検索するつもりで、 (".*?"|[^"'])*('.*?)\r\n とするとOKですが、
(".*?"|[^"']+)*('.*?)\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ベストアンサー
- 回答日時:
いやいや、バックトラッキングを甘く見ちゃいけないと思いますよ。
(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) のようにバックトラッキングを無効にすると、数千文字でも一瞬でした。
この回答への補足
perlでも実行して同様にフリーズすることを確認しました。
「バックトラックで長考している」で納得できました。
(?> ..)などで回避するようにします。
回答ありがとうございました。
どうも甘く見ていたようです。
「ちなみ・・」のように
(?>(".*?"|[^"']+))*('.*?)\r\n や
(".*?"|(?>[^"']+))*('.*?)\r\n とすると検索できました。
よく考えると、パターンそのものは、テキストの先頭から最後のコメント部分までは全部、最長での一致範囲なのでバックトラックが発生しないが、最後のコメントからテキスト末尾にパターンが一致しないことを判定するのにバックトラックが発生して長考しているようです。
(".*?"|[^"']+)*(('.*?)\r\n|$) としてもフリーズしませんでした。
もうちょっと細部を確認したいので、来週まで保留にさせてください。
No.1
- 回答日時:
例えば、(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になっているはずですが、これを取得するタイミングで戻ってきません。
いくつかの対象テキストで試しましたが、このタイミングは同じでした。
(数行程度のテキストでは確かにOKでした。しかし30行程度でもNGです)
具体的なテキストとプログラムがあったほうが良さそうなので、用意してみます。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Visual Basic(VBA) ファイル全てを .xlsm に変更したところ、プログラムが途中で落ちてしまっています 17 2022/12/07 12:03
- Excel(エクセル) PHPプログラムをエクセルに張り付けると検索ボックスがでてくる! 3 2022/05/08 07:10
- Visual Basic(VBA) ユーザーフォーム「frm_基本❶」を立ち上げると新規で入力する行数を右下のNoとして表示しています。 1 2023/03/16 19:02
- PHP htmlspecialcharsが機能していないです。 バグですか? 1 2022/04/05 01:22
- Visual Basic(VBA) ユーザーフォームの表示を追加したい 2 2023/03/26 23:18
- Visual Basic(VBA) 検索のユーザーフォームの表示について 1 2023/03/27 23:31
- Visual Basic(VBA) このVBAでExcelアプリケーションを作成は必要ですか? 3 2023/07/19 21:13
- Excel(エクセル) vba 転記するときの最終行について 2 2022/09/03 09:31
- PHP ここでの ②if($su_d<>"")の比較演算子 を使う理由は 1 2022/03/26 02:33
- Excel(エクセル) VBAについて 3 2022/06/19 18:19
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正規表現 秀丸エディタ 行頭か...
-
vbaの正規表現で、マッチした一...
-
非決定性オートマトンから正規...
-
最適なスクリプト言語は何でし...
-
メールアドレスの正規表現について
-
MFCで正規表現
-
VB2005で、正規表現を使いたい
-
正規表現で「)」がメタ文字の理...
-
URLを正規表現に変換したい
-
C言語のコメントを「正規表現」...
-
wordの何も書かれていない2ペー...
-
PS4コントローラーをPCでゲーム...
-
エクセルでアルファベットか数...
-
Chr(13)とChr(10)の違いは?
-
EBCDIC⇒SJIS変換の方法
-
EXCELで=より左の文字を一括で...
-
文字列からタブコードを取り除...
-
Excelで指数表現しないようにす...
-
VBAでの Replace関数で、ワイル...
-
Excelで3E8を3.00E+8にしない方...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正規表現 秀丸エディタ 行頭か...
-
正規表現でAND検索はできる...
-
vbaの正規表現で、マッチした一...
-
メールアドレスの正規表現について
-
文章中全ての半角カッコ ( の...
-
正規表現です。括弧内にある複...
-
Perl 数値にスラッシュを入れる...
-
[正規表現] 数字範囲をヒット...
-
正規表現でシングルクォーテー...
-
[VBS] テキストファイルから任...
-
C言語にパターンマッチってない...
-
MFCで正規表現
-
Mで始まりuで終わる文字列
-
C言語のコメントを「正規表現」...
-
正規表現でカウントアップ(?)す...
-
第二水準漢字が含まれるか?
-
特定タグ以外を変換したい
-
正規表現で囲まれた部分の文字列
-
grepの正規表現での最短マッチ...
-
1行~複数行をまとめる正規表現
おすすめ情報