正規表現におけるバックトラッキングBacktracking in Regular Expressions

バックトラッキングは、正規表現パターンに省略可能な 量指定子 または 代替構成体が含まれている場合に発生します。この場合、正規表現エンジンは、一致の検索を継続するために、以前に保存した状態に戻ります。Backtracking occurs when a regular expression pattern contains optional quantifiers or alternation constructs, and the regular expression engine returns to a previous saved state to continue its search for a match. バックトラッキングは、正規表現を強力にするための中心的な機能で、これにより、非常に複雑なパターンを照合できる強力かつ柔軟な正規表現を作成できるようになります。Backtracking is central to the power of regular expressions; it makes it possible for expressions to be powerful and flexible, and to match very complex patterns. その一方で、バックトラッキングにはマイナス面もあり、At the same time, this power comes at a cost. 多くの場合、正規表現エンジンのパフォーマンスを左右する最大の要因になります。Backtracking is often the single most important factor that affects the performance of the regular expression engine. さいわい、正規表現エンジンの動作とバックトラッキングの使用方法は開発者が制御できます。Fortunately, the developer has control over the behavior of the regular expression engine and how it uses backtracking. ここでは、バックトラッキングの動作のしくみと、バックトラッキングを制御する方法について説明します。This topic explains how backtracking works and how it can be controlled.

注意

一般に、.NET 正規表現エンジンのような非決定性有限オートマトン (NFA: Nondeterministic Finite Automaton) エンジンでは、効率的かつ高速な正規表現を作成する責任は開発者にあります。In general, a Nondeterministic Finite Automaton (NFA) engine like .NET regular expression engine places the responsibility for crafting efficient, fast regular expressions on the developer.

このトピックは、次のセクションで構成されています。This topic contains the following sections:

バックトラッキングを使用しない直線的な比較Linear Comparison Without Backtracking

正規表現パターンに省略可能な量指定子や代替構成体が含まれていない場合、正規表現エンジンは線形時間で実行されます。If a regular expression pattern has no optional quantifiers or alternation constructs, the regular expression engine executes in linear time. つまり、パターンの最初の言語要素を入力文字列のテキストと照合し、パターンの次の言語要素を入力文字列の次の文字または文字グループと照合するという操作が、That is, after the regular expression engine matches the first language element in the pattern with text in the input string, it tries to match the next language element in the pattern with the next character or group of characters in the input string. 照合が最終的に成功または失敗するまで繰り返されます。This continues until the match either succeeds or fails. いずれの場合も、正規表現エンジンは入力文字列内を 1 文字ずつ進みます。In either case, the regular expression engine advances by one character at a time in the input string.

具体的な例を次に示します。The following example provides an illustration. 正規表現 e{2}\w\b は、文字 "e" が 2 回出現した後に任意の単語文字とワード境界が続くパターンを検索します。The regular expression e{2}\w\b looks for two occurrences of the letter "e" followed by any word character followed by a word boundary.

using System;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      string input = "needing a reed";
      string pattern = @"e{2}\w\b";
      foreach (Match match in Regex.Matches(input, pattern))
         Console.WriteLine("{0} found at position {1}", 
                           match.Value, match.Index);
   }
}
// The example displays the following output:
//       eed found at position 11
Imports System.Text.RegularExpressions

Module Example
   Public Sub Main()
      Dim input As String = "needing a reed"
      Dim pattern As String = "e{2}\w\b"
      For Each match As Match In Regex.Matches(input, pattern)
         Console.WriteLine("{0} found at position {1}", _
                           match.Value, match.Index)
      Next   
   End Sub
End Module
' The example displays the following output:
'       eed found at position 11

この正規表現には量指定子 {2}が含まれていますが、この量指定子は直線的に評価されます。Although this regular expression includes the quantifier {2}, it is evaluated in a linear manner. 正規表現エンジンがバックトラックしないのは、 {2} が省略可能な量指定子ではないからです。この量指定子は、前の部分式が一致する必要がある正確な回数 (可変の回数ではなく) を指定しています。The regular expression engine does not backtrack because {2} is not an optional quantifier; it specifies an exact number and not a variable number of times that the previous subexpression must match. 結果として、正規表現エンジンは、次の表に示すような方法でこの正規表現パターンを入力文字列と照合します。As a result, the regular expression engine tries to match the regular expression pattern with the input string as shown in the following table.

操作Operation パターン内の位置Position in pattern 文字列内の位置Position in string 結果Result
11 ee "needing a reed" (インデックス 0)"needing a reed" (index 0) 一致なし。No match.
22 ee "eeding a reed" (インデックス 1)"eeding a reed" (index 1) 一致候補。Possible match.
33 e{2}e{2} "eding a reed" (インデックス 2)"eding a reed" (index 2) 一致候補。Possible match.
44 \w\w "ding a reed" (インデックス 3)"ding a reed" (index 3) 一致候補。Possible match.
55 \b\b "ing a reed" (インデックス 4)"ing a reed" (index 4) 一致候補の失敗。Possible match fails.
66 ee "eding a reed" (インデックス 2)"eding a reed" (index 2) 一致候補。Possible match.
77 e{2}e{2} "ding a reed" (インデックス 3)"ding a reed" (index 3) 一致候補の失敗。Possible match fails.
88 ee "ding a reed" (インデックス 3)"ding a reed" (index 3) 照合の失敗。Match fails.
99 ee "ing a reed" (インデックス 4)"ing a reed" (index 4) 一致なし。No match.
1010 ee "ng a reed" (インデックス 5)"ng a reed" (index 5) 一致なし。No match.
1111 ee "g a reed" (インデックス 6)"g a reed" (index 6) 一致なし。No match.
1212 ee " a reed" (インデックス 7)" a reed" (index 7) 一致なし。No match.
1313 ee "a reed" (インデックス 8)"a reed" (index 8) 一致なし。No match.
1414 ee " reed" (インデックス 9)" reed" (index 9) 一致なし。No match.
1615 ee "reed" (インデックス 10)"reed" (index 10) 一致なし。No match
1616 ee "eed" (インデックス 11)"eed" (index 11) 一致候補。Possible match.
1717 e{2}e{2} "ed" (インデックス 12)"ed" (index 12) 一致候補。Possible match.
1818 \w\w "d" (インデックス 13)"d" (index 13) 一致候補。Possible match.
1919 \b\b "" (インデックス 14)"" (index 14) 一致。Match.

