18

区切り文字（例<と>）の間でテキストを一致させるという一般的な問題には、2つの一般的なパターンがあります。

  • 貪欲*または+数量詞を次の形式START [^END]* ENDで使用する<[^>]*>、または
  • 怠惰*?または+?数量詞を次の形式START .*? ENDで使用し<.*?>ます。

どちらか一方を優先する特別な理由はありますか？

4

3 に答える 3

12

いくつかの利点：

[^>]*：

  • より表現力豊か。
  • /sフラグに関係なく改行をキャプチャします。
  • 一致を成功させるためにエンジンをバックトラックする必要がないため、より迅速に検討されます（[^>]エンジンは選択を行わないため、パターンを文字列と一致させる方法は1つだけです）。

.*?

  • 「コードの重複」はありません-終了文字は1回だけ表示されます。
  • 終了区切り文字が1文字を超える場合は、より単純になります。（この場合、文字クラスは機能しません）一般的な代替手段は(?:(?!END).)*です。END区切り文字が別のパターンである場合、これはさらに悪化します。
于 2011-08-29T08:18:19.477 に答える
7

1つ目はより明確です。つまり、一致するテキストの一部から終了区切り文字を確実に除外します。これは、2番目のケースでは保証されません（正規表現がこのタグ以外に一致するように拡張されている場合）。

例：と一致させようとする<tag1><tag2>Hello!と<.*?>Hello!、正規表現は一致します

<tag1><tag2>Hello!

一方、<[^>]*>Hello!一致します

<tag2>Hello!
于 2011-08-29T08:20:17.220 に答える
7

このような質問に取り組むときにほとんどの人が考慮しないのは、正規表現が一致するものを見つけることができない場合に何が起こるかです。 そのとき、キラーパフォーマンスの陥没穴が現れる可能性が最も高くなります。たとえば、Timの例を見てみましょう。ここでは、のようなものを探しています<tag>Hello!。何が起こるかを考えてみましょう：

<.*?>Hello!

正規表現エンジンはを検出し、<すぐに終了を検出しますが、は検出し>ません>Hello!。したがって、が続くaを.*?探し続けます。存在しない場合は、あきらめる前にドキュメントの最後まで移動します。次に、正規表現エンジンは別のを見つけるまでスキャンを再開し、再試行します。 それがどうなるかはすでにわかっていますが、正規表現エンジンは通常、そうではありません。ドキュメント内のすべてで同じリガマロールを通過します。次に、他の正規表現について考えます。>Hello!<<

<[^>]*>Hello!

前と同じように、からにすばやく一致しますが<、>に一致しませんHello!。に戻り<、終了して別ののスキャンを開始し<ます。最初の正規表現と同じようにすべてをチェック<しますが、ドキュメントが見つかるたびにドキュメントの最後まで検索するわけではありません。

しかし、それよりもさらに悪いです。あなたがそれについて考えるならば、.*?事実上、否定的な先読みと同等です。「次のキャラクターを消費する前に、正規表現の残りの部分がこの位置で一致しないことを確認してください」と言っています。言い換えると、

/<.*?>Hello!/

...と同等です：

/<(?:(?!>Hello!).)*(?:>Hello!|\z(*FAIL))/

したがって、実行しているすべての位置で、通常の試合の試みだけでなく、はるかに高価な先読みが行われます。（先読みは少なくとも1文字をスキャンする必要があるため、少なくとも2倍のコストがかかります。その後、.先に進んで1文字を消費します。）

（(*FAIL)Perlのバックトラッキング制御動詞の1つです（PHPでもサポートされています）。 |\z(*FAIL)「またはドキュメントの最後に到達してあきらめる」という意味です。）

最後に、否定文字クラスのアプローチには別の利点があります。（@Bartが指摘したように）数量詞が所有格のようには機能しませんが、フレーバーがそれをサポートしている場合は、所有格にすることを妨げるものは何もありません。

/<[^>]*+>Hello!/

...またはアトミックグループでラップします：

/(?><[^>]*>)Hello!/

これらの正規表現は、不必要にバックトラックすることがないだけでなく、バ​​ックトラックを可能にする状態情報を保存する必要もありません。

于 2011-08-29T09:50:18.833 に答える