バックトラッキング
更新 : 2007 年 11 月
正規表現にオプションまたは代替の一致パターンが含まれる場合、正規表現一致エンジンは、入力文字列の評価中のある時点で 1 つまたは複数の方向に分岐することで、可能性のあるパターン一致をすべて実行できます。エンジンが最初に検索した方向で一致する文字列が見つからなかった場合、エンジンは入力文字列の中で分岐が発生した位置まで戻り、代替の一致パターンを試みる必要があります。
たとえば、灰色を意味する 2 種類のスペル gray と grey を検索するためにデザインされる正規表現について考えてみます。代替文字 | を使用して正規表現 gr(a|e)y を作成します。この表現により両方のスペルを検索できます。入力文字列 greengraygrowngrey に適用した場合、エンジンはまず gray を検索するものと仮定します。入力文字列の先頭 2 文字 gr が見つかりますが、その次が green の e なので検索は失敗します。エンジンは r (代替文字より前の部分に一致した最後の文字) までバックトラックし、grey を検索しようとします。e が 2 つあるため、ここでも検索は失敗します。エンジンは検索を続行し、埋め込まれている 2 つの単語 gray と grey が最終的に見つかります。
この正規表現を作成して入力文字列に適用する方法の例を次のコードに示します。
Imports System.Text.RegularExpressions
Module Example
Public Sub Main()
' Define strings: "gray" and "grey".
Dim r As New Regex("gr(a|e)y")
Dim m As MatchCollection = r.Matches("greengraygrowngrey")
Console.WriteLine("Number of groups found: {0}", m.Count)
End Sub
End Module
' The example displays the following output:
' Number of groups found: 2
using System;
using System.Text.RegularExpressions;
public class Example
{
public static void Main()
{
// Define strings: "gray" and "grey".
Regex r = new Regex("gr(a|e)y");
MatchCollection m = r.Matches("greengraygrowngrey");
Console.WriteLine("Number of groups found: {0}", m.Count);
}
}
// The example displays the following output:
// Number of groups found: 2