正規表現パターンに省略可能な量指定子や代替構成体が含まれていない場合、正規表現パターンと入力文字列の照合に必要な比較の最大数は、入力文字列の文字数にほぼ等しくなります。If a regular expression pattern includes no optional quantifiers or alternation constructs, the maximum number of comparisons required to match the regular expression pattern with the input string is roughly equivalent to the number of characters in the input string. この場合、正規表現エンジンは、この 13 文字の文字列の一致候補を特定するために 19 回の比較を使用します。In this case, the regular expression engine uses 19 comparisons to identify possible matches in this 13-character string. つまり、正規表現エンジンは、省略可能な量指定子や代替構成体が含まれていない場合にはほぼ線形時間で実行されます。In other words, the regular expression engine runs in near-linear time if it contains no optional quantifiers or alternation constructs.

ページのトップへBack to top

省略可能な量指定子または代替構成体によるバックトラッキングBacktracking with Optional Quantifiers or Alternation Constructs

正規表現に省略可能な量指定子または代替構成体が含まれている場合、入力文字列の評価は直線的ではなくなります。When a regular expression includes optional quantifiers or alternation constructs, the evaluation of the input string is no longer linear. NFA エンジンによるパターン一致の動作は、照合する入力文字列内の文字ではなく、正規表現内の言語要素によって決まります。Pattern matching with an NFA engine is driven by the language elements in the regular expression and not by the characters to be matched in the input string. したがって、正規表現エンジンは、省略可能な部分式や代替の部分式を完全に照合しようとします。Therefore, the regular expression engine tries to fully match optional or alternative subexpressions. 部分式内の次の言語要素に進んで照合が失敗した場合は、正規表現全体を入力文字列と照合するために、それまでに見つかった部分的な一致を放棄して、以前に保存した状態に戻ることもあります。When it advances to the next language element in the subexpression and the match is unsuccessful, the regular expression engine can abandon a portion of its successful match and return to an earlier saved state in the interest of matching the regular expression as a whole with the input string. このように、一致を見つけるために以前に保存した状態に戻るプロセスを、バックトラッキングと呼びます。This process of returning to a previous saved state to find a match is known as backtracking.

例として、 .*(es)という正規表現パターンについて見てみましょう。この正規表現パターンは、文字 "es" と、それに先行するすべての文字に一致します。For example, consider the regular expression pattern .*(es), which matches the characters "es" and all the characters that precede it. 次の例に示すように、入力文字列が "Essential services are provided by regular expressions." の場合、このパターンは、"expressions" の "es" までの文字列全体に一致します。As the following example shows, if the input string is "Essential services are provided by regular expressions.", the pattern matches the whole string up to and including the "es" in "expressions".

using System;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      string input = "Essential services are provided by regular expressions.";
      string pattern = ".*(es)"; 
      Match m = Regex.Match(input, pattern, RegexOptions.IgnoreCase);
      if (m.Success) {
         Console.WriteLine("'{0}' found at position {1}", 
                           m.Value, m.Index);
         Console.WriteLine("'es' found at position {0}", 
                           m.Groups[1].Index);      
      } 
   }
}
//    'Essential services are provided by regular expres' found at position 0
//    'es' found at position 47
Imports System.Text.RegularExpressions

Module Example
   Public Sub Main()
      Dim input As String = "Essential services are provided by regular expressions."
      Dim pattern As String = ".*(es)" 
      Dim m As Match = Regex.Match(input, pattern, RegexOptions.IgnoreCase)
      If m.Success Then
         Console.WriteLine("'{0}' found at position {1}", _
                           m.Value, m.Index)
         Console.WriteLine("'es' found at position {0}", _
                           m.Groups(1).Index)                  
      End If     
   End Sub
End Module
'    'Essential services are provided by regular expres' found at position 0
'    'es' found at position 47

この場合、正規表現エンジンでは次のようにバックトラッキングが使用されます。To do this, the regular expression engine uses backtracking as follows:

  • .* (任意の文字の 0 回以上の出現に一致します) を入力文字列全体と照合します。It matches the .* (which matches zero, one, or more occurrences of any character) with the whole input string.

  • 正規表現パターンの "e" との照合を試みますが、It attempts to match "e" in the regular expression pattern. 入力文字列にはもう照合する文字がありません。However, the input string has no remaining characters available to match.

  • 最後に成功した照合 ("Essential services are provided by regular expressions.") にバックトラックして、"e" を文末のピリオドと照合します。It backtracks to its last successful match, "Essential services are provided by regular expressions", and attempts to match "e" with the period at the end of the sentence. 照合に失敗します。The match fails.

  • 成功した前の照合へのバックトラッキングを一度に 1 文字ずつ繰り返して、暫定的に一致する部分文字列 "Essential services are provided by regular expr" に到達します。It continues to backtrack to a previous successful match one character at a time until the tentatively matched substring is "Essential services are provided by regular expr". その後、パターンの "e" を "expressions" の 2 つ目の "e" と比較して、一致を見つけます。It then compares the "e" in the pattern to the second "e" in "expressions" and finds a match.

  • パターンの "s" を、一致した文字 "e" の後の "s" ("expressions" の 1 つ目の "s") と比較します。It compares "s" in the pattern to the "s" that follows the matched "e" character (the first "s" in "expressions"). 照合に成功します。The match is successful.

