正規表現に繰り返しグループが含まれている場合、例えば^(one|two)*done$グループの繰り返しごとに試す2つの代替案があります。理論的には、この正規表現は、任意の長さの文字列に一致する必要があります。oneoneone…done。実際には、バックトラッキング正規表現エンジンは、ある時点で諦めざるを得なくなるでしょう。

正規表現エンジンが再帰アルゴリズムを使用する場合、グループの繰り返しごとに、エンジンのコールスタックへの呼び出しが追加されます。エンジンは、実際に行う必要のある繰り返しの回数が使用可能なスタック領域を超えると、諦めるか、クラッシュすることさえあります。

エンジンが再帰的でなくても、グループのマッチング試行が各繰り返しでどこから開始されたかを追跡する必要があります。これは、正規表現の残りの部分が一致しなかった場合にエンジンがバックトラックできるようにするために必要です。次のものとの一致を試みる場合oneoneoneエンジンはグループを3回繰り返します。繰り返しごとに、量指定子のバックトラック位置を保存します。代替演算子も、試行ごとにバックトラック位置を保存します。3回の繰り返しの後done文字列の最後に一致しません。ここで、エンジンは6つのバックトラック位置を逆順にたどります。それは試みますtwo代替演算子の各バックトラック位置で。それは試みますdone量指定子の各バックトラック位置で。プロセスは完全に線形です。繰り返される文字列でもone正規表現は、文字列の最後にdoneがあるかどうかによって、即座に一致するか、一致に失敗します。

ただし、この正規表現を繰り返す文字列に使用する場合one数百万回の場合、すべてのバックトラック位置を記憶しようとしてメモリ不足になるのを防ぐために設計された正規表現エンジンの制限に遭遇する可能性があります。これにより、エンジンが非常に長い一致を見つけることができなくなる可能性があります。

上記の例では、キャプチャグループを使用することで、さらに事態が悪化しています。一致が成功すると、キャプチャグループは最後にoneまたはtwo文字列の中に保持します。ただし、マッチング試行中は、oneまたはtwoの最新の一致も保持します。これにより、グループの反復ごと、およびグループにバックトラックするたびに、正規表現エンジンに追加の作業が発生します。

非キャプチャおよびアトミックグループで最適化する

正規表現エンジンが行う必要のある作業量を減らすために、この正規表現を最適化できます。これらは、すべての正規表現に適用するのに適した手法です。パフォーマンスの違いがほとんど測定できない短い文字列でのみ正規表現を使用する場合でも、それらを優れたコーディング習慣として扱う必要があります。

まず第一に、本当に正規表現一致の一部をキャプチャしたい場合にのみキャプチャグループを使用してください。そうでない場合は、常に非キャプチャグループを使用できます。後方参照を持たないキャプチャグループを非キャプチャグループに変換しても、正規表現が一致することになっている内容は決して変わりません。だから^(?:one|two)*done$が最初の最適化です。

この場合、2つの選択肢は相互に排他的です。twoは、oneがすでに一致している位置では決して一致しません。したがって、そのバックトラックはすべて不要です。アトミックグループを使用することで、正規表現エンジンにそれを伝えることができます。^(?>one|two)*done$。これで、正規表現エンジンは、グループを繰り返すたびに、代替演算子のバックトラック位置を破棄します。それはもはや試みませんtwoの位置でoneがすでに一致しました。

所有格量指定子で最適化する

ただし、量指定子*はまだバックトラックします。^(?>one|two)*done$はまだ試みますdoneのすべての位置でoneは、量指定子がバックトラックしたように一致しました。これを停止するには、量指定子を所有格にすることができます。^(?>one|two)*+done$。この正規表現は、まったくバックトラックしません。

この正規表現が実際に任意の長さのoneoneone…doneシーケンスに一致できるかどうかは、正規表現エンジンが所有格量指定子をどのように実装しているかによって異なります。所有格量指定子がバックトラック位置をまったく保存しない場合は、可能です。ただし、一部の正規表現フレーバーでは、所有格量指定子は^(?>(?>one|two)*)done$と書く別の方法です。その場合、量指定子はまだすべてのバックトラック位置を保存し、正規表現エンジンが外側のアトミックグループを終了するときにそれらを破棄するだけです。これはdoneが一致に失敗した場合、パフォーマンスが向上します。ただし、量指定子が保存できるバックトラック位置の数によって正規表現エンジンが制限されている場合、長い一致を許可しません。

不要なグループを排除する

キャプチャグループを非キャプチャグループまたはアトミックグループに変換するよりもさらに良いのは、不要なグループを削除することです。正規表現の演算子の優先順位を理解していないため、正規表現トークンを不必要にグループ化することがあります。代替演算子は、すべての演算子の中で最も低い優先順位を持っています。正規表現またはそれを含むグループ内で、その左側にあるすべてと右側にあるすべての間で代替を行います。量指定子は優先順位が高くなります。直前のトークンまたはグループのみを繰り返します。

