繰り返し演算子または量指定子に関するトピックでは、最長一致と最短一致の繰り返しについて説明しています。最長一致と最短一致は、正規表現エンジンが正規表現パターンの可能な順列を試行する順序を決定します。最長一致量指定子は、最初にトークンをできるだけ多く繰り返そうとし、エンジンが全体の一致を見つけるためにバックトラックするにつれて、徐々に一致を諦めます。最短一致量指定子は、最初に必要な回数だけトークンを繰り返し、エンジンが正規表現をバックトラックして全体の一致を見つけるにつれて、徐々に一致を拡張します。

最長一致と最短一致は順列が試行される順序を変更するため、正規表現全体の一致を変更できます。ただし、一致が見つからない場合に正規表現エンジンがバックトラックして正規表現のすべての可能な順列を試行するという事実は変わりません。

所有量指定子は、正規表現エンジンがすべての順列を試行するのを防ぐ方法です。これは主にパフォーマンス上の理由で役立ちます。所有量指定子を使用して、特定の一致を除外することもできます。

このチュートリアルで説明されている正規表現フレーバーのうち、所有量指定子はJGsoft、Java、およびPCREでサポートされています。これには、PHP、Delphi、RなどのPCREに基づく正規表現サポートを備えた言語が含まれます。PythonはPython 3.11以降、PerlはPerl 5.10以降、RubyはRuby 1.9以降、BoostはBoost 1.42以降で所有量指定子をサポートしています。

所有量指定子の仕組み

最長一致量指定子と同様に、所有量指定子はトークンをできるだけ多く繰り返します。最長一致量指定子とは異なり、エンジンがバックトラックするときに一致を諦めません。所有量指定子を使用すると、すべてかゼロかのどちらかになります。量指定子の後に+を追加することで、量指定子を所有量指定子にすることができます。*は最長一致、*?は最短一致、そして*+は所有量指定子です。++, ?+と{n,m}+もすべて所有量指定子です。

と一致させようとした場合にどうなるかを見てみましょう"[^"]*+"に対して"abc"。アスタリスクによって繰り返されるため、"は". [^"]と一致しますa, bとc。最後の"は最後の"と一致し、全体の一致が見つかりました。この場合、最長一致量指定子を使用するか所有量指定子を使用するかにかかわらず、最終結果は同じです。ただし、所有量指定子はバックトラッキング位置を記憶する必要がないため、パフォーマンスがわずかに向上します。

正規表現が失敗した場合、パフォーマンスの向上は σημαντικόςです。対象が"abc(閉じ引用符なし)の場合、2番目の"が失敗することを除いて、上記の一致プロセスは同じ方法で発生します。所有量指定子を使用する場合、バックトラックする手順はありません。正規表現には、一致の一部を放棄して正規表現の異なる順列を試すことができる代替または非所有量指定子がありません。したがって、2番目の"が失敗すると、一致の試行はすぐに失敗します。