バックトラッキングを使用した場合、この正規表現パターンを 55 文字の入力文字列と照合するのに 67 回の比較操作が必要になります。When you use backtracking, matching the regular expression pattern with the input string, which is 55 characters long, requires 67 comparison operations. 一般に、正規表現パターンに 1 つの代替構成体または省略可能な量指定子が含まれている場合、パターンの照合に必要な比較操作の回数は入力文字列の文字数の 2 倍以上になります。Generally, if a regular expression pattern has a single alternation construct or a single optional quantifier, the number of comparison operations required to match the pattern is more than twice the number of characters in the input string.

ページのトップへBack to top

入れ子になった省略可能な量指定子によるバックトラッキングBacktracking with Nested Optional Quantifiers

パターンに多数の代替構成体、入れ子になった代替構成体、または (最もよくあるケースとして) 入れ子になった省略可能な量指定子が含まれていると、正規表現パターンの照合に必要な比較操作の回数は指数関数的に増加する可能性があります。The number of comparison operations required to match a regular expression pattern can increase exponentially if the pattern includes a large number of alternation constructs, if it includes nested alternation constructs, or, most commonly, if it includes nested optional quantifiers. 例として、1 つ以上の文字 "a" から成る文字列全体に一致するように作られた ^(a+)+$ という正規表現パターンについて見てみましょう。For example, the regular expression pattern ^(a+)+$ is designed to match a complete string that contains one or more "a" characters. 次の例では、同じ長さの 2 つの入力文字列が渡されていますが、パターンに一致するのは 1 つ目の文字列だけです。The example provides two input strings of identical length, but only the first string matches the pattern. System.Diagnostics.Stopwatch クラスは、照合操作にかかる時間を調べるために使用されています。The System.Diagnostics.Stopwatch class is used to determine how long the match operation takes.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      string pattern = "^(a+)+$";
      string[] inputs = { "aaaaaa", "aaaaa!" };
      Regex rgx = new Regex(pattern);
      Stopwatch sw;
      
      foreach (string input in inputs) {
         sw = Stopwatch.StartNew();   
         Match match = rgx.Match(input);
         sw.Stop();
         if (match.Success)
            Console.WriteLine("Matched {0} in {1}", match.Value, sw.Elapsed);
         else
            Console.WriteLine("No match found in {0}", sw.Elapsed);
      }
   }
}
Imports System.Diagnostics
Imports System.Text.RegularExpressions

Module Example
   Public Sub Main()
      Dim pattern As String = "^(a+)+$"
      Dim inputs() As String = { "aaaaaa", "aaaaa!" }
      Dim rgx As New Regex(pattern)
      Dim sw As Stopwatch
      
      For Each input As String In inputs
         sw = Stopwatch.StartNew()   
         Dim match As Match = rgx.Match(input)
         sw.Stop()
         If match.Success Then
            Console.WriteLine("Matched {0} in {1}", match.Value, sw.Elapsed)
         Else
            Console.WriteLine("No match found in {0}", sw.Elapsed)
         End If      
      Next
   End Sub
End Module

出力を見るとわかるように、入力文字列がパターンに一致しない場合の処理時間は一致する場合の約 2 倍になります。As the output from the example shows, the regular expression engine took about twice as long to find that an input string did not match the pattern as it did to identify a matching string. これは、照合の失敗は常に最悪のシナリオに相当するためです。This is because an unsuccessful match always represents a worst-case scenario. 正規表現エンジンは、照合の失敗という結論に到達するまでに、正規表現を使用してデータのすべての可能なパスを辿らなければなりません。かっこが入れ子になっていると、データのパスは大幅に増加します。The regular expression engine must use the regular expression to follow all possible paths through the data before it can conclude that the match is unsuccessful, and the nested parentheses create many additional paths through the data. 2 つ目の文字列がパターンに一致しないという結論に到達するまでに正規表現エンジンによって行われる操作を以下に示します。The regular expression engine concludes that the second string did not match the pattern by doing the following:

  • 文字列の先頭にいることを確認し、文字列の最初の 5 文字をパターン a+と照合します。It checks that it was at the beginning of the string, and then matches the first five characters in the string with the pattern a+. 次に、文字 "a" のグループが文字列内にそれ以上ないことを特定します。It then determines that there are no additional groups of "a" characters in the string. 最後に、文字列の終わりをテストします。Finally, it tests for the end of the string. 文字列にまだ文字が 1 文字残っているため、照合は失敗します。Because one additional character remains in the string, the match fails. この照合の失敗に必要な比較は 9 回です。This failed match requires 9 comparisons. 正規表現エンジンは、"a" (以降は照合 1 と呼びます)、"aa" (照合 2)、"aaa" (照合 3)、および "aaaa" (照合 4) の各照合の状態情報を保存します。The regular expression engine also saves state information from its matches of "a" (which we will call match 1), "aa" (match 2), "aaa" (match 3), and "aaaa" (match 4).

  • 以前に保存した照合 4 に戻ります。It returns to the previously saved match 4. 追加のキャプチャ グループに割り当てる必要がある文字 "a" があと 1 つあることを特定します。It determines that there is one additional "a" character to assign to an additional captured group. 最後に、文字列の終わりをテストします。Finally, it tests for the end of the string. 文字列にまだ文字が 1 文字残っているため、照合は失敗します。Because one additional character remains in the string, the match fails. この照合の失敗に必要な比較は 4 回です。This failed match requires 4 comparisons. これまでに実行された比較は合計 13 回になります。So far, a total of 13 comparisons have been performed.

  • 以前に保存した照合 3 に戻ります。It returns to the previously saved match 3. 追加のキャプチャ グループに割り当てる必要がある文字 "a" があと 2 つあることを特定しますが、It determines that there are two additional "a" characters to assign to an additional captured group. 文字列の終わりのテストに失敗します。However, the end-of-string test fails. その後、照合 3 に戻り、2 つの追加のキャプチャ グループの 2 つの追加の文字 "a" を照合しようとしますが、It then returns to match3 and tries to match the two additional "a" characters in two additional captured groups. ここでも文字列の終わりのテストに失敗します。The end-of-string test still fails. これらの照合の失敗に必要な比較は 12 回です。These failed matches require 12 comparisons. これまでに実行された比較は合計 25 回になります。So far, a total of 25 comparisons have been performed.

