5

入力データは次のとおりです。

                                *** INVOICE ***                                

                              THE BIKE SHOP                              
                      1 NEW ROAD, TOWNVILLE,                       
                          SOMEWHERE, UK, AB1 2CD                          
                        TEL 01234-567890  

 To: COUNTER SALE                                   No:  243529 Page: 1

                                                    Date: 04/06/10 12:00

                                                    Ref:    Aiden   

 Cust No: 010000

動作する正規表現は次のとおりです (オプション: singleline、ignorewhitespace、コンパイル済み) - すぐに一致し、グループが適切に入力されます。

\W+INVOICE\W+
(?<shopAddr>.*?)\W+
To:\W+(?<custAddr>.*?)\W+
No:\W+(?<invNo>\d+).*?
Date:\W+(?<invDate>[0-9/ :]+)\W+
Ref:\W+(?<ref>[\w ]*?)\W+
Cust

Cust No から「N」を rex に追加するとすぐに、入力の解析が永久にハングします。

\W+INVOICE\W+
(?<shopAddr>.*?)\W+
To:\W+(?<custAddr>.*?)\W+
No:\W+(?<invNo>\d+).*?
Date:\W+(?<invDate>[0-9/ :]+)\W+
Ref:\W+(?<ref>[\w ]*?)\W+
Cust N

「任意の文字」のようなものを追加すると:

\W+INVOICE\W+
(?<shopAddr>.*?)\W+
To:\W+(?<custAddr>.*?)\W+
No:\W+(?<invNo>\d+).*?
Date:\W+(?<invDate>[0-9/ :]+)\W+
Ref:\W+(?<ref>[\w ]*?)\W+
Cust .

それは機能しますが、固定文字を追加するとすぐに、rex が再びハングします。

\W+INVOICE\W+
(?<shopAddr>.*?)\W+
To:\W+(?<custAddr>.*?)\W+
No:\W+(?<invNo>\d+).*?
Date:\W+(?<invDate>[0-9/ :]+)\W+
Ref:\W+(?<ref>[\w ]*?)\W+
Cust ..:

些細なことを追加すると、それが倒れてしまう理由を誰かアドバイスできますか? なんらかのトレースを有効にして、一致するアクティビティを監視し、壊滅的なバックトラックでスタックしているかどうかを確認できますか?

4

3 に答える 3

8

ではRegexOptions.IgnorePatternWhitespace、パターン内の空白を無視するようにエンジンに指示しています。したがって、パターンに書き込むCust Noと、実際にはCustNo入力と一致しない を意味します。これが問題の原因です。

ドキュメントから：

デフォルトでは、正規表現パターンの空白は重要です。正規表現エンジンが入力文字列の空白文字に一致するように強制します。[...]

このRegexOptions.IgnorePatternWhitespaceオプションまたはxインライン オプションは、このデフォルトの動作を次のように変更します。

  • 正規表現パターンのエスケープされていない空白は無視されます。正規表現パターンの一部にするには、空白文字をエスケープする必要があります (例:\sまたは"\ ")。

Cust Noしたがって、モードでは の代わりに をIgnorePatternWhitespace記述する必要があります。Cust\ Noそうしないと、 と解釈されるからCustNoです。

于 2010-06-04T13:24:27.940 に答える
2

polygenelubricantsは、正規表現が失敗した理由をすでに説明しています。それがハングする理由は、壊滅的なバックトラックに遭遇しているためです。正規表現には、同じテキストにさまざまな方法で一致させることができる多くの部分があります。全体的な一致が失敗した場合、正規表現エンジンは、すべての順列を使い果たすか、スタックオーバーフローで中止されるまで、すべての可能な順列を試行します。

例：はと同じ文字に喜んで一致しますTo:\W+(?<custAddr>.*?)\W+。また、を使用しているため、は入力テキストの一部にクロスオーバーし、さらに進んでいきます。あなたの例では、「Cust」の後に「N」を追加するとどうなるかをRegexBuddyでテストしました。つまり、正規表現エンジンは1,000,000ステップ後に中止されます。.*?\WSingleline.*?No:...

これを回避するには、正規表現をより具体的にするか、（この場合はこれがより適切なオプションである可能性があります）「アトミックグループ」ですでに一致しているパーツを囲むことにより、正規表現エンジンがバックトラックしないようにする必要があります。

(?>\W+INVOICE\W+)
(?>(?<shopAddr>.*?)\W+To:)
(?>\W+(?<custAddr>.*?)\W+No:)
(?>\W+(?<invNo>\d+).*?Date:)
(?>\W+(?<invDate>[0-9/\ :]+)\W+Ref:)
(?>\W+(?<ref>[\w\ ]*?)\W+Cust)

これにより、入力と正規表現が一致しない場合に、正規表現がはるかに速く失敗する可能性があります。

于 2010-06-04T16:39:24.337 に答える
0

Tim Pietzcker は、壊滅的なバックトレースを回避しようとしているときに、ここで何かに取り組んでいます。.NET には、「所有量指定子」と呼ばれる欠落している機能があります。これは基本的に、正規表現が可能な限り貪欲になり、バックトレース時に何もあきらめないことを意味します。

たとえば、「abc」に [abc]+c という式を一致させる場合、成功します。[abc]+ は最初に 3 文字すべてに一致し、次に最後の c は行末に達したために失敗します。これにより、バックトラックが発生し、「ab」のみが一致し、一致が成功するために c が残ります。

「abc」で式 [abc]++c を一致させようとすると、失敗します。[abc]++ は最初に 3 文字すべてに一致し、次に最後の c は行末に達したために失敗します。ただし、今回は、ポーズ量指定子 (追加のプラス記号 +) のためにバックトラックはなく、式は一致しません。

Tim Pietzcker は、ポーズ量指定子を使用する代わりの方法を指摘しています。アトミック グループは、正規表現を破滅的なバックトレースから守ることができます。したがって、すべての実用的な目的において、所有表現 [abc]++c と原子表現 (?>[abc]+)c は同等です。

あなたは私に多くの時間を節約してくれました。ありがとうございました。

于 2011-03-07T17:53:58.630 に答える