C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[5]: Regex.Replaceの不明な動作


(過去ログ 30 を表示中)

[トピック内 6 記事 (1 - 6 表示)]  << 0 >>

■14328 / inTopicNo.1)  Regex.Replaceの不明な動作
  
□投稿者/ men (1回)-(2008/02/15(Fri) 11:27:10)

分類:[.NET 全般] 

はじめましてmenと申します。

VS2005C#で開発をしています。

下記の文の中のメールアドレス部分をリンクさせる処理をしているのですが、inputString(String型)に
「ではまた...........................................m(__)m」
のようにドット(.)が連続した値を入れて処理をするとCPU使用率が100%になり、最終的にタイムアウトになります。
ドットは上記の半分くらいなら正常に動作します。
どうかご教授お願いします。


public const string VALID_MAIL_ADDRESS_PATTERN =
@"([a-zA-Z_0-9!#$%&'*+/=?^`{|}~.-](?:[a-zA-Z_0-9!#$%&'*+/=?^`{|}~.-]|\.(?=[a-zA-Z_0-9!#$%&'*+/=?^`{|}~.-])){0,63}
@(?:[a-zA-Z0-9]\.|[a-zA-Z0-9][a-zA-Z0-9-]*[a-zA-Z0-9]\.)+[a-zA-Z]{2,6})";

Regex.Replace(inputString, MailFactory.VALID_MAIL_ADDRESS_PATTERN, "(※リンク作成aタグ$1使用)", RegexOptions.IgnoreCase);
引用返信 編集キー/
■14342 / inTopicNo.2)  Re[1]: Regex.Replaceの不明な動作
□投稿者/ やじゅ (165回)-(2008/02/15(Fri) 16:32:09)
No14328 (men さん) に返信
> のようにドット(.)が連続した値を入れて処理をするとCPU使用率が100%になり、最終的にタイムアウトになります。
> ドットは上記の半分くらいなら正常に動作します。
>

何を知りたいのか分かりませんが、Regex.Replaceの不具合かも知れませんね。
何はともあれ、正常に動作しないのであれば、先に連続したドット(.)の数を
調べてエラーにしてしまえばいいのではないですか。

メールアドレスとしたら例外パターンですから。
引用返信 編集キー/
■14344 / inTopicNo.3)  Re[2]: Regex.Replaceの不明な動作
□投稿者/ れい (425回)-(2008/02/15(Fri) 17:13:29)
何をしたいのかよくわかりませんが、
メールアドレスにマッチさせたいなら
正規表現が間違っていますね。

この表現だと重くても当然です。
うまく一致しないメールアドレスも出てきてしまうと思います。

「文字のエスケープ」という項目がMSDNにあると思いますので
そちらを参考に表現を直したほうがいいでしょう。
引用返信 編集キー/
■14351 / inTopicNo.4)  Re[3]: Regex.Replaceの不明な動作
□投稿者/ men (3回)-(2008/02/15(Fri) 18:38:36)
ご返答ありがとうございます。

情報が不足していましたが、これはブログを読み込む画面での処理です。
ブログ内容にアドレスが書き込まれていた場合にリンク付けしています。

他にも何万件のブログがありますが、この「ではまた...........................................m(__)m」を含むブログ
だけがRegex.Replaceをするとおかしな動作を起こしています。

やじゅ さんがおっしゃってるようにRegex.Replaceの不具合だと思います。
ありがとうございました。
引用返信 編集キー/
■14358 / inTopicNo.5)  Re[4]: Regex.Replaceの不明な動作
□投稿者/ れい (426回)-(2008/02/15(Fri) 20:54:55)
No14351 (men さん) に返信
> やじゅ さんがおっしゃってるようにRegex.Replaceの不具合だと思います。

違います。
不具合ではありません。

その正規表現では、ほとんど全ての正規表現エンジンで同じ症状を示すはずです。
もしくは、そもそもマッチングまでいかずにエラーを出します。
その表現でもすばやく動作するほど最適化された正規表現エンジンを作ることも理論上可能ですが、見たことがありません。

指定した正規表現が何に一致するのか、
きちんと理解しないとバグを産みます。
また、正規表現自体がどう動作しているのか、
きちんと理解していないと今回のように「おかしい」ように見える場合もあります。

> 他にも何万件のブログがありますが、この「ではまた...........................................m(__)m」を含むブログ
> だけがRegex.Replaceをするとおかしな動作を起こしています。

1000件でうまく動くからOKとか、10000件でうまく動くからOKとか、
そういう質のコードでいいのでしたら適当でよいと思いますが。

つい最近も正規表現の有用性が話題になりましたので、
誰かのために途中まで適当に書いておくと。

正規表現というのは文字列から状態遷移図を作成し、
そこに文字列を流し込むという、オートマトンです。
タイプに応じてNFA、DFA、などがありますが、.Netは基本的にDFAタイプで、様々な拡張をしているようです。

たかが状態遷移図ですから、高度なことを考えてくれるわけではありません。
状態遷移図どおりに遷移していくだけです。
ですから、正規表現から生成される遷移図が複雑であれば時間がかかりますし、
流し込む文字列によって終状態まで流れる時間も変わります。

.Netはバックトラックが可能で、単純な表現で非常に複雑な遷移を生成可能です。
また、DFAをNFAに変換せずDFAのまま流しますので、
どんなに再帰が深くても正規表現のコンパイルエラーにはなりません。

今回の正規表現は、より単純化すると
"(a|a(?=a)){1000}b"
のようになります。
この表現から作られる遷移図に
"aaaaaaaaaaaaaaaaaaaaaaaa"
みたいな文字列を流し込むと2の文字数乗のオーダーで時間がかかります。
どうしてそのようになるのかは…余白が足りないので省略です。
状態遷移図を描いてみるとわかります。
そして、それはほぼ必至です。

#「文字数からして絶対足りないじゃないか」と言えるのは我々がNPを解ける頭脳を持ってるからです。

この問題は"(?="に限りません。
バックトラックや量指定子、代替演算子などを組み合わせると
比較的簡単に大変な状態遷移図を作れてしまいます。

NFAタイプの正規表現エンジンでは、
正規表現文字列をコンパイルする時点で状態遷移図がメモリに収まらなくなるのでエラーになりますが、
DFAでは文字列を流し込むまでわかりません。

ですので、正規表現を扱うのであれば、
何をどう一致させたいのか、それには正規表現エンジンはどういう振る舞いをしているのか、
それをきちんと考えなければいけません。

長い正規表現が嫌われるのも、
きちんとエスケープされてない正規表現が嫌われるのも、
正規表現が使えないという人が出るのも、ある程度当然だと思います。

ですので、正規表現を使うのであれば、綺麗に分かりやすく書く必要があります。
.Netでは"(#"でコメントが使えますし、
IgnorePatternWhitespaceを使えば任意の位置に空白を入れられます。
これらを活用するとよいと思います。
引用返信 編集キー/
■14432 / inTopicNo.6)  Re[5]: Regex.Replaceの不明な動作
□投稿者/ men (4回)-(2008/02/18(Mon) 16:24:16)
No14358 (れい さん) に返信

ありがとうございます。
私がまだまだ勉強不足でした。

れいさんの意見を参考に勉強して、もう1度正規表現を検討したいと思います。

ありがとうございました。
解決済み
引用返信 編集キー/


トピック内ページ移動 / << 0 >>

このトピックに書きこむ

過去ログには書き込み不可

管理者用

- Child Tree -