このようにして、正規表現エンジンがすべての可能な一致の組み合わせを試行し終わるまで入力文字列と正規表現の比較が続けられます。一致しないという結論に到達するのはその後です。Comparison of the input string with the regular expression continues in this way until the regular expression engine has tried all possible combinations of matches, and then concludes that there is no match. この比較は、入れ子になった量指定子があるため、O(2n) (指数演算、n は入力文字列の文字数) です。Because of the nested quantifiers, this comparison is an O(2n) or an exponential operation, where n is the number of characters in the input string. そのため、最悪のケースでは、30 文字の入力文字列で約 1,073,741,824 回、40 文字の入力文字列では約 1,099,511,627,776 回の比較が必要になります。This means that in the worst case, an input string of 30 characters requires approximately 1,073,741,824 comparisons, and an input string of 40 characters requires approximately 1,099,511,627,776 comparisons. 使用する文字列の長さがこのレベル以上になると、正規表現パターンに一致しない入力を処理するときに、正規表現メソッドの完了までに膨大な時間がかかる可能性があります。If you use strings of these or even greater lengths, regular expression methods can take an extremely long time to complete when they process input that does not match the regular expression pattern.

ページのトップへBack to top

バックトラッキングの制御Controlling Backtracking

バックトラッキングを使用すると、強力かつ柔軟な正規表現を作成できますが、Backtracking lets you create powerful, flexible regular expressions. 前のセクションで見たように、受け入れられないほどのパフォーマンスの低下が伴うことがあります。However, as the previous section showed, these benefits may be coupled with unacceptably poor performance. 過度なバックトラッキングを回避するには、 Regex オブジェクトをインスタンス化したり静的な正規表現の一致メソッドを呼び出したりするときに、タイムアウト間隔を定義する必要があります。To prevent excessive backtracking, you should define a time-out interval when you instantiate a Regex object or call a static regular expression matching method. これについては、次のセクションで説明します。This is discussed in the next section. また、.NET では、バックトラッキングを制限または抑制する 3 つの正規表現言語要素がサポートされています。これらを使用すると、パフォーマンスをほとんど低下させずに複雑な正規表現を使用できます。それらの言語要素とは、非バックトラッキング部分式後読みアサーション、および先読みアサーションです。In addition, .NET supports three regular expression language elements that limit or suppress backtracking and that support complex regular expressions with little or no performance penalty: nonbacktracking subexpressions, lookbehind assertions, and lookahead assertions. 各言語要素の詳細については、「 Grouping Constructs」を参照してください。For more information about each language element, see Grouping Constructs.

タイムアウト間隔の定義Defining a Time-out Interval

.NET Framework 4.5.NET Framework 4.5以降では、正規表現エンジンが単一の一致を検索する最長間隔を表すタイムアウト値を設定できます。それを超えると試行が中止され、 RegexMatchTimeoutException 例外がスローされます。Starting with the .NET Framework 4.5.NET Framework 4.5, you can set a time-out value that represents the longest interval the regular expression engine will search for a single match before it abandons the attempt and throws a RegexMatchTimeoutException exception. タイムアウト間隔を指定するには、インスタンス正規表現の TimeSpan コンストラクターに Regex.Regex(String, RegexOptions, TimeSpan) 値を指定します。You specify the time-out interval by supplying a TimeSpan value to the Regex.Regex(String, RegexOptions, TimeSpan) constructor for instance regular expressions. また、各静的パターン一致メソッドには、 TimeSpan パラメーターを持つオーバーロードがあり、これを使用してタイムアウト値を指定できます。In addition, each static pattern matching method has an overload with a TimeSpan parameter that allows you to specify a time-out value. 既定のタイムアウト間隔は Regex.InfiniteMatchTimeout に設定されており、正規表現エンジンはタイムアウトしません。By default, the time-out interval is set to Regex.InfiniteMatchTimeout and the regular expression engine does not time out.

重要

正規表現がバックトラッキングに依存する場合は、常にタイムアウト間隔を設定することをお勧めします。We recommend that you always set a time-out interval if your regular expression relies on backtracking.