の代わりに"[^"]*"を最長一致量指定子で使用した場合、エンジンはバックトラックしていました。"が文字列の最後で失敗した後、[^"]*は1つの一致を諦め、ab。アスタリスクによって繰り返されるため、"を残します。 c. [^"]*と一致できず、バックトラックしてaだけになり、"はbと一致できません。最後に、[^"]*はバックトラックしてゼロ文字と一致し、"は失敗しますa。この時点で初めてすべてのバックトラッキング位置が使い果たされ、エンジンは一致の試行を諦めます。基本的に、この正規表現は、一致しない開始引用符の後に続く文字と同じくらい多くの不要な手順を実行します。

所有量指定子が重要な場合

所有量指定子の主な実際的な利点は、正規表現の速度を上げることです。特に、所有量指定子を使用すると、正規表現の失敗を早めることができます。上記の例では、閉じ引用符が一致に失敗した場合、正規表現が引用符をスキップした可能性がないことがわかります。したがって、バックトラックして引用符を確認する必要はありません。量指定子を所有量指定子にすることで、正規表現エンジンにこれを認識させます。実際、JGsoftエンジンを含む一部のエンジンは、正規表現のコンパイル時に[^"]*と"が相互に排他的であることを検出し、アスタリスクを自動的に所有量指定子にします。

さて、単一の量指定子を持つ正規表現のような線形バックトラッキングは非常に高速です。速度の違いに気付くことはまずありません。ただし、量指定子をネストする場合、所有量指定子によって問題が解決する場合があります。量指定子のネストとは、グループ内に1つ以上の繰り返されるトークンがあり、グループも繰り返されることを意味します。それは破滅的なバックトラッキングがしばしば発生する場合です。このような場合、問題を解決するために所有量指定子またはアトミックグループ化に依存します。

所有量指定子は一致結果を変更できる

所有量指定子を使用すると、一致の試行結果が変わる可能性があります。バックトラッキングは行われないため、最長一致量指定子のバックトラッキングが必要な一致は、所有量指定子では見つかりません。たとえば、".*"と一致します"abc"は"abc"xと一致しますが、".*+"はこの文字列とまったく一致しません。

両方の正規表現で、最初の"は文字列の最初の"と一致します。繰り返されるドットは、文字列の残りの部分abc"xと一致します。2番目の"は、文字列の最後で一致に失敗します。

ここで、2つの正規表現のパスが分かれます。所有ドットスターはすべてを望んでいます。バックトラッキングは行われません。"が失敗したため、試行する順列が残っておらず、全体の一致の試行は失敗します。最長一致ドットスターは、最初はすべてを取得しますが、返却しても構いません。一度に1文字ずつバックトラックします。abc", "はxにバックトラックします。abc, "と一致します"にバックトラックします。全体の一致"abc"が見つかりました。

基本的に、ここでの教訓は、所有量指定子を使用する場合、所有量指定子を適用しているものが、それに続くものと一致できないことを確認する必要があるということです。上記の例の問題は、ドットが閉じ引用符とも一致することです。これは、所有量指定子を使用できないようにします。前のセクションの否定文字クラスは閉じ引用符と一致できないため、所有量指定子にすることができます。

所有量指定子の代わりにアトミックグループ化を使用する

技術的には、所有量指定子は、単一の量指定子の周りにアトミックグループを配置するための表記上の便宜です。所有量指定子をサポートするすべての正規表現フレーバーは、アトミックグループ化もサポートしています。ただし、アトミックグループ化をサポートするすべての正規表現フレーバーが所有量指定子をサポートするわけではありません。これらのフレーバーでは、アトミックグループを使用してまったく同じ結果を得ることができます。

基本的に、X*+の代わりに、(?>X*)と記述します。量指定されたトークンXと量指定子の両方がアトミックグループ内にあることに注意することが重要です。Xがグループであっても、同じ効果を得るには、その周りに追加のアトミックグループを配置する必要があります。(?:a|b)*+は(?>(?:a|b)*)と同等ですが、(?>a|b)*とは同等ではありません。後者は有効な正規表現ですが、より大きな正規表現の一部として使用した場合、同じ効果はありません。

説明のために、(?:a|b)*+bと(?>(?:a|b)*)bどちらもマッチしません。b. a|bはbスター量指定子は満たされ、それが所有格量指定子であるかアトミックグループであるという事実により、スターはすべてのバックトラック位置を忘れてしまいます。正規表現の2番目のbはマッチするものがなくなり、全体的なマッチの試みは失敗します。

正規表現(?>a|b)*bでは、アトミックグループは選択肢がそのバックトラック位置を放棄することを強制します。これは、aがマッチした場合、正規表現の残りの部分が失敗してもbを試すために戻ってこないことを意味します。スターはグループの外側にあるため、通常の欲張りなスターです。2番目のbが失敗すると、欲張りなスターはゼロ回の繰り返しにバックトラックします。そして、対象文字列の2番目のbはbにマッチします。

この違いは、所有格量指定子を使用して他の誰かが書いた正規表現を、所有格量指定子を持たない正規表現フレーバーに変換する場合に特に重要です。もちろん、RegexBuddyのようなツールにコンバージョンを任せることもできます。