だからone|two*は一致しますone, tw, two, twoo, twoooなど。最後のoだけでなく、代替を繰り返すためにグループが必要でした。ただし、選択肢の周りに余分なグループは必要ありません。(?:(?:one)|(?:two))*の2つのネストされたグループは不要です。

(?:[ab])+にも不要なグループがあります。文字クラスは、単一の正規表現トークンとして扱われます。量指定子はそれを直接繰り返すことができます[ab]+.

これらの不要なグループがどれほど影響を与えるかは、正規表現エンジンによって異なります。非キャプチャグループを使用するというアドバイスに従った場合、エンジンは不要なグループを最適化できる可能性があります。ただし、不要なキャプチャグループがある場合は、それを行うことはできません。正規表現エンジンは、後でキャプチャグループによって一致したテキストを取得する必要があるかどうかを判断できないため、削除できません。

単一のトークンを繰り返す

理論的には、^(?:a|b|c)+$と^[abc]+$は同じです。実際には、ほとんどのバックトラックエンジンは後者の方がはるかに高速に実行されます。文字クラスは、両方の文字を同時に試すことができます。代替演算子のように他の文字を試すためにバックトラックする必要はまったくありません。文字クラスの各反復は、正確に1つの文字と一致します。量指定子はバックトラックする必要があるかもしれませんが、それを行うためにバックトラック位置は必要ありません。反復回数を覚えておくだけで済みます。文字列内の1文字を後方にステップバックし、反復回数をデクリメントするだけで、バックトラックできます。これにより、^[abc]+$は任意の長さの文字列に一致できます。

"(?:[^"]|\\.)*"は、バックスラッシュでエスケープされている場合、二重引用符を含む可能性のある二重引用符付きの文字列に一致する単純なソリューションです。ドットがそれらに一致すると仮定して、改行を許可します。

上記の正規表現は、すべての二重引用符付き文字列に一致し、それ以外には何も一致しないという意味で正しいです。ただし、パフォーマンスが低いため、単純です。少なくとも非キャプチャグループを使用しています。2つの選択肢を反転させた場合、アトミックグループを使用できます（正規表現エンジンは貪欲であることを思い出してください）。ただし、正規表現エンジンにバックトラック位置をまったく保存しない所有格量指定子がない限り、文字列内の文字ごとにグループを繰り返している限り、数百万文字の長さの二重引用符付き文字列に一致させることはできません。

この正規表現を最適化するには、否定された文字クラスを繰り返す必要があります"(?:[^"\\]+|\\.)*"。これにより、正規表現は文字列内のエスケープされていない文字の実行をすばやく照合できます。エスケープされた文字よりもそれらの方がはるかに一般的であるため、正規表現エンジンが記憶する必要のあるバックトラック位置の数が大幅に減少します。外側のグループは、エスケープされていない文字の実行ごとに1回、およびエスケープされた文字ごとに1回のみ繰り返されます。閉じる引用符が一致しなかった場合、2つの量指定子は引き続きバックトラックします。ただし、ほとんどの反復は、はるかに高速にバックトラックできる内側の量指定子の反復になります。

否定された文字クラスにバックスラッシュが含まれるようになったことに注意してください。これにより、2つの選択肢が相互に排他的になることが保証されます。これは不可欠です。破滅的なバックトラックのトピックに注意を払った場合、ネストされた量指定子の同様のパターンに気づくでしょう。閉じる引用符が一致に失敗すると正規表現はバックトラックしますが、2番目の選択肢は最初の選択肢で一致した文字と一致することは決してないため、線形にバックトラックします。

この最適化をさらに一歩進めることができます。エスケープされていない文字の実行のためにグループを繰り返す必要はなく、エスケープされた文字とエスケープされていない文字の間でそれを交互にする必要もありません。グループがエスケープされた文字を処理する場合にのみ必要です。"[^"\\]*(?:\\.[^"\\]*)*"は、二重引用符付きの文字列を、ゼロ個以上のエスケープされていない文字と、それに続くゼロ個以上のエスケープされた文字のシリーズと、さらにそれに続くゼロ個以上のエスケープされていない文字のシリーズとして扱います。これで、グループは文字列内のエスケープされていない文字ごとに1つのバックトラック位置のみを記憶します。これにより、正規表現はほぼ任意の長さの文字列に一致できます。文字列に数百万のエスケープされた文字が含まれている場合にのみ、正規表現エンジンの制限に遭遇します。閉じる引用符が一致しない場合、バックトラックします。ただし、すべてのバックトラック試行は、グループがで始まるため、すぐに失敗します\\.これは、〜と相互に排他的です。[^"\\]*.

もし正規表現エンジンがアトミックグループ化または所有格量指定子をサポートしているなら、さらに素晴らしいことができます。"(?>[^"\\]*(?>\\.[^"\\]*)*)"または"[^"\\]*+(?:\\.[^"\\]*+)*+"これらの正規表現は両方とも、閉じる二重引用符をマッチさせようとするときに、すべてのバックトラッキング位置を破棄します。したがって、まったくバックトラックしません。