RegexMatchTimeoutException 例外では、指定されたタイムアウト間隔中に正規表現エンジンで一致を見つけられなかったことを示しますが、例外がスローされた理由は示しません。A RegexMatchTimeoutException exception indicates that the regular expression engine was unable to find a match within the specified time-out interval but does not indicate why the exception was thrown. 原因は、通常は過度なバックトラッキングですが、例外がスローされたときのシステムの負荷に対して、タイムアウト間隔の設定が短すぎた可能性もあります。The reason might be excessive backtracking, but it is also possible that the time-out interval was set too low given the system load at the time the exception was thrown. 例外を処理するときに、入力文字列との一致の検索をやめるか、タイムアウト間隔を延長して一致操作を再試行するかを選択できます。When you handle the exception, you can choose to abandon further matches with the input string or increase the time-out interval and retry the matching operation.

たとえば、次のコードは Regex.Regex(String, RegexOptions, TimeSpan) コンストラクターを呼び出して、1 秒のタイムアウト値を持つ Regex オブジェクトをインスタンス化します。For example, the following code calls the Regex.Regex(String, RegexOptions, TimeSpan) constructor to instantiate a Regex object with a time-out value of one second. 正規表現パターン (a+)+$は、行の末尾にある 1 つ以上の "a" 文字の 1 つ以上のシーケンスに一致しますが、過度なバックトラッキングの対象になります。The regular expression pattern (a+)+$, which matches one or more sequences of one or more "a" characters at the end of a line, is subject to excessive backtracking. この例では、 RegexMatchTimeoutException がスローされたら、タイムアウト値を 3 秒の最大間隔まで大きくします。If a RegexMatchTimeoutException is thrown, the example increases the time-out value up to a maximum interval of three seconds. その後、パターンに一致させる試行を中止します。After that, it abandons the attempt to match the pattern.

using System;
using System.ComponentModel;
using System.Diagnostics;
using System.Security;
using System.Text.RegularExpressions;
using System.Threading; 

public class Example
{
   const int MaxTimeoutInSeconds = 3;

   public static void Main()
   {
      string pattern = @"(a+)+$";    // DO NOT REUSE THIS PATTERN.
      Regex rgx = new Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1));       
      Stopwatch sw = null;
      
      string[] inputs= { "aa", "aaaa>", 
                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                         "aaaaaaaaaaaaaaaaaaaaaa>",
                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>" };
                                 
      foreach (var inputValue in inputs) {
         Console.WriteLine("Processing {0}", inputValue);
         bool timedOut = false;
         do { 
            try {
               sw = Stopwatch.StartNew();
               // Display the result.
               if (rgx.IsMatch(inputValue)) {
                  sw.Stop();
                  Console.WriteLine(@"Valid: '{0}' ({1:ss\.fffffff} seconds)", 
                                    inputValue, sw.Elapsed); 
               }
               else {
                  sw.Stop();
                  Console.WriteLine(@"'{0}' is not a valid string. ({1:ss\.fffff} seconds)", 
                                    inputValue, sw.Elapsed);
               }
            }
            catch (RegexMatchTimeoutException e) {   
               sw.Stop();
               // Display the elapsed time until the exception.
               Console.WriteLine(@"Timeout with '{0}' after {1:ss\.fffff}", 
                                 inputValue, sw.Elapsed);
               Thread.Sleep(1500);       // Pause for 1.5 seconds.

               // Increase the timeout interval and retry.
               TimeSpan timeout = e.MatchTimeout.Add(TimeSpan.FromSeconds(1));
               if (timeout.TotalSeconds > MaxTimeoutInSeconds) {
                  Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
                                    MaxTimeoutInSeconds);
                  timedOut = false;
               }
               else {               
                  Console.WriteLine("Changing the timeout interval to {0}", 
                                    timeout); 
                  rgx = new Regex(pattern, RegexOptions.IgnoreCase, timeout);
                  timedOut = true;
               }
            }
         } while (timedOut);
         Console.WriteLine();
      }   
   }
}
// The example displays output like the following :
//    Processing aa
//    Valid: 'aa' (00.0000779 seconds)
//    
//    Processing aaaa>
//    'aaaa>' is not a valid string. (00.00005 seconds)
//    
//    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
//    Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
//    
//    Processing aaaaaaaaaaaaaaaaaaaaaa>
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
//    Changing the timeout interval to 00:00:02
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
//    Changing the timeout interval to 00:00:03
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
//    Maximum timeout interval of 3 seconds exceeded.
//    
//    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
//    Maximum timeout interval of 3 seconds exceeded.
Imports System.ComponentModel
Imports System.Diagnostics
Imports System.Security
Imports System.Text.RegularExpressions
Imports System.Threading 

Module Example
   Const MaxTimeoutInSeconds As Integer = 3
   
   Public Sub Main()
      Dim pattern As String = "(a+)+$"    ' DO NOT REUSE THIS PATTERN.
      Dim rgx As New Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1))       
      Dim sw As Stopwatch = Nothing
      
      Dim inputs() As String = { "aa", "aaaa>", 
                                 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                                 "aaaaaaaaaaaaaaaaaaaaaa>",
                                 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>" }
                                 
      For Each inputValue In inputs
         Console.WriteLine("Processing {0}", inputValue)
         Dim timedOut As Boolean = False
         Do 
            Try
               sw = Stopwatch.StartNew()
               ' Display the result.
               If rgx.IsMatch(inputValue) Then
                  sw.Stop()
                  Console.WriteLine("Valid: '{0}' ({1:ss\.fffffff} seconds)", 
                                    inputValue, sw.Elapsed) 
               Else
                  sw.Stop()
                  Console.WriteLine("'{0}' is not a valid string. ({1:ss\.fffff} seconds)", 
                                    inputValue, sw.Elapsed)
               End If
            Catch e As RegexMatchTimeoutException   
               sw.Stop()
               ' Display the elapsed time until the exception.
               Console.WriteLine("Timeout with '{0}' after {1:ss\.fffff}", 
                                 inputValue, sw.Elapsed)
               Thread.Sleep(1500)       ' Pause for 1.5 seconds.

               ' Increase the timeout interval and retry.
               Dim timeout As TimeSpan = e.MatchTimeout.Add(TimeSpan.FromSeconds(1))
               If timeout.TotalSeconds > MaxTimeoutInSeconds Then
                  Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
                                    MaxTimeoutInSeconds)
                  timedOut = False
               Else                
                  Console.WriteLine("Changing the timeout interval to {0}", 
                                    timeout) 
                  rgx = New Regex(pattern, RegexOptions.IgnoreCase, timeout)
                  timedOut = True
               End If
            End Try
         Loop While timedOut
         Console.WriteLine()
      Next   
   End Sub 
End Module
' The example displays output like the following:
'    Processing aa
'    Valid: 'aa' (00.0000779 seconds)
'    
'    Processing aaaa>
'    'aaaa>' is not a valid string. (00.00005 seconds)
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
'    Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaa>
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
'    Changing the timeout interval to 00:00:02
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
'    Changing the timeout interval to 00:00:03
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
'    Maximum timeout interval of 3 seconds exceeded.
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
'    Maximum timeout interval of 3 seconds exceeded.

非バックトラッキング部分式Nonbacktracking Subexpression

(?> subexpression) 言語要素を使用すると、部分式でバックトラッキングがなされないようにすることができます。The (?> subexpression) language element suppresses backtracking in a subexpression. これは、照合の失敗に関連するパフォーマンスの問題の防止に役立ちます。It is useful for preventing the performance problems associated with failed matches.

次の例は、入れ子になった量指定子を使用している場合にバックトラッキングを抑制すると、いかにパフォーマンスが向上するかを示しています。The following example illustrates how suppressing backtracking improves performance when using nested quantifiers. この例では、入力文字列が 2 つの正規表現に一致しないことが正規表現エンジンによって確認されるまでの時間を測定しています。It measures the time required for the regular expression engine to determine that an input string does not match two regular expressions. 1 つ目の正規表現は、1 つ以上の 16 進数、コロン、1 つ以上の 16 進数、2 つのコロンというパターンを 1 つ以上含む文字列を、バックトラッキングを使用して照合します。The first regular expression uses backtracking to attempt to match a string that contains one or more occurrences of one or more hexadecimal digits, followed by a colon, followed by one or more hexadecimal digits, followed by two colons. 2 つ目の正規表現は、バックトラッキングを無効にする以外は 1 つ目と同じです。The second regular expression is identical to the first, except that it disables backtracking. 出力を見るとわかるように、バックトラッキングを無効にするとパフォーマンスが大幅に向上します。As the output from the example shows, the performance improvement from disabling backtracking is significant.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      string input = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:";
      bool matched;
      Stopwatch sw;
      
      Console.WriteLine("With backtracking:");
      string backPattern = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$";
      sw = Stopwatch.StartNew();
      matched = Regex.IsMatch(input, backPattern);
      sw.Stop();
      Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed);
      Console.WriteLine();
      
      Console.WriteLine("Without backtracking:");
      string noBackPattern = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$";
      sw = Stopwatch.StartNew();
      matched = Regex.IsMatch(input, noBackPattern);
      sw.Stop();
      Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed);
   }
}
// The example displays output like the following:
//       With backtracking:
//       Match: False in 00:00:27.4282019
//       
//       Without backtracking:
//       Match: False in 00:00:00.0001391
Imports System.Diagnostics
Imports System.Text.RegularExpressions

Module Example
   Public Sub Main()
      Dim input As String = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:"
      Dim matched As Boolean
      Dim sw As Stopwatch
      
      Console.WriteLine("With backtracking:")
      Dim backPattern As String = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$"
      sw = Stopwatch.StartNew()
      matched = Regex.IsMatch(input, backPattern)
      sw.Stop()
      Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed)
      Console.WriteLine()
      
      Console.WriteLine("Without backtracking:")
      Dim noBackPattern As String = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$"
      sw = Stopwatch.StartNew()
      matched = Regex.IsMatch(input, noBackPattern)
      sw.Stop()
      Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed)
   End Sub
End Module
' The example displays the following output:
'       With backtracking:
'       Match: False in 00:00:27.4282019
'       
'       Without backtracking:
'       Match: False in 00:00:00.0001391

後読みアサーションLookbehind Assertions

.NET には、入力文字列の前の文字と一致する 2 つの言語要素 (?<=subexpression)(?<!subexpression) が含まれています。.NET includes two language elements, (?<=subexpression) and (?<!subexpression), that match the previous character or characters in the input string. これらの言語要素は、どちらもゼロ幅アサーションです。つまり、現在の文字の直前にある文字が subexpressionに一致するかどうかを、前進もバックトラッキングもせずに確認します。Both language elements are zero-width assertions; that is, they determine whether the character or characters that immediately precede the current character can be matched by subexpression, without advancing or backtracking.

(?<= subexpression ) は肯定後読みアサーションで、現在の位置の前にある文字が subexpressionに一致する必要があります。(?<= subexpression ) is a positive lookbehind assertion; that is, the character or characters before the current position must match subexpression. (?<!subexpression) は否定後読みアサーションで、現在の位置の前にある文字が subexpressionに一致しない必要があります。(?<!subexpression) is a negative lookbehind assertion; that is, the character or characters before the current position must not match subexpression. 否定と肯定のどちらの後読みアサーションも、 subexpression が前の部分式のサブセットである場合に特に役立ちます。Both positive and negative lookbehind assertions are most useful when subexpression is a subset of the previous subexpression.

次の例では、メール アドレスのユーザー名を検証する 2 つの同等の正規表現パターンが使われています。The following example uses two equivalent regular expression patterns that validate the user name in an email address. 1 つ目のパターンでは、過度なバックトラッキングのためにパフォーマンスが低下します。The first pattern is subject to poor performance because of excessive backtracking. 2 つ目のパターンでは、1 つ目の正規表現に変更を加えて、入れ子になった量指定子を肯定後読みアサーションに置き換えています。The second pattern modifies the first regular expression by replacing a nested quantifier with a positive lookbehind assertion. この例の出力には、 Regex.IsMatch メソッドの実行時間が表示されます。The output from the example displays the execution time of the Regex.IsMatch method.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      Stopwatch sw;
      string input = "test@contoso.com";
      bool result;
      
      string pattern = @"^[0-9A-Z]([-.\w]*[0-9A-Z])?@";
      sw = Stopwatch.StartNew();
      result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
      sw.Stop();
      Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed);
      
      string behindPattern = @"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@";
      sw = Stopwatch.StartNew();
      result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase);
      sw.Stop();
      Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed);
   }
}
// The example displays output similar to the following:
//       Match: True in 00:00:00.0017549
//       Match with Lookbehind: True in 00:00:00.0000659
Module Example
   Public Sub Main()
      Dim sw As Stopwatch
      Dim input As String = "test@contoso.com"
      Dim result As Boolean
      
      Dim pattern As String = "^[0-9A-Z]([-.\w]*[0-9A-Z])?@"
      sw = Stopwatch.StartNew()
      result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
      sw.Stop()
      Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed)
      
      Dim behindPattern As String = "^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@"
      sw = Stopwatch.StartNew()
      result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase)
      sw.Stop()
      Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed)
   End Sub
End Module
' The example displays output similar to the following:
'       Match: True in 00:00:00.0017549
'       Match with Lookbehind: True in 00:00:00.0000659

最初の正規表現パターン ^[0-9A-Z]([-.\w]*[0-9A-Z])*@は、次の表に示すように定義されています。The first regular expression pattern, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@, is defined as shown in the following table.

パターンPattern 説明Description
^ 文字列の先頭から照合を開始します。Start the match at the beginning of the string.
[0-9A-Z] 英数字 1 文字に一致します。Match an alphanumeric character. Regex.IsMatch メソッドが RegexOptions.IgnoreCase オプションを使用して呼び出されているため、この比較では大文字と小文字が区別されません。This comparison is case-insensitive, because the Regex.IsMatch method is called with the RegexOptions.IgnoreCase option.
[-.\w]* ハイフン、ピリオド、または単語文字の 0 回以上の出現に一致します。Match zero, one, or more occurrences of a hyphen, period, or word character.
[0-9A-Z] 英数字 1 文字に一致します。Match an alphanumeric character.
([-.\w]*[0-9A-Z])* 0 個以上のハイフン、ピリオド、または単語文字の後に英数字が続く組み合わせの 0 回以上の出現に一致します。Match zero or more occurrences of the combination of zero or more hyphens, periods, or word characters, followed by an alphanumeric character. これが最初のキャプチャ グループです。This is the first capturing group.
@ アット マーク ("@") に一致します。Match an at sign ("@").

2 つ目の正規表現パターン ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@では、肯定後読みアサーションが使用されています。The second regular expression pattern, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, uses a positive lookbehind assertion. このパターンは、次の表に示すように定義されています。It is defined as shown in the following table.

パターンPattern 説明Description
^ 文字列の先頭から照合を開始します。Start the match at the beginning of the string.
[0-9A-Z] 英数字 1 文字に一致します。Match an alphanumeric character. Regex.IsMatch メソッドが RegexOptions.IgnoreCase オプションを使用して呼び出されているため、この比較では大文字と小文字が区別されません。This comparison is case-insensitive, because the Regex.IsMatch method is called with the RegexOptions.IgnoreCase option.
[-.\w]* ハイフン、ピリオド、または単語文字の 0 回以上の出現と一致します。Match zero or more occurrences of a hyphen, period, or word character.
(?<=[0-9A-Z]) 最後に照合された文字を後読みして、英数字だった場合は照合を継続します。Look back at the last matched character and continue the match if it is alphanumeric. 英数字は、ピリオド、ハイフン、およびすべての単語文字から成るセットのサブセットです。Note that alphanumeric characters are a subset of the set that consists of periods, hyphens, and all word characters.
@ アット マーク ("@") に一致します。Match an at sign ("@").

先読みアサーションLookahead Assertions

.NET には、入力文字列の次の文字と一致する 2 つの言語要素 (?=subexpression)(?!subexpression) が含まれています。.NET includes two language elements, (?=subexpression) and (?!subexpression), that match the next character or characters in the input string. これらの言語要素は、どちらもゼロ幅アサーションです。つまり、現在の文字の直後にある文字が subexpressionに一致するかどうかを、前進もバックトラッキングもせずに確認します。Both language elements are zero-width assertions; that is, they determine whether the character or characters that immediately follow the current character can be matched by subexpression, without advancing or backtracking.

(?= subexpression ) は肯定先読みアサーションで、現在の位置の後にある文字が subexpressionに一致する必要があります。(?= subexpression ) is a positive lookahead assertion; that is, the character or characters after the current position must match subexpression. (?!subexpression) は否定先読みアサーションで、現在の位置の後にある文字が subexpressionに一致しない必要があります。(?!subexpression) is a negative lookahead assertion; that is, the character or characters after the current position must not match subexpression. 肯定と否定のどちらの先読みアサーションも、 subexpression が次の部分式のサブセットである場合に特に役立ちます。Both positive and negative lookahead assertions are most useful when subexpression is a subset of the next subexpression.

次の例では、完全修飾型名を検証する 2 つの同等の正規表現パターンが使用されています。The following example uses two equivalent regular expression patterns that validate a fully qualified type name. 1 つ目のパターンでは、過度なバックトラッキングのためにパフォーマンスが低下します。The first pattern is subject to poor performance because of excessive backtracking. 2 つ目のパターンでは、1 つ目の正規表現に変更を加えて、入れ子になった量指定子を肯定先読みアサーションに置き換えています。The second modifies the first regular expression by replacing a nested quantifier with a positive lookahead assertion. この例の出力には、 Regex.IsMatch メソッドの実行時間が表示されます。The output from the example displays the execution time of the Regex.IsMatch method.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      string input = "aaaaaaaaaaaaaaaaaaaaaa.";
      bool result;
      Stopwatch sw;
      
      string pattern = @"^(([A-Z]\w*)+\.)*[A-Z]\w*$";
      sw = Stopwatch.StartNew();
      result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
      sw.Stop();
      Console.WriteLine("{0} in {1}", result, sw.Elapsed);

      string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
      sw = Stopwatch.StartNew();
      result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase);
      sw.Stop();
      Console.WriteLine("{0} in {1}", result, sw.Elapsed);
   }
}
// The example displays the following output:
//       False in 00:00:03.8003793
//       False in 00:00:00.0000866
Imports System.Diagnostics
Imports System.Text.RegularExpressions

Module Example
   Public Sub Main()
      Dim input As String = "aaaaaaaaaaaaaaaaaaaaaa."
      Dim result As Boolean
      Dim sw As Stopwatch
      
      Dim pattern As String = "^(([A-Z]\w*)+\.)*[A-Z]\w*$"
      sw = Stopwatch.StartNew()
      result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
      sw.Stop()
      Console.WriteLine("{0} in {1}", result, sw.Elapsed)

      Dim aheadPattern As String = "^((?=[A-Z])\w+\.)*[A-Z]\w*$"
      sw = Stopwatch.StartNew()
      result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase)
      sw.Stop()
      Console.WriteLine("{0} in {1}", result, sw.Elapsed)
   End Sub
End Module
' The example displays the following output:
'       False in 00:00:03.8003793
'       False in 00:00:00.0000866

最初の正規表現パターン ^(([A-Z]\w*)+\.)*[A-Z]\w*$は、次の表に示すように定義されています。The first regular expression pattern, ^(([A-Z]\w*)+\.)*[A-Z]\w*$, is defined as shown in the following table.

パターンPattern 説明Description
^ 文字列の先頭から照合を開始します。Start the match at the beginning of the string.
([A-Z]\w*)+\. 1 個の英文字 (A-Z) の後に 0 個以上の単語文字が続くパターンの 1 回以上の繰り返しの後にピリオドが続くパターンに一致します。Match an alphabetical character (A-Z) followed by zero or more word characters one or more times, followed by a period. Regex.IsMatch メソッドが RegexOptions.IgnoreCase オプションを使用して呼び出されているため、この比較では大文字と小文字が区別されません。This comparison is case-insensitive, because the Regex.IsMatch method is called with the RegexOptions.IgnoreCase option.
(([A-Z]\w*)+\.)* 前のパターンの 0 回以上の繰り返しに一致します。Match the previous pattern zero or more times.
[A-Z]\w* 1 個の英文字の後に 0 個以上の単語文字が続くパターンに一致します。Match an alphabetical character followed by zero or more word characters.
$ 入力文字列の末尾で照合を終了します。End the match at the end of the input string.

2 つ目の正規表現パターン ^((?=[A-Z])\w+\.)*[A-Z]\w*$では、肯定先読みアサーションが使用されています。The second regular expression pattern, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, uses a positive lookahead assertion. このパターンは、次の表に示すように定義されています。It is defined as shown in the following table.

パターンPattern 説明Description
^ 文字列の先頭から照合を開始します。Start the match at the beginning of the string.
(?=[A-Z]) 先頭の文字を先読みして、英文字 (A-Z) だった場合は照合を継続します。Look ahead to the first character and continue the match if it is alphabetical (A-Z). Regex.IsMatch メソッドが RegexOptions.IgnoreCase オプションを使用して呼び出されているため、この比較では大文字と小文字が区別されません。This comparison is case-insensitive, because the Regex.IsMatch method is called with the RegexOptions.IgnoreCase option.
\w+\. 1 個以上の単語文字の後にピリオドが続くパターンに一致します。Match one or more word characters followed by a period.
((?=[A-Z])\w+\.)* 1 個以上の単語文字の後にピリオドが続くパターンの 0 回以上の繰り返しと一致します。Match the pattern of one or more word characters followed by a period zero or more times. 最初の単語文字は英文字でなければなりません。The initial word character must be alphabetical.
[A-Z]\w* 1 個の英文字の後に 0 個以上の単語文字が続くパターンに一致します。Match an alphabetical character followed by zero or more word characters.
$ 入力文字列の末尾で照合を終了します。End the match at the end of the input string.

ページのトップへBack to top

関連